Corso di
Progettazione di Algoritmi
Docente: Annalisa De
Bonis
matricole congrue ad uno
a.a. 2018-19
Orario delle lezioni
- Martedì: 14-16, P3
- Mercoledì: 15-17, P4
- Venerdì: 9-11, P4
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 che potrà eventualmente espletarsi anche con l'ausilio di Teams.
- 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) Aggiornata il 12 marzo
- Grafi (visita DFS, componenti connesse, grafi bipartiti, ordinamento topologico di un DAG)
- Code a priorità
- Algoritmi greedy, prima parte (Interval Scheduling, Interval Partitioning, Problema della minizzazione dei ritardi)
- Algoritmi greedy, seconda parte (Problema del Caching).
- Algoritmi greedy, terza parte i(Problema del Cammini Minimi).
- Algoritmi greedy, quarta parte (Problema del minimo albero ricoprente, k-clustering).
- Divide et impera (prima parte)
- Divide et impera (seconda parte)
- 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.
- Problemi difficili e ricerca esaustiva intelligente.
Appelli
Avvisi: