Corso di
Progettazione di Algoritmi
Docente: Annalisa De
Bonis
matricole congrue ad uno
a.a. 2023-24
Avvisi:
- 11 giugno 2024.
La visione delle prove di mercoledì 12 giugno è riservata agli studenti che non hanno superato le prove intercorso.
Le persone che intendono visionare il compito prima di accettare il voto devono mandare email a adebonis@unisa.it
per chiedere di visionare la prova in altra data. Ovviamente queste persone dovranno sostenere la discussione della prova
22 maggio 2024.
Lunedì 27 maggio non ci sarà lezione. Ci vediamo direttamente alla prove in itinere con gli studenti che si sono prenotati.
19 aprile 2024.
Venerdì 26/4 comincia il tutorato. Per il momento le lezioni saranno svolte "a distanza".
Vi darò maggiori informazioni a lezione.
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)
- Programmazione dinamica (VI parte: Segmented Least Squares, Sottosequenza crescente più lunga)
- Programmazione dinamica (VII parte: Costruzione della sequenza crescente piu` lunga e versione iterativa dell'algoritmo di ottimizzazione; soluzione del problema quando la sequenza crescente consiste di celle consecutive)
- Programmazione dinamica (VIII parte: Parentesizzazione di valore massimo, Problema degli inviti, Problema della sottosequenza palindroma più lunga, Problema della stazione di servizio
- Problemi difficili, Backtracking e Branch and bound .
Appelli