Corso di
Progettazione di Algoritmi
Docente: Annalisa De
Bonis
matricole congrue ad uno
a.a. 2019-20
Orario delle lezioni
- Lunedì: 11-13, F1
- Mercoledì: 13-15, F1
- Venerdì: 11-13, F1
Orario di
ricevimento
- Durante tutto il periodo in cui la didattica sarà svolta nella modalità a distanza, gli studenti potranno contattare la docente via email per l'attività di ricevimento, attività che potrà eventualmente essere espletata nel corso di un meeting su Teams da concordarsi sempre via email.
- 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
Slide delle
lezioni
- 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 BFS con liste di adiacenza e algoritmo ricorsivo per la visita DFS)
- Grafi (Visita DFS iterativa con stack, componenti connesse, grafi bipartiti)
- Grafi (Connetività forte di grafi direzionati, Ordinamento topologico di un DAG, Esercizi
)
- Algoritmi greedy (Interval Scheduling)
- Algoritmi greedy (Partizionamento di Intervalli, Minimizzazione dei Ritardi)
- Algoritmi greedy (Caching offline)
- Algoritmi greedy (Problema dei cammini minimi e algoritmo di Dijkstra)
- Algoritmi greedy (Problema del minimo albero ricoprente e algoritmo di Prim )
- Algoritmi greedy (Algoritmo di Kruskal)
- Algoritmi greedy (Algoritmo Inverti e cancella, Correttezza algoritmi per MST senza il vincolo sui costi, k-clustering)
- Divide et impera (prima parte)
- Divide et impera (seconda parte)
- Divide et impera (terza parte)
- Divide et impera (quarta parte)
- Divide et impera (quinta parte)
- Divide et impera (sesta parte)
- Algoritmi basati sulla tecnica della programmazione dinamica (prima parte): Interval Scheduling Pesato, Segmented Least Squares.
- Algoritmi basati sulla tecnica della programmazione dinamica (seconda parte): Subset Sums, Problema dello zaino.
- Algoritmi basati sulla tecnica della programmazione dinamica (terza parte): Cammini minimi .
- Algoritmi basati sulla tecnica della programmazione dinamica (quarta parte): Coin change problem , sottosequenza comune piu` lunga, allineamento d sequenze.
- Algoritmi basati sulla tecnica della programmazione dinamica (quinta parte): Ulteriori esempi
- Problemi difficili e ricerca esaustiva intelligente.
File con le informazioni sugli esami a distanza di Progettazione di Algoritmi (aggiornato con ulteriori indicazioni scritte nel file in maiuscolo).
N.B. Gli studenti con PA da 6 CFU che intendono portare il programma aggiornato (senza il flusso e con i nuovi argomenti) devono comunicarlo via mail alla docente almeno una settimana prima della data dell'appello. Gli studenti degli anni precedenti che devono sostenere PA da 9 CFU devono inviare email alla docente solo nel caso in cui vogliano portare il vecchio programma da 9 CFU e devono farlo almeno una settimana prima della data dell'appello. L'oggetto della mail deve essere, per gli studenti con PA da 6 CFU "SOSTENIMENTO APPELLO data_appello CON NUOVO PROGRAMMA DA 6 CFU" mentre quello per gli studenti con PA da 9 CFU deve essere "SOSTENIMENTO APPELLO data_appello CON VECCHIO PROGRAMMA DA 9 CFU", dove al posto di data_appello deve comparire la data dell'appello nel formato giorno/mese/anno.
Non e` possibile cambiare scelta del programma da un appello all'altro a meno che non si tratti di una diversa sessione d'esame. Gli studenti sopra indicati sono comunque tenuti ad inviare mail alla docente almeno una settimana prima dell'appello.
N.B. Gli studenti prenotati agli appelli potranno ricevere una mail dalla docente alla quale dovranno rispondere, nei termini indicati nella mail, per dare conferma della propria partecipazione
alla prova scritta e fornire eventuali informazioni necessarie per la partecipazione alla prova.
Appelli
Avvisi:
- 3/06/2020: Ricordo che gli studenti con PA da 6 CFU che intendono portare il programma aggiornato (senza il flusso e con i nuovi argomenti) devono comunicarlo via mail alla docente almeno una settimana prima della data dell'appello. Gli studenti degli anni precedenti che devono sostenere PA da 9 CFU devono inviare email alla docente solo nel caso vogliano portare il vecchio programma da 9 CFU e devono farlo almeno una settimana prima della data dell'appello.
- 29/05/2020: I risultati dell'esercitazione sono stati comunicati via chat su Teams. Sono stati
fissati due eventi per il team esercitazionePA, uno per mercoledi` 3/6 e l'altro per giovedi` 4/6. A ciascun studente e` stato comunicato quando collegarsi.
- 7/05/2020: La lezione di lunedì 11 maggio è rimandata a martedì 12 maggio dalle 9 alle 11.
- 25/03/2020: I giorni 31/3, 7/4, 21/4 e 28/4, alle 9:00, si terrano le lezioni di recupero di PA.
- 25/03/2020: Ricordo a tutti gli studenti che stanno seguendo le lezioni a distanza di iscriversi al corso di PA per le matricole congrue ad 1 sulla piattaforma di e-learning.
- 16/03/2020: A causa di problemi tecnici, la lezione di oggi è stata registrata. I link ai due video della lezione sono stati inviati via email agli studenti.
Gli studenti potranno pormi domande riguardanti la lezione oggi pomeriggio, dalle 15:30 alle 16:30, attraverso la chat della piattaforma di e-learning.
Le modalità di erogazione delle prossime lezioni a distanza saranno comunicate di volta in volta via email.