ALGORITMI II a.a. 2006/07

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.

Greedy

Descrizione generale. Algoritmi per la pianificazione di intervalli. Algoritmo per la pianificazione che minimizza il ritardo.
Il problema dei cammini minimi con pesi non negativi: algoritmo di Dijkstra. Il problema del minimo albero di copertura: algoritmo di Prim ed algoritmo di Kruskal.
Codici di Huffman. Algoritmi di approssimazione per problemi di ottimizzazione: quantificazione dell'errore.
Algoritmi di approssimazione: il problema della ripartizione, il problema della copertura tramite vertici, il problema della selezione del centro.
[Testo 3: Cap. 4, 11. Testo 2: Cap. 17, 22, 24, 25, 37. Appunti del corso]

Divide et Impera

Descrizione generale. Il problema della somma di sottovettori. Prodotto di matrici. 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.
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. Generalizzazione della
tecnica: Branch & Bound.
[Testo 1: Cap. 7. Appunti del corso]

Testi Consigliati

E. Horowitz, S. Sahni,Fundamentals of Computer Algorithms, Computer Science Press.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli Algoritmi, Jackson Libri (tre volumi).
J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley.
C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e Strutture di Dati, McGraw-Hill.