Propedeuticità

Algoritmi e strutture dati I

Prerequisiti

È necessario aver seguito il corso Algoritmi e Strutture Dati I.

Programma

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’.

Supplement

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’.

Metodi didattici

Lezioni frontali in aula

Modalità di valutazione

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.

Testi consigliati

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.

Post correlati:

• Non ci sono post correlati.