Algoritmi e strutture dati II
È necessario aver seguito il corso Algoritmi e Strutture Dati I.
B-alberi e hashing per la memoria secondaria.
Alberi di copertura di costo minimo: algoritmo di Kruskal, algoritmo di Prim.
Cammini minimi da sorgente unica: algorimi di Dijkstra, algoritmo di Bellman-Ford.
Heap binomiali e Heap di Fibonacci.
Programmazione dinamica: moltiplicazione di matrici con il minimo numero di prodotti, la piu' lunga sottosequenza a comune fra due stringhe, problema dello zaino intero con/senza ripetizioni, palindrome, proghrammazione delle catene di montaggio.
Algoritmi Greedy: selezione delle attivita', colorazione di un grafo di intervalli, codici di Huffman.
Cammini minimi fra tutte le coppie: algoritmo di Floyd-Warshall, algoritmo analogo alla moltiplicazione di matrici, algoritmo di Johnson per grafi sparsi.
Flusso massimo; metodo di Ford-Fulkerson, algoritmo di Edmonds-Karp.
Non-determinismo e algoritmi enumerativi.
Teoria della NP-completezza e riducibilita'.
Strutture dati per la memoria secondaria. Alberi di copertura di costo minimo. Cammini minimi da sorgente e fra coppie. Programmazione dinamica. Tecnica Greedy. Algoritmi flusso massimo. Non-determinismo e algoritmi enumerativi. Teoria della NP-completezza e riducibilita'.
Lezioni frontali in aula
Per accedere all'esame orale, lo studente deve superare una prova scritta di 2 ore, senza possibilita' di consultare i testi. Una volta superata la prova scritta lo studente dovrà - a pena dell'annullamento della prova - sostenere l'orale nello stesso appello.
1.T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduzione agli algoritmi e strutture dati (Seconda edizione), McGraw-Hill, 2005, ISBN: 88-386-6251-7.