Corso di
Progettazione di Algoritmi
Docente: Annalisa De
Bonis
matricole congrue ad uno
a.a. 2023-24
Orario delle lezioni
- Lunedì: 9-11, P4
- Martedì: 15:30-17:30, P4
- Mercoledì: 9-11, P3
Orario di
ricevimento
- L'orario di ricevimento aggiornato è pubblicato qui
Libri di testo
-
KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY.
-
S. DASGUPTA, C. H. PAPADIMITRIOU, AND U. V. VAZIRANI. ALGORITHMS. MCGRAW-HILL
Altri testi utili
-
CORMEN, LEISERSON, RIVEST, STEIN. INTRODUCTION TO ALGORITHMS. THE MIT PRESS, MCGRAW-HILL BOOK COMPANY.
Prove in itinere
Slide delle
lezioni
- Introduzione al corso
- Efficienza degli algoritmi e analisi asintotica degli algoritmi (I parte)
- Efficienza degli algoritmi e analisi asintotica degli algoritmi (II parte)
- Efficienza degli algoritmi e analisi asintotica degli algoritmi (III parte)
- Grafi (I parte: definizioni, proprieta`, visita BFS e proprieta` BFS)
- Grafi (II parte: visita DFS.)
- Grafi (III parte: visita DFS con stack, componenti connesse, ordinamento topologico.)
- Grafi (IV parte: Grafi bipartiti e Esercizi)
- Algoritmi greedy (I parte: Algoritmo di Dijkstra e sua correttezza)
- Algoritmi greedy (II parte: implementazione dell'algoritmo di Dijkstra con coda a priorita`, Interval Scheduling)
- Algoritmi greedy (III parte: Partizionamento di Intervalli)
- Nota su notazioni asintotiche
- Esercitazione del 18 marzo
- Algoritmi greedy (IV parte: Minimizzazione dei ritardi e esercizio del taglio del tubo)
- Algoritmi greedy (V parte: Minimo albero ricoprente e algoritmo di Prim )
- Algoritmi greedy (VI parte: Esempio di esecuzione dell'algoritmo di Prim, Algoritmo di Kruskal.)
- Algoritmi greedy (VII parte: Proprietà del ciclo e algoritmo Inverti-Cancella, k-clustering
- Algoritmi greedy (VIII parte: Codifica di Huffman)
- Divide et impera (I parte): fino a
QuickSelect (aggiornato il 15/4)
- Divide et impera (II parte):
Sottosequenza di somma più grande e soluzione di relazioni di ricorrenza.
- Divide et impera (III parte):
Moltiplicazione veloce di interi, Coppia di punti a distanza minima, Lower bound per il problema dell'ordinamento con confronti.
- Esercitazione
- Programmazione dinamica (I parte: Interval Scheduling Pesato)
- Programmazione dinamica (II parte: Subset Sums, Problema dello zaino)
- Programmazione dinamica (III parte: Minimum Coin Change Problem, Coin Change Problem, Sottosequenza Comune Più Lunga)
- Programmazione dinamica (IV parte: Algoritmo di Bellman-Ford per i cammini minimi - I versione)
- Programmazione dinamica (V parte: Algoritmo di Bellman-Ford con miglioramento, moltiplicazione di matrici)
Appelli
Avvisi:
- 19 aprile 2024.
Venerdì 26/4 comincia il tutorato. Per il momento le lezioni saranno svolte "a distanza".
Vi darò maggiori informazioni a lezione.