Il corso intende fornire un'introduzione alle tecniche avanzate di progettazione degli algoritmi, alla complessità computazionale e alla trattabilità dei problemi. Vengono, in particolare, presentate le principali tecniche di dimostrazione di correttezza, esaminate le tecniche di progettazione greedy e di programmazione dinamica, con applicazioni alla soluzione di vari problemi di ottimizzazione, di compressione dei dati e problemi su grafi pesati. Vengono introdotte le classi di complessità P e NP e il concetto di NP-completezza e di riduzione tra problemi. Vengono infine presentate tecniche di progettazione ed analisi di algoritmi approssimati e di algoritmi randomizzati.

Il problema della correttezza degli algoritmi: dimostrazioni per induzione, dimostrazioni di correttezza di algoritmi ricorsivi.

 

Tecniche di progettazione di algoritmi: introduzione agli algoritmi greedy ed alla programmazione dinamica per la soluzione di problemi di ottimizzazione (ad es., problema dello zaino intero e frazionario, percorsi minimi su grafi pesati, i codici di Huffman, problemi di scheduling). Introduzione alla Teoria della Complessità: problemi trattabili e non trattabili, le principali classi di complessità (P e NP), il concetto di riduzione polinomiale tra problemi e il concetto di NP-completezza, esempi di problemi NPcompleti e dimostrazioni di NP-completezza. Introduzione all'intrattablita' computazionale. Introduzione agli algoritmi approssimati; fattore di approssimazione; esempi di algoritmi approssimati per problemi du grafi. Introduzione agli algoritmi randomizzati. Progettazione ed analisi di algoritmi randomizzati per problemi di scheduling e problemi su grafi.