L'obiettivo
del corso è quello di introdurre i concetti fondamentali della progettazione di
algoritmi per problemi polinomiali e problemi computazionali difficili. Il
corso presenterà i concetti di base di progettazione di algoritmi per problemi
di flusso nelle reti e problemi di matching. Tecniche generali come
greedy e programmazione e dinamica saranno applicate a problemi di
cammino minimo, spanning tree, knapsack. Algoritmi di approssimazione saranno
presentati per problemi computazionali difficili come TSP, vertex cover set
cover, sat, scheduling. Particolare enfasi sarà data ai metodi basati sulla
programmazione lineare e gli algoritmi randomizzati. Infine , il corso
introdurrà i principali problemi computazionali in teoria dei giochi.