Appello 12/02/18
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 9 crediti del corso, si suggerisce come testo di riferimento il seguente libro:
Demetrescu, Finocchi, Italiano
Algoritmi e Strutture Dati
McGraw-Hill
Per i restanti 3 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
Equazioni di ricorrenza: uno scenario meno comune: Picture-Hanging Puzzles:
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: Alberi binari di ricerca; alberi AVL: pptx , pdf
Capitolo 8: Code con priorita'. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci. pptx , pdf
Tecnica della programmazione dinamica. Il problema della ricerca di un insieme indipendente di peso massimo di un cammino. Algoritmo di programmazione dinamica per il problema con complessità lineare.
pptx , pdf
Ancora sulla tecnica della programmazione dinamica. Algoritmo per il calcolo della distanza fra due stringhe:
pptx , pdf
Problem Set: istruzioni e consigli (qui).
Problem Set 1 (qui).
Problem Set 2 (qui). Soluzioni: (qui).
Esercizi svolti a lezione: (qui).
Un esercizio discusso di programmazione dinamica: (qui).
Diario delle lezioni (modulo I): (qui).
Materiale didattico (modulo II)
Teoria dei grafi, problemi su grafi, algoritmi su grafi. Il problema della colorazione di un grafo. 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
Algoritmo di Bellman e Ford; cammini minimi in DAG pesati; pptx , pdf
Cammini minimi fra tutte le coppie: algoritmo di Floy e Warshall e algoritmo di Johnson; pptx , pdf
Mantenere efficientemente una collezione di insiemi disgiunti: il problema della Union-Find; pptx , pdf
il problema del minimo albero ricoprente: algoritmo di Kruskal; pptx , pdf
Algoritmo di Prim-Jarnik; calcolo degli antenati comuni in un albero e algoritmo di Tarjan. pptx , pdf
Diario delle lezioni (modulo II) clicca qui.
Esercizi svolti a lezione (con soluzioni).
Esercitazione 1: clicca qui.
Esercitazione 2: clicca qui.
Esercitazione 3: clicca qui.
Esercitazione 4: clicca qui.
Esercitazione 5: clicca qui.
Esercitazione 6: clicca qui.
Torna
all'Indice
Appello/Esonero 20/02/17
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Torna
all'Indice
Appello 23/06/17
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 10/07/17
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 19/09/17
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 29/01/18
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 12/02/18
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
Ricevimento studenti
Il normale
orario di ricevimento nel periodo di svolgimento delle lezioni di questo
corso e' il lunedi' dalle 14,45 alle 16,15. (Meglio contattare sempre il docente per email).
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
