Corso di
Progettazione di Algoritmi
Docente: Annalisa De
Bonis
matricole congrue ad uno
a.a. 2017-18
Orario delle lezioni
- Martedì: 13-15, P3
- Mercoledì: 9-11, P3
- Giovedì: 15-17, P3
Orario di
ricevimento
- Durante il periodo in cui è prevista la didattica a distanza, gli studenti possono inviare email alla docente per l'attività di ricevimento
- L'orario di ricevimento è pubblicato qui
Libri di testo
-
KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY.
-
S. DASGUPTA, C. H. PAPADIMITRIOU, AND U. V. VAZIRANI. ALGORITHMS. MCGRAW-HILL
Prove in itinere
Slide delle
lezioni
N.B. il materiale qui pubblicato NON include tutto quello che viene detto a lezione
e non è in alcun modo sostitutivo dei libri di testo.
- Efficienza degli algoritmi e analisi asintotica degli algoritmi
- Grafi (Definizioni di grafo e di albero, alcune semplici proprietà dei grafi e degli alberi, visita BFS)
- Grafi (visita DFS, componenti connesse, grafi bipartiti, ordinamento topologico di un DAG)
- Algoritmi greedy (prima parte): Interval Scheduling, Interval Partitioning.
- Algoritmi greedy (seconda parte): Problema della minizzazione dei ritardi, Problema del Caching, Problema dei Cammini Minimi.
- Algoritmi greedy (terza parte): Problema del Minimo Albero Ricoprente.
- Divide et impera
- Algoritmi basati sulla tecnica della programmazione dinamica (prima parte): Interval Scheduling Pesato, Segmented Least Squares, Subset Sum, Problema dello Zaino.
- Algoritmi basati sulla tecnica della programmazione dinamica (seconda parte): Allineamento di Sequenze, Algoritmo di Bellman-Ford per i cammini minimi, Sottosequenza comune piu` lunga, Coin Change Problem.
- Massimo flusso.
- Applicazioni del Massimo flusso (prima parte): Massimo Matching.
- Applicazioni del Massimo flusso (seconda parte): Massimo numero di percorsi disgiunti, Connettivita` di una rete, Eliminazione da un campionato di baseball.
- Problemi difficili e ricerca esaustiva intelligente.
Appelli
Avvisi:
- 28/03/2018: Al contrario di quanto detto a lezione, domani non ci sarà lezione. Auguri a tutti di Buona Pasqua!
- 12/03/2018: La lezione di PA di domani (13 marzo) si terra`
dalle 15 alle 17 per dare modo al Prof. Palmieri di svolgere la sua lezione per la classe 2 dalle 13 alle 15.