Descrizione generale del corso

Vengono presentate e analizzate, anche mediante la tecnica
dell'analisi ammortizzata, diverse strutture dati avanzate (quali
B-tree, splay tree, heap binomiali e heap di Fibonacci) e le procedure
per la loro gestione. Inoltre vengono studiati, progettati e analizzati
algoritmi su grafi per la soluzione efficiente di svariati problemi di
ottimizzazione.



PROGRAMMA PARTICOLAREGGIATO DEL CORSO

Analisi ammortizzata
Stack con multipop e contatore binario
Metodi dell'aggregazione, degli accantonamenti e del potenziale
Tabelle dinamiche con inserimenti e cancellazioni

Strutture dati avanzate
B-alberi: applicazioni, altezza, ricerca, inserimenti e cancellazioni
Splay trees: ricerca, inserimenti e cancellazioni, analisi ammortizzata
di m operazioni di cui n sono inserimenti; top-down splay trees
Strutture dati per insiemi disgiunti: unione per ranghi, compressione
dei cammini, algoritmo Union-Find, notazione di Knuth, funzione di
Ackermann e sua inversa
Heap binomiali: alberi binomiali, operazioni di inserimento, minimo ed
estrazione del minimo, decremento di una chiave, cancellazione di una
chiave, unione di due heap binomiali
Heap di Fibonacci: alberi binomiali non ordinati, operazioni di
inserimento, minimo ed estrazione del minimo, decremento di una chiave,
cancellazione di una chiave, unione di due heap di Fibonacci, analisi
ammortizzata

Cammini minimi da una singola sorgente in grafi orientati
Grafo dei cammini minimi, albero dei cammini minimi, algoritmo generico
per i camminimi minimi da singola sorgente, algoritmo di Bellman-Ford,
algoritmo di Dijkstra, algoritmo lineare su grafi aciclici

Cammini minimi tra tutte le coppie di nodi in grafi orientati
Algoritmo di Floyd-Warshall, chiusura transitiva, algoritmo di Johnson su grafi sparsi

Alberi ricoprenti minimi
Passi rossi e passi blu, invariante del colore, algoritmi di Boruvka, di Kruskal e di Prim, clustering di massima separazione

Reti di flusso e applicazioni
Flusso reale e flusso netto in una rete di flusso, proprietà del flusso
netto, reti con sorgenti e pozzi multipli, notazione di sommatoria
implicita, il metodo di Ford-Fulkerson, capacità e rete residue, cammini
aumentanti, tagli in reti di flusso, teorema del massimo flusso/minimo
taglio, analisi della procedura di Ford-Fulkerson, abbinamento massimo
in grafi bipartiti, algoritmo di Edmonds-Karp e sua analisi di
complessità, edge-connectivity.

Il libro di testo consigliato è:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to
algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts,
2009

disponibile anche nella traduzione italiana