Algoritmi e Strutture Dati A.A. 2013/14

 

L’obiettivo del corso è quello di introdurre strutture dati e tecniche algoritmiche di base per la soluzione efficiente di problemi su sequenze, liste, alberi e grafi. Nelle lezioni si discuteranno inoltre alcune tecniche analitiche per la valutazione delle prestazioni degli algoritmi, o delle limitazioni inerenti del calcolo.

 

Orario Lezioni
Orario lezione Aula Tipo
Martedì 10:30-13:30 F06 Teoria
Giovedì 13:30-15:30 Si5 Laboratorio
Venerdì 10:30-12:30 F06 Teoria
Venerdì 13:30-15:30 Si1 Laboratorio

Ricevimento su appuntamento.

 

Appelli
Data Ora Aula Tipo
10/06/2014 10:30 Si3 Laboratorio Testo
TestSet
12/06/2014 15:00 F09 Scritto Testo
02/07/2014 13:30 Si3/Si7 Laboratorio Testo
TestSet
03/07/2014 15:00 F09 Scritto Testo
23/07/2014 13:30 Si3/Si7 Laboratorio Esame
TestSet
24/07/2014 15:00 F09 Scritto Testo
16/09/2014 13:30 Si3/Si7 Laboratorio Testo
TestSet
18/09/2014 15:00 F09 Scritto Testo
12/01/2015 13:30 Si3/Si7 Laboratorio Testo
TestSet
14/01/2015 15:00 F09 Scritto Testo
28/01/2015 13:30 Si3/Si7 Laboratorio Testo
TestSet
30/01/2015 15:00 F09 Scritto Testo
17/02/2015 13:30 Si3/Si7 Laboratorio Testo
TestSet
19/02/2014 15:00 F09 Scritto Testo

Nota: uno studente che abbia superato una prova scritta può ripresentarsi alle successive prove. Il voto sarà quello ottenuto nell’ultima prova consegnata.

Testi
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. Versione Italiana [CLRS] [Testo Consigliato]
  • Jeff Erickson. Algorithms, 2013. Online [E]
  • Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Algorithms. McGraw-Hill, 2006. [DPV]
  • Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005. [KT]
  • Kurt Mehlhorn and Peter Sanders. Data Structures and Algorithms: The basic toolkit. Springer, 2008. Online [MS]

 

Esercizi

 

Registro delle Lezioni
Data Argomento Rif. Bibliografici
12/03/2014 Introduzione al corso e puzzle.  puzzle (facoltativi)
14/03/2014 Problema, istanza, dimensione dell’istanza, complessità in tempo al caso pessimo, caso ottime e caso medio, analisi asintotica e confronto di algoritmi. Insertion Sort e analisi. Notazione asintotica: O-grande, Omega e Theta, con esempi. Cap. 1, 2.1, 2.2, 3.1 [CLRS]
18/03/2014 Tecnica “divide et impera”. MergeSort: algoritmo, proprietà, e analisi della complessità. Relazioni di ricorrenza e teorema per la loro risoluzione. Ricerca Binaria. Soluzione di alcuni esercizi. Cap 2.3, 4.0, 4.4, 4.5 [CLRS]
21/03/2014 Relazioni di ordine k. Fibonacci: triviale, con memorizzazione e con matrice. Esercizi Divide et impera. Relazioni di ordine k. Sez. 3 Numeri di Fibonacci
25/03/2014 Quicksort: algoritmo, complessità nel caso ottimo, pessimo e medio (con dimostrazione). Procedura Partition. Limiti inferiori con albero delle decisioni. Esercizi divide et impera. Cap. 7, 8.1 [CLRS]
01/04/2014 Ordinare in tempo lineare: Counting Sort e Radix Sort. Code di priorità: definizione di Heap, proprietà, realizzazione come array, operazioni e costruzione in tempo lineare. Cap. 8.2, 8.3, 6.1, 6.2, 6.3 [CLRS]
04/04/2014 HeapSort e operazioni Heap. Esercizi. Cap. 6.4, 6.5 [CLRS]
08/04/2014 Alberi binari di ricerca: definizione, proprietà, visite, ricerca, min, max, predecessore e successore, con analisi della complessità in tempo. Esercizi. Cap. 12.1, 12.2, 12.3 [CLRS]
15/04/2014 Problema del dizionario. Tabelle hash e gestione delle collisioni con liste di trabocco e open addressing. Cap. 11.1, 11.2, 11.4 [CLRS] (senza dimostrazioni)
29/04/2014 Grafi: definizione, notazione, terminologia, rappresentazioni (matrice di adiacenza e liste di adiacenza). Visita BFS con analisi di complessità ed esempio e cammino minimo. Cap. 22.1, 22.2 [CLRS]
02/05/2014 Esercizi Alberi binari di ricerca e Heap.
06/05/2014 Visita DFS con analisi di complessità e proprietà. Esercizi. Cap. 22.3, Lemma 22.11 in Cap. 22.4
13/05/2014 Algoritmo di Dijkstra: proprietà ed esempi. Esercizi. Cap. 24.0, 24.3, 24.5
16/05/2014 Esercizi di riepilogo.
20/05/2014 Programmazione Dinamica: Problema dello zaino e calcolo della distanza di edit tra due stringhe. Cap. 15.3; Edit Distance, Problema dello zaino, xkcd
27/05/2014 Classi P e NP. Problemi NP-Completi. Riduzioni. Cap. 34.0; Note su riduzioni
30/05/2014 Simulazione prova d’esame. Testo