Appello 16/02/15
Torna
all'Indice
Programma del corso
Gli argomenti che costituiscono il programma del corso sono quelli trattati sui lucidi presentati a lezione.
Torna
all'Indice
Libro di testo
Si suggerisce come testo di riferimento il seguente libro:
Demetrescu, Finocchi, Italiano
Algoritmi e Strutture Dati
McGraw-Hill
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:
clicca qui
Capitolo 1: Un'introduzione informale agli algoritmi:
clicca qui
Capitolo 2: Modelli di calcolo e notazione asintotica:
clicca qui
Capitolo 2: ricorsione,tecniche di progettazione e equazioni di ricorrenza:
clicca qui
Equazioni di ricorrenza: uno scenario meno comune: Picture-Hanging Puzzles:
clicca qui
Capitolo 4: Ordinare in tempo quadratico (Selection Sort, Insertion Sort):
clicca qui
Capitolo 4: Algoritmi di ordinamento che usano la tecnica del divide et impera: MergeSort e QuickSort:
clicca qui
Capitolo 4: Heap Sort:
clicca qui
Capitolo 4: un lower bound al problema dell'ordinamento (per una classe ragionevole di algoritmi) e algoritmi lineari (fuori da tale classe di algoritmi):
clicca qui
Capitolo 3: Strutture dati elementari; rappresentazioni indicizzate e collegate di alberi; algoritmi di visita di alberi:
clicca qui
Capitolo 6: Alberi binari di ricerca; alberi AVL: clicca qui
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.
clicca qui
Ancora sulla tecnica della programmazione dinamica. Algoritmo per il calcolo della distanza fra due stringhe:
clicca qui
Capitolo 8: Code con priorita'. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci. clicca qui
Problem Set: istruzioni e consigli (qui).
Problem Set 1 (qui). Soluzioni: (qui).
Problem Set 2 (qui). Soluzioni: (qui).
Problem Set 3 (qui). Soluzioni: (qui).
Diario delle lezioni: (qui). Esercizi svolti a lezione: (qui).
Materiale didattico (modulo II)
Teoria dei grafi, problemi su grafi, algoritmi su grafi. Il problema della colorazione di un grafo. clicca qui.
Rappresentazione in memoria di grafi. Visite: ampiezza e profondità; clicca qui.
Applicazioni della visita DFS: cicli, DAG, ordinamento topologico e componenti fortemente connesse; clicca qui.
Cammini minimi in grafi pesati; algoritmo di Dijkstra; clicca qui.
Algoritmo di Bellman e Ford; cammini minimi in DAG pesati; clicca qui.
Cammini minimi fra tutte le coppie: algoritmo di Floy e Warshall e algoritmo di Johnson; clicca qui.
Mantenere efficientemente una collezione di insiemi disgiunti: il problema della Union-Find; clicca qui.
il problema del minimo albero ricoprente: algoritmo di Kruskal; clicca qui.
Algoritmo di Prim; clicca qui.
Diario delle lezioni (Gualà) clicca qui.
Esercizi svolti a lezione (oltre quelli che sono nelle slide); clicca qui.
Qualche altro esercizio; clicca qui.
Dispense: massimo flusso in una rete. clicca qui.
La tecnica greedy. Argomenti coperti: Interval Scheduling, Interval Partitioning, Minimum Lateness, Data Compression e Algoritmo di Huffman.
Slide: algoritmi greedy; algoritmo di Huffman.
Torna
all'Indice
Esonero/Appello 06/02/14
Testo prova scritta (modulo I):
clicca qui
Risultati prova scritta (modulo I):
clicca qui
Torna
all'Indice
Appello 18/06/14
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 14/07/14
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 15/09/14
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/02/15
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,30 alle 16,00. (Contattare il docente per email in tutti gli altri casi).
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