Progettazione di Algoritmi a.a. 2012-2013

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 nel programma è data una dimostrazione di correttezza e valutata la complessità di possibili implementazioni. Alla fine di ogni argomento sono elencati i testi consigliati in ordine di rilevanza. Gli appunti saranno pubblicati durante lo svolgimento del corso.

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 1: Cap. 3, 4. Testo 3: Cap. 22, 23. Testo 5: Cap. 12.]

Greedy

Descrizione generale della tecnica. 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.

[Appunti del corso. Testo 1: Cap. 4, 5. Testo 3: Cap. 16, 21, 23, 24. Testo 4: Cap. 4, 11.]

Divide et Impera

Descrizione generale della tecnica. Il problema della somma di sottovettori. Algoritmo per la ricerca della coppia di punti più vicini. Il problema della selezione.

[Appunti del corso. Testo 1: Cap. 2. Testo 4: Cap. 5. Testo 5: Cap. 5, 10.]

Programmazione Dinamica

Descrizione generale della tecnica e confronto con 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.

[Appunti del corso. Testo 1: Cap. 6. Testo 2: Cap. 5. Testo 3: Cap. 15, 24, 25. Testo 4: Cap. 6. Testo 5: Cap. 10.]

Backtracking

Descrizione generale della tecnica. 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.

[Appunti del corso. Test 1: Cap. 9. Testo 2: Cap. 7.]

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.

[Appunti del corso. Testo 1: Cap. 8. Testo 3: Cap. 34]

1. S. Dasgupta, C. Papadimitriou, U. Vazirani      Algorithms   Mac Graw-Hill 2007. Disponibile anche online: Algorithms

2. E. Horowitz, S. Sahni      Fundamentals of Computer Algorithms   Computer Science Press.

3. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein      Introduzione agli algoritmi e strutture dati    Mac Graw-Hill 2005.

4. J. Kleinberg, E. Tardos      Algorithm Design    Addison Wesley, 2005.

5. C. Demetrescu, I. Finocchi, G.F. Italiano      Algoritmi e Strutture di Dati    Mac Graw-Hill 2008.