Esonero 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 (6/11/24): (qui).
Esercitazione 2 (12/11/24): (qui).
Esercitazione 3 (19/11/24): (qui).
Esercitazione 4 (27/11/24): (qui).
Esercitazione 5 (18/12/24): (qui).
Esercitazione 6 (7/01/25): (qui).
Problem Set: istruzioni e consigli (qui).
Template Latex (per le soluzioni): pdf , zip .
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
Esercitazione 1 (18/03/25): (qui).
Esercitazione 2 (01/04/25): (qui).
Esercitazione 3 (10/04/25): (qui).
Torna
all'Indice
Ricevimento studenti
Possiamo incontrarci sia in presenza che online. Mandatemi una email per prendere appuntamento.
Torna
all'Indice
Esonero 18/02/25
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
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
