Appello 18/02/25
Torna
all'Indice
Programma del corso
Si veda il diario dettagliato delle lezioni (reperibile in questa pagina, appena le lezioni sono terminate, o sul sito www.informatica.uniroma2.it.)
Torna
all'Indice
Libro di testo
Per i primi 6 crediti del corso, si suggerisce come testo di riferimento il seguente libro:
Demetrescu, Finocchi, Italiano
Algoritmi e Strutture Dati
McGraw-Hill
Per i restanti 6 crediti del corso, si suggerisce invece:
[KT05]
Jon Kleinberg e Eva Tardos
Algorithm Design
Addison Wesley (2005)
Gli argomenti svolti possono essere anche reperiti su altri testi, a piacere
dello studente. Testi utili a tale proposito sono suggeriti nei lucidi della lezione introduttiva.
Torna
all'Indice
Materiale didattico (modulo I)
Introduzione al corso:
pptx , pdf
Capitolo 1: Un'introduzione informale agli algoritmi:
pptx , pdf
Capitolo 2: Modelli di calcolo e notazione asintotica:
pptx , pdf
Capitolo 2: ricorsione,tecniche di progettazione e equazioni di ricorrenza:
pptx , pdf
Capitolo 4: Ordinare in tempo quadratico: il Selection Sort. Algoritmi di ordinamento che usano la tecnica del divide et impera: MergeSort e QuickSort:
pptx , pdf
Capitolo 4: Heap Sort:
pptx , pdf
Capitolo 4: un lower bound al problema dell'ordinamento (per una classe ragionevole di algoritmi) e algoritmi lineari (fuori da tale classe di algoritmi):
pptx , pdf
Capitolo 3: Strutture dati elementari; rappresentazioni indicizzate e collegate di alberi; algoritmi di visita di alberi:
pptx , pdf
Capitolo 6: Il problema del Dizionario; Alberi binari di ricerca; alberi AVL: pptx , pdf
Capitolo 8: Code con priorita'. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci. pptx , pdf
Grafi. Cosa e perché. pptx , pdf
Rappresentazione in memoria di grafi. Visite: ampiezza e profondità. pptx , pdf
Applicazioni della visita DFS: cicli, DAG, ordinamento topologico e componenti fortemente connesse; pptx , pdf
Cammini minimi in grafi pesati; algoritmo di Dijkstra; pptx , pdf
Esercitazione 1 (2/11/23): (qui).
Esercitazione 2 (7/11/23): (qui).
Esercitazione 3 (14/11/23): (qui).
Esercitazione 4 (23/11/23): (qui).
Esercitazione 5 (19/12/23): (qui).
Esercitazione 6 (9/01/24): (qui).
Problem Set: istruzioni e consigli (qui).
Problem Set 1 (qui).
Problem Set 2 (qui).
Diario delle lezioni (modulo I): (qui).
Materiale didattico (modulo II)
Introduzione al modulo 2; pdf
Algoritmi greedy: Interval Scheduling e Interval Partitioning; pdf
Strutture dati Union-Find; pdf
Il problema del Minimum Spanning Tree: l'agoritmo di Kruskal e l'algoritmo di Prim; il problema del k-clustering di massimo spacing; pdf
Programmazione Dinamica I: primo esempio e principi generali; pdf
Programmazione Dinamica II: weighted Interval Scheduling, Longest Increasing Subsequence, House Coloring Problem, Segmented Least Squares, Knapsack problem; pdf
Programmazione Dinamica III: sequence alignment, algoritmo di Hirschberg, cammini minimi in grafi con pesi negativi, algoritmo di Bellman-Ford; pdf
Il problema del massimo flusso e il problema del minimo taglio. L'algoritmo di Ford-Fulkerson; teorema del max-flow min-cut; Scegliere buoni cammini aumentanti;
pdf
Applicazioni del max-flow. Massimo matching su grafi bipartiti. Massimo numero di cammini arco-disgiunti. Image Segmentation. Baseball elimination;
pdf
Introduzione all'NP-completezza. Concetto di riduzione polinomiale. Alcune riduzioni polinomiali;
pdf
Ancora sull'NP-completezza. P vs NP. NP-completezza. Co-NP;
pdf
Ancora sull'NP-completezza. Qualche altra riduzione. Super Mario, Peg Solitaire e Tetris sono NP-completi; pdf
Algoritmi di approssimazione. Algoritmo 2-apx per Load Balancing. Un algoritmo migliore: 3/2-apx per Load Balancing; pdf
Algoritmi di approssimazione. Algoritmo 2-apx per il problema del k-Center; pdf
Tabelle hash; pdf
Esercitazione 1 (19/03/24): (qui).
Esercitazione 2 (04/04/24): (qui).
Esercitazione 3 (16/04/24): (qui).
Esercitazione 4 (07/05/24): (qui).
Esercitazione 5 (21/05/24): (qui).
Problem Set 3 (qui).
Diario delle lezioni (modulo II) clicca qui.
Torna
all'Indice
Ricevimento studenti
Possiamo incontrarci sia in presenza che online. Mandatemi una email per prendere appuntamento.
Torna
all'Indice
Esonero 19/02/24
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Torna
all'Indice
Appello 13/06/24
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Testo prova scritta (modulo II):
clicca qui
Risultati prova scritta (modulo II):
clicca qui
Torna
all'Indice
Appello 16/07/24
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Testo prova scritta (modulo II):
clicca qui
Risultati prova scritta (modulo II):
clicca qui
Torna
all'Indice
Appello 09/09/24
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Testo prova scritta (modulo II):
clicca qui
Risultati prova scritta (modulo II):
clicca qui
Torna
all'Indice
Appello 24/09/24
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Testo prova scritta (modulo II):
clicca qui
Risultati prova scritta (modulo II):
clicca qui
Torna
all'Indice
Appello 21/01/25
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Testo prova scritta (modulo II):
clicca qui
Risultati prova scritta (modulo II):
clicca qui
Torna
all'Indice
Appello 18/02/25
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Testo prova scritta (modulo II):
clicca qui
Risultati prova scritta (modulo II):
clicca qui
Dott. Luciano Gualà
Università di Roma "Tor Vergata"
Via della
Ricerca Scientifica snc
I-00133 Roma, Italy
E-mail: guala@mat.uniroma2.it
URL: http://www.mat.uniroma2.it/~guala
