PROGETTAZIONE DI ALGORITMI a.a. 2011/12

Programma del Corso

Obiettivi

Il corso ha l'obiettivo di presentare idee e tecniche per la progettazione e realizzazione di software efficiente ed elegante. In particolare tali idee e tecniche sono sfruttate in quelle parti di importanti sistemi software (sistemi operativi, compilatori/interpreti, DBMS, ecc.) che devono fornire elevate prestazioni. Enfasi è posta nella definizione e nella dimostrazione rigorosa delle proprietà dei concetti presentati (algoritmi e strutture dati). Il programma del corso si sviluppa in base alle principali tecniche algoritmiche (Greedy, Divide et Impera, Programmazione Dinamica e Backtracking) che sono esemplificate tramite numerosi esempi. I problemi considerati hanno maggiore importanza come esempi di applicazione di una certa tecnica che per il loro interesse intrinseco.

Per ogni algoritmo sottomenzionato, durante il corso, sarà data una dimostrazione di correttezza e valutata la complessità di possibili implementazioni.

Grafi

Rappresentazione tramite matrici di adiacenza o liste di adiacenza. Visite in ampiezza e visite in profondità. Alberi di copertura, alberi dei cammini minimi, componenti fortemente connesse e ordinamento topologico. Cammini minimi in grafi orientati aciclici.
[Testo 2: Cap. 23,25. Testo 4: Cap. 11.]

Greedy

Descrizione generale. Algoritmi per la pianificazione di intervalli. Algoritmo per la pianificazione che minimizza il ritardo. Il problema dei cammini minimi : algoritmo di Dijkstra. Il problema del minimo albero di copertura: algoritmo di Prim ed algoritmo di Kruskal, strutture dati per insiemi disgiunti. Codici di Huffman. Algoritmi di approssimazione e quantificazione dell'errore. Il problema della copertura tramite vertici.
[Testo 3: Cap. 4, 11. Testo 2: Cap. 17, 22, 24, 25. Appunti del corso]

Divide et Impera

Descrizione generale. Il problema della somma di sottovettori. Algoritmo per la ricerca della coppia di punti più vicini. Il problema della selezione.
[Testo 4: Cap. 5, 10. Testo 3: Cap. 5, Appunti del corso]

Programmazione Dinamica

Descrizione generale e confronto con la tecnica Divide et Impera. Algoritmo per il problema della più lunga sottosequenza comune. Distanza tra stringhe. Associatività del prodotto di matrici. Come passare dal valore ottimo alla soluzione ottima. Il problema dei cammini minimi con pesi anche negativi: algoritmo di Bellman-Ford, algoritmo di Floyd e Warshall. Applicazioni: sistemi di vincoli di differenza. Algoritmi pseudopolinomiali: il problema dello zaino a variabili intere.
[Testo 2: Cap. 16, 25. Testo 4: Cap.10. Testo 3: Cap. 6. Testo 1: Cap. 5 Appunti del corso]

Backtracking

Descrizione generale. Enumerazione di strutture semplici: sottoinsiemi, sequenze, permutazioni. Generazione delle possibili soluzioni di un problema: cammini, cammini hamiltoniani, colorazioni. Euristiche di taglio: il problema dello zaino.
[Testo 1: Cap. 7. Appunti del corso]

Calcolabilità e Complessità

Automi a stati finiti. Macchine di Turing. Linguaggi ricorsivamente enumerabili. Linguaggi ricorsivi e linguaggi indecidibili. Indecidibilità del problema della fermata. Riduzione tra linguaggi. La classe NP. La congettura su P ed NP. Problemi NP-completi. Riduzione polinomiale tra linguaggi.
[Testo 2 Appunti del corso]