Algoritmi e Strutture Dati [moduli 1 e 2]

  Algoritmi e Strutture Dati [moduli 1 e 2 - 12 CFU]
  Anno Accademico 2014/2015
  Corso per Studenti Part Time

  Docente Dr. Damiano Macedonio
  Dipartimento di Scienze Ambientali, Informatica e Statistica
  Università Ca’ Foscari di Venezia

Contenuti (ultimo aggiornamento: 27 luglio 2015)

Comunicazioni
Programma del Corso
Materiale Didattico
Lezioni in Dettaglio
Prove di Esame

Comunicazioni

Orario lezioni:
- sabato ore 9:30-12:00 Aula C.
Ricevimento: al sabato prima/dopo lezione. Previo appuntamento via mail.
Prossimi appuntamenti:
- Sabato 4 luglio ore 9:00, aula 1 complesso Zeta: esercitazione straordinaria prima/seconda parte del corso.
Risultati esami:
- Appello del 04 luglio 2015: chi accetta la registrazione del voto deve comunicarlo via e-mail al docente.
- Appello del 23 maggio 2015: chi accetta la registrazione del voto deve comunicarlo via e-mail al docente.
Esame:
- Una prova scritta (su esercizi, risoluzione di problemi, teoremi) per ciascuno dei due moduli del corso.
- Le due prove scritte sono indipendenti:
  - Possono essere affrontate in appelli/sessioni di esame differenti.
  - Possono essere ripetute a discrezione dello studente.
  - La consegna di un nuovo scritto annulla automaticamente l'eventuale voto precedente.
- L'esame è superato se entrambe le prove scritte hanno ottenuto una valutazione sufficiente (voto maggiore o uguale a 18).
- Il voto finale è dato dalla media dei due scritti.
- A discrezione del docente, può essere richiesta una prova orale. Il voto fa media con quello dello scritto.
- Per gli studenti del vecchio ordinamento:
  - Metodologico: attenetevi al programma (9 CFU) del 2012/2013.
  - Professionalizzante: per acquisire i 15 CFU dovete superare gli scritti di questo nuovo corso (12 CFU) più una integrazione (3 CFU). L'integrazione riguarda le reti di flusso e prevede l'assegnazione di un progetto.

Programma del Corso

Modulo A
- Algoritmi, modelli di calcolo e metodologie di analisi. Introduzione informale agli algoritmi. Modelli di calcolo. Notazione asintotica. Ricorrenze.
- Strutture dati elementari. Array, liste. Pile, code. Alberi.
- Ordinamento. Heapsort. Mergesort. Quicksort. Mediane e statistiche d'ordine.
- Alberi di ricerca. Alberi binari. Alberi AVL.
- Hashing. Tavole ad accesso diretto. Tavole hash. Risoluzione delle collisioni.
Modulo B
- Tecniche fondamentali per il progetto di algoritmi. Tecnica divide et impera. Programmazione dinamica. Algoritmi golosi (o greedy).
- Grafi e visite di grafi. Rappresentazione di grafi. Visita in ampiezza. Visita in profondità. Ordinamento topologico. Componenti fortementi connesse.
- Alberi di copertura minimi. Definizioni e proprietà. Algoritmi di Kruskal e Prim.
- Cammini minimi. Definizioni e proprietà. Algoritmi di Dijkstra, Bellman-Ford e Floyd-Warshall.
- Problemi NP-completi. Classi di complessità P e NP. Riducibilità polinomiale e NP-completezza. Esempi di problemi NP-completi.
Testi di Riferimento:
- [T1] Testo principale:
  C. Demetrescu, I. Finocchi, G. F. Italiano.
  Algoritmi e strutture dati (seconda edizione), McGraw-Hill, 2008.
- [T2] Testo di consultazione:
  T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.
  Introduction to Algorithms (3rd Edition), MIT Press, 2009.
  Traduzione italiana a cura di Livio Colussi edita da McGraw-Hill, Milano, 2010.

Materiale Didattico

Top

Introduzione al corso.
Esercizi di Algoritmi e Strutture Dati, dispensa scritta dal dott. Moreno Marzolla.
Appunti delle lezioni
- Capitolo 01. Traccia della lezione del 11 ottobre 2014: introduzione informale agli algoritmi.
- Capitolo 02. Traccia delle lezioni del 15-29 novembre 2014: metodologie di analisi.
- Capitolo 03. Integrazione della lezione del 06 dicembre 2014: correttezza degli algoritmi.
- Capitolo 04. Traccia delle lezioni del 06-13 dicembre 2014: pile, code e alberi.
- Capitolo 05. Traccia della lezione del 20 dicembre 2014: alberi binari di ricerca.
- Capitolo 06. Integrazione facoltativa della lezione del 21 febbraio 2015: heap binari e code di priorità.
- Capitolo 07. Integrazione facoltativa delle lezioni del 7-21 febbraio 2015: algoritmi di ordinamento;.
- Capitolo 08. Integrazione su tabelle hash.
- Capitolo 09. Traccia della lezione del 07 marzo 2015.
- Capitolo 10. Traccia delle lezioni del 21-28 marzo 2015.
- Capitolo 11. Integrazione facoltativa della lezione del 18 aprile 2015.
- Capitolo 12. Traccia della lezione del 9 maggio 2015 (solo l'algoritmo di Floyd-Warshall).
Presentazioni
- Lucidi 01. Lezioni del 25 ottobre 2014 e 8 novembre 2014: tecniche di analisi degli algoritmi.
- Lucidi 02. Lucidi delle Lezioni del 06-13 dicembre 2012: strutture dati elementari.
- Lucidi 03. Lucidi della Lezione del 20 dicembre 2014: Alberi Binari di Ricerca.
- Lucidi 04. Lucidi delle Lezioni del 20 dicembre 2014 e 7 febbraio 2015: Alberi AVL.
- Lucidi 05. Traccia delle Lezioni del 21-14 febbraio 2012: Algoritmi di Ordinamento.
- Lucidi 06. Traccia della lezione del 28 febbraio 2015.
- Lucidi 07. Traccia della lezione del 14 marzo 2015.
- Lucidi 08. Traccia della lezione del 18 aprile 2015.

Lezioni in Dettaglio

Top

04 ott 2014. Introduzione al corso [pdf].
11 ott 2014. Riferimenti: Capitolo 1 del testo principale [T1]; Capitolo 1 degli Appunti. Introduzione agli algoritmi. Numeri di Fibonacci: algoritmo numerico e algoritmo ricorsivo. Analisi di algoritmi ricorsivi con albero delle ricorrenze. Occupazione di memoria.
18 ott 2014. Riferimenti: Capitolo 1 del testo principale [T1]; Capitolo 1 degli Appunti. Introduzione agli algoritmi. Numeri di Fibonacci: algoritmo iterativo e algoritmo basato su potenze ricorsive. Cenni sulla notazione asintotica. Analisi della complessità di algoritmi basati su potenze ricorsive. Esercizi proposti: Esercizi 1.2 e 1.3; Problema 1.3 del testo principale [T1].
25 ott 2014. Riferimenti: Capitolo 2, sezioni 2.1 - 2.2 - 2.3 - 2.4 - 2.5 del testo principale [T1]; Lucidi della lezione. Modelli di calcolo. Notazione asintotica. Delimitazioni inferiori e superiori. Rapporto tra classi di complessità.
8 nov 2014. Riferimenti: Capitolo 2, sezioni 2.1 - 2.2 - 2.3 - 2.4 - 2.5 del testo principale [T1]; Lucidi della lezione. Analisi di algoritmi iterativi: ricerca del minimo in un array e ordinamento con Selection Sort. Analisi di algoritmi ricorsivi. Ricerca sequenziale: analisi temporale del caso migliore, caso pessimo e caso medio. Ricerca Binaria: analisi temporale del caso migliore e caso pessimo. Descrizione del metodo di iterazione e di sostituzione con esempi. Esercizi proposti: Esercizi 2.1 - 2.2 - 2.5; Problemi 1.3 - 2.1 - 2.2 - 2.3 del testo principale [T1].
15 nov 2014. Riferimenti: Capitolo 2, sezione 2.5 del testo principale [T1]; Capitolo 2 degli Appunti; Lucidi della lezione. Metodo di sostituzione e iterazione: casi particolari. Analisi delle relazioni di ricorrenza derivate da algoritmi basati sulla tecnica "divide et impera". Teorema fondamentale delle ricorrenze, caso 2: enunciato, dimostrazione e applicazioni.
29 nov 2014. Riferimenti: Capitolo 2, sezione 2.5; Capitolo 3, sezioni 3.1 - 3.2 del testo principale [T1]; Capitolo 2 degli appunti. Teorema fondamentale delle ricorrenze: enunciato completo senza dimostrazione. Esempi di analisi di algoritmi e applicazione del teorema fondamentale. Relazioni di ricorrenza non risolvibili con il teorema fondamentale. Analisi dell'albero della ricorsione. Esercizi proposti: Esercizi 2.1 - 2.6 - 2.7 - 2.9 - 2.11; Problemi 2.5 - 2.8 - 2.9 - 2.10, [T1] pagg. 57/58/59; Capitolo 1 della dispensa Esercizi di Algoritmi e Strutture Dati.
06 dic 2014. Riferimenti: Capitolo 3, sezioni 3.1 - 3.1.2 del testo principale [T1]; Capitolo 3 e Capitolo 4 degli Appunti; Lucidi della lezione. Correttezza degli algoritmi. Strutture dati indicizzare e collegate. Dizionari.
13 dic 2014. Riferimenti: Capitolo 3, Sezioni 3.2 - 3.3 del testo principale [T1]. Pile: definizione, implementazione con array usando tecnica del raddoppio e dimezzamento. Analisi ammoritizzata. Code: definizione, implementazione con array circolari. Alberi: definizione, rappresentazioni indicizzate, rappresentazioni collegate. Visite in profondità (preordine, simmetrica, postordine), visita in ampiezza. Esercizi. Esercizi proposti: Esercizi 3.4 - 3.5; Problemi 3.3 - 3.6 - 3.7 del testo principale [T1]; Esercizi 2.7 - 2.8 - 2.9 - 2.10 - 2.11 - 2.20 - 2.21 - 2.22 - 2.25 - 2.34 della dispensa Esercizi di Algoritmi e Strutture Dati.
20 dic 2014. Riferimenti: Capitolo 6, Sezioni 6.1 - 6.2 - 6.2.1 del testo principale [T1]; consiglio anche le Sezioni 12.1 - 12.2 - 12.3 di [T2]; Lucidi su ABR e Lucidi su AVL. Alberi binari di ricerca: definizione, propietà, visita in ordine, ricerca di una chiave, ricerca del minimo/massimo, ricerca del predecessore/successore, inserimento e cancellazione. Alberi AVL: fattore di bilanciamento e definizione, altezza di un albero bilanciato. Esercizi proposti: Esercizio 6.1; Problema 6.1 del testo principale [T1]; Esercizi 2.3 - 2.4 - 2.5 - 2.6 - 2.8 - 2.14 della dispensa Esercizi di Algoritmi e Strutture Dati.
07 feb 2015. Riferimenti: Capitolo 6, Sezione 6.2 - 6.2.1 - 6.2.2 - 6.2.3 - del testo principale [T1]; Lucidi della lezione. Alberi AVL: ri-bilanciamento tramite rotazioni, ricerca, inserimento e cancellazione. Esercizi proposti: Esercizi 6.4 - 6.5 - 6.6; Problemi 6.2 - 6.3 - 6.4 - 6.6 del testo principale [T1].
14 feb 2015. Riferimenti: Capitolo 4, Sezione 4.2 - 4.2.1 - 4.2.2 - 4.5 - 4.5.1 - del testo principale [T1]; Lucidi della lezione. Problema dell'ordinamento. Ordinamento in tempo quadratico: Insertion Sort, Selection Sort, Bubble Sort. Procedura Partition per Quick Sort: esempio di esecuzione, correttezza e complessità. Algoritmo Quick Sort: correttezza e complessità con analisi del caso peggiore, del caso migliore, e caso medio. Quick Sort randomizzato. Un link interessante: Sorting Algorithm Animations. Esercizi proposti: Esercizi 4.2 ; Problemi 4.1 - 4.7 - 4.11 - 4.12 - 4.13 del testo principale [T1]; Esercizi 3.1 - 3.2 - 3.4 - 3.6 - 3.9 - 3.10 - della dispensa Esercizi di Algoritmi e Strutture Dati.
21 feb 2015. Riferimenti: Capitolo 4, Sezione 4.1 - 4.1.1 - 4.1.2 - 4.3 - 4.3.1 - 4.3.2 - 4.4 - 4.6 - 4.7 del testo principale [T1]; Lucidi della lezione. Merge Sort: analisi, correttezza e complessità. Heap binari: definizione, altezza, numero di nodi interni e foglie. Struttura MaxHeap. Procedure fixHeap e heapify: descrizione, correttezza e complessità. Cenni alla coda con priorità implementata da Heap binomiale (consiglio le Sezioni 7.1 - 7.2 di [T2]. ). Algoritmo Heap Sort: correttezza, complessità, esempi di esecuzione. Alberi di decisione. Limitazione inferiore del numero di confronti per algoritmi di ordinamento. Esercizi proposti: Esercizi 4.1 - 4.2 - 4.5 - 4.3 - 4.7 - 4.10 - 4.14 - 4.12; Problema 4.3 - 4.4 - 4.8 - del testo principale [T1]; Esercizi 3.3 - 3.5 - 3.7 - 3.8 - 3.11 - 3.12 della dispensa Esercizi di Algoritmi e Strutture Dati.
28 feb 2015. Capitolo 4, Capitolo 7 del testo principale [T1]; Lucidi-05 Lucidi-06 della lezione. Tecniche lineari di ordinamento: Counting Sort, Bucket Sort, Radix Sort. Visione generale (pregi e difetti) degli algoritmi di odinamento. Hashing. Tabelle ad accesso diretto. Tabelle hash. Funzioni hash. Uniformità semplice. Risoluzione delle collisioni: liste di collisione, indirizzamento aperto con scansione lineare, quadratica e hashing doppio. Inserimento, ricerca e cancellazione chiavi in tempo medio costante.
07 mar 2015. Sezione 12.0 - 12.1 del testo principale [T1]; Capitolo 9 degli Appunti. Introduzione ai grafi. Grafi orientati e non orientati. Sottografo e sottografo indotto. Cammini e cicli. Distanza tra vertici. Grafi connessi e grafi completi. Componenti connesse e clique. Alberi liberi e loro principali proprietà.
14 mar 2015. Sezione 12.1 - 12.2 - 12.3 - 12.4 - 12.5 - 12.5.1 del testo principale [T1]. Lucidi della lezione. Grado di un vertice in grafi orientati e non orientati. Lemma della stretta di mano. Rappresentazione di grafi: lista di archi, liste di adiacenza, matrice di adiacenza. Confronto tra le varie rappresentazioni analizzando le principali operazioni sui grafi. Visite di grafi non orientati. Visita in ampiezza e in profondità. Proprietà della visita in ampiezza. Albero di copertura. Albero dei cammini minimi. Ricerca delle componenti connesse e delle componenti fortemente connesse. Esercizi proposti: Esercizi 12.1 - 12.2 - 12.3 - 12.4 - 12.5 - 12.6 - 12.7; Problema 12.4 - 12.6 del testo principale [T1]; Esercizi 8.1 - 8.2 - 8.3 - 8.4 - 8.5 - 8.6 - 8.8 - 8.10 - 8.12 -8.13 - 8.14 - 8.15 - 8.20 - 8.21 della dispensa Esercizi di Algoritmi e Strutture Dati.
21 mar 2015. Sezioni 13.0 - 13.1 del testo principale [T1]; Capitolo 10 degli Appunti. Consiglio anche le Sezioni 23.0 - 23.1 di [T2]. Grafi pesati. Alberi di copertura minimi: definizione, proprietà e teorema fondamentale.
28 mar 2013. Sezioni 13.2 - 13.3 del testo principale [T1]; Capitolo 10 degli Appunti. Consiglio anche la Sezione 23.2 di [T2]. Algoritmo di Kruskal: correttezza, complessità ed esempio di esecuzione. Gestione di insiemi disgiunti.
11 apr 2015. Sezioni 13.2 - 13.3 del testo principale [T1]; Capitolo 10 degli Appunti. Consiglio anche la Sezione 23.2 di [T2]. Algoritmo di Prim: correttezza, complessità (a seconda delle strutture dati utilizzate) ed esempio di esecuzione. Esercizi proposti: Esercizio 13.2 - 13.3 - 13.4 - 13.5 - 13.8; Problema 13.1 - 13.2 - 13.3 - 13.4 del testo principale [T1]; Esercizio 8.11 della dispensa Esercizi di Algoritmi e Strutture Dati.
18 apr 2015. Sezione 14.1 - 14.2 - 14.3 - 14.5 del testo principale [T1]; Lucidi della lezione. Consiglio anche la Sezione 24.1 - 24.2 - 24.4 - 24.6 di [T2]. Cammini minimi in grafi orientati. Distanza tra nodi. Varianti del problema dei cammini minimi. Osservazioni su cicli di peso negativo. Rappresentazione dei camini minimi: albero dei cammini minimi. Principali propriettà. Sottostruttura ottima. Cammini minimi da sorgente unica. Lemma di Dijkstra. Algoritmo di Dijkstra: pseudocodice, discussione della complessità a seconda delle strutture dati usate. Simulazione di esecuzione. Esercizi proposti: Esercizio 14.1 - 14.2 - 14.5 - 14.7, [T1] pag. 402; Problema 14.2 - 14.4 - 14.5 - 14.6, [T1] pagg. 403/404; Esercizi 8.7 - 8.9 - 8.16 - 8.17 - 8.18 - 8.19 - 8.22 della dispensa Esercizi di Algoritmi e Strutture Dati.
09 mag 2013. Sezioni 14.3 - 14.6 - 14.6.1 - 14.6.2 del testo principale [T1]; Capitolo 12 degli Appunti e Lucidi 08. Consiglio anche la Sezione 25.1 di [T2]. Algoritmo di Bellman-Ford: descrizione, cenni sulla correttezza e analisi della complessità. Matrice di adiacenza pesata. Programmazione dinamica. Algoritmo di Floyd-Warshall. Struttura di un cammino minimo. Formula ricorsiva. Analisi della complessità. Algoritmo con spazio cubico e quadratico. Esercizi proposti: Esercizio 14.1 - 14.2 - 14.5 - 14.7, [T1] pag. 402. Problema 14.2 - 14.4 - 14.5 - 14.6, [T1] pagg. 403/404.

Prove di Esame

Top

mace@unive.it