P. Crescenzi, G. Gambosi, R. Grossi. “Strutture di Dati e Algoritmi. Progettazione, analisi e visualizzazione”, Pearson Education Addison-Wesley, 2006
Obiettivi Formativi
Conoscenze:
Metodi per la progettazione e l'analisi di algoritmi efficienti
Competenze acquisite
Applicazione di tecniche avanzate per la progettazione e l'analisi di algoritmi efficienti
Capacità acquisite al termine del corso:
Progettazione e analisi di algoritmi efficienti
Prerequisiti
Corsi raccomandati: Algoritmi e Strutture Dati
Metodi Didattici
Numero di ore totali del corso: 150
Numero di ore per studio personale e altre attività formative di tipo individuale: 102
Numero di ore relative alle attività in aula: 48
Altre Informazioni
Martedi', dalle 11.30 alle 13.30.
Orario di ricevimento
Modalità di verifica apprendimento
Modalità:
Scritto e orale
Programma del corso
Contenuti del corso (programma dettagliato):
Divide et impera: distanza minima tra coppie di punti, intersezione di segmenti, diagramma di Voronoi, moltiplicazione di polinomi, trasformata veloce di Fourier. Randomizzazione: test di primalità, skip list, hashing universale.
Analisi ammortizzata: tabelle dinamiche.
Algoritmi greedy: codice di Huffman, problema del commesso viaggiatore, schedulazione di attività, cammini minimi, minimo albero ricoprente, bin packing.
Programmazione dinamica: moltiplicazione di matrici, alberi binari di ricerca ottimali, distanza tra due stringhe, ricerca approssimata di stringhe, allineamento di sequenze. Ricerca all'interno di testi.