Algoritmi e Strutture Dati [moduli 1 e 2 - 12 CFU]   Anno Accademico 2012/2013   Corso per Studenti Part Time   Docente Dr. Damiano Macedonio   Dipartimento di Scienze Ambientali, Informatica e Statistica   Università Ca’ Foscari di Venezia

Contenuti   (ultimo aggiornamento: 16 maggio 2013)

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

Comunicazioni

• Le lezioni sono terminate.
• Prossimi appuntamenti:
  • sabato 22 giugno 2013 ore 10.00: ricevimento generale.
  • giovedì 18 luglio 2013 ore 9.30: esercitazione finale.
• Ricevimento: al sabato prima, della lezione. Previo appuntamento via mail.
• Orario lezioni:
  • sabato ore 9:30-12:45 Aula 2.
• 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) dello scorso anno.
    • 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] 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 20 ottobre 2012: introduzione informale agli algoritmi.
  • Capitolo 02. Traccia delle lezioni del 03-10 novembre 2012: metodologie di analisi.
  • Capitolo 03. Traccia della lezioni del 10 novembre 2012: correttezza degli algoritmi.
  • Capitolo 04. Integrazione delle lezioni del 10-17 novembre 2012: pile, code e alberi.
  • Capitolo 05. Integrazione delle lezioni del 24 novembre - 01 dicembre 2012: alberi binari di ricerca.
  • Capitolo 06. Integrazione facoltativa della lezione del 22 dicembre 2012: heap binari e code di priorità.
  • Capitolo 07. Integrazione facoltativa delle lezioni del 15-22 dicembre 2012: algoritmi di ordinamento;.
  • Capitolo 08. Integrazione su tabelle hash.
  • Capitolo 09. Traccia della lezione del 23 febbraio 2013. (Attenzione: rispetto alla versione del 1 marzo ho modificato l'enunciato delle Proprietà 9.2 e 9.3.)
  • Capitolo 10. Traccia delle lezioni del 9-22 marzo 2013.
  • Capitolo 11. Traccia delle lezioni del 6-20 aprile 2013. (Attenzione: la dimostrazione del Teorema 11.2 non fa parte del programma di esame.)
  • Capitolo 12. Traccia della lezione del 4 maggio 2013.
• Presentazioni
  • Lucidi 01. Lezione del 27 ottobre 2012: tecniche di analisi degli algoritmi.
  • Lucidi 02. Integrazione delle Lezioni del 10-17 novembre 2012: strutture dati elementari.
  • Lucidi 03. Integrazione della Lezione del 24 novembre 2012: Alberi Binari di Ricerca.
  • Lucidi 04. Integrazione della Lezione del 01 dicembre 2012: Alberi AVL.
  • Lucidi 05. Traccia delle Lezioni del 15-22 dicembre 2012: Algoritmi di Ordinamento.
  • Lucidi 06. Traccia della lezione del 16 febbraio 2013.
  • Lucidi 07. Traccia della lezione del 02 marzo 2013.
  • Lucidi 07. Traccia della lezione del 11 maggio 2013.
  • Lucidi 07. Traccia della lezione del 11 maggio 2013.
  • Lucidi 07. Teoria della NP-completezza, cenni.

Lezioni in Dettaglio

Top

• 20 ott 2012. Introduzione al corso [pdf].
• 20 ott 2012. Riferimenti: Capitolo 1 del testo principale [T1]; Capitolo 1 degli Appunti. Introduzione agli algoritmi. Numeri di Fibonacci: algoritmo numerico, algoritmo ricorsivo, algoritmo iterativo e algoritmo basato su potenze ricorsive. Analisi di algoritmi ricorsivi con albero delle ricorrenze. Occupazione di memoria. 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].
• 27 ott 2012. 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à. 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].
• 03 nov 2012. 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: enunciato, dimostrazione e applicazioni. Esercizi proposti: Esercizi 2.6 - 2.7 - 2.9 - 2.11; Problemi 2.5 - 2.8 - 2.9 - 2.10, [T1] pagg. 57/58/59.
• 10 nov 2012. Riferimenti: Capitolo 2, sezione 2.5; Capitolo 3, sezioni 3.1 - 3.2 del testo principale [T1]; Capitolo 2, Capitolo 3 eCapitolo 4 degli Appunti; Lucidi della lezione. Esempi di analisi di algoritmi e applicazione del teorema fondamentale. Relazioni di ricorrenza non risolvibili con il teorema fondamentale: analisi dell'albero della ricorsione, cambiamenti di variabile. Correttezza degli algoritmi. Strutture dati indicizzare e collegate. Tecnica del raddoppiamento-dimezzamento (cenni). Pile e code. Esercizi proposti: Esercizi 2.1 - 2.2 - 2.5; Problemi 1.3 - 2.1 - 2.2 - 2.3 del testo principale [T1], Capitolo 1 della dispensa Esercizi di Algoritmi e Strutture Dati.
• 17 nov 2012. Riferimenti: Capitolo 3, Sezione 3.3 del testo principale [T1]. 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 della dispensa Esercizi di Algoritmi e Strutture Dati.
• 24 nov 2012. Riferimenti: Capitolo 6, Sezione 6.1 del testo principale [T1]; consiglio anche le Sezioni 12.1 - 12.2 - 12.3 di [T2]; Lucidi della lezione. Alberi binari di ricerca: definizione, propietà, visita in ordine, ricerca di una chiave, ricerca del minimo/massimo, ricerca del predecessore/successore, inserimento e cancellazione. 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.
• 01 dic 2012. Riferimenti: Capitolo 6, Sezione 6.2 - 6.2.1 - 6.2.2 - 6.2.3 - del testo principale [T1]; Lucidi della lezione. Alberi AVL: fattore di bilanciamento e definizione,altezza, ri-bilanciamento tramite rotazioni, ricerca, inserimento e cancellazione. Esercizi proposti: Esercizi 6.4 - 6.5 - 6.6; Problema 6.2 - 6.3 - 6.4 - 6.6 del testo principale [T1].
• 15 dic 2012. Riferimenti: Capitolo 4, Sezione 4.2 - 4.2.1 - 4.2.2 - 4.4 - 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. Merge Sort: analisi, correttezza e complessità. Un link interessante: Sorting Algorithm Animations. Esercizi proposti: Esercizi 4.2 - 4.12 ; Problema 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.
• 22 dic 2012. Riferimenti: Capitolo 4, Sezione 4.1 - 4.1.1 - 4.1.2 - 4.3 - 4.3.1 - 4.3.2 - 4.6 - 4.7 del testo principale [T1]; Lucidi della lezione. Heap binari: definizione, altezza, numero di nodi interni e foglie. Struttura MaxHeap. Procedure fixHeap e heapify: descrizione, correttezza e complessità. Algoritmo Heap Sort: correttezza, complessità, esempi di esecuzione. Cenni alla coda con priorità implementata da Heap binomiale (consiglio le Sezioni 7.1 - 7.2 di [T2]. ). Alberi di decisione. Limitazione inferiore del numero di confronti per algoritmi di ordinamento. Cenni alle tecniche lineari di ordinamento: Counting Sort, Bucket Sort, Radix Sort. Esercizi proposti: Esercizi 4.1 - 4.2 - 4.5 - 4.3 - 4.7 - 4.10 - 4.14; 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.
• 16 feb 2013. Capitolo 7 del testo principale [T1]; Lucidi della lezione. 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.
• 23 feb 2013. 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à.
• 02 mar 2013. 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.
• 09 mar 2013. 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.
• 16 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. Cenni alla gestione di insiemi disgiunti.
• 22 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 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.
• 06 apr 2013. Sezione 14.1 del testo principale [T1]; Capitolo 11 degli Appunti. Consiglio anche la Sezione 24.1 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à. Cammini minimi da sorgente unica.
• 13 apr 2013. Sezioni 14.2- 14.3 - 14.5 del testo principale [T1]; Capitolo 11 degli Appunti. Consiglio anche le Sezioni 24.2 - 24.4 - 24-6 di [T2]. Procedura di inizializzazione e di rilassamento: principali proprietà. Algoritmo di Dijkstra: pseudocodice, discussione della complessità a seconda delle strutture dati usate. Simulazione di esecuzione.
• 20 apr 2013. Sezioni 14.2- 14.3 - 14.5 del testo principale [T1]; Capitolo 11 degli Appunti. Consiglio anche le Sezioni 24.2 - 24.4 - 24-6 di [T2]. Algoritmo di Dijkstra: dimostrazione della correttezza. Discussione del comportamento dell'algoritmo di Dijkstra in caso di pesi negativi. Algoritmo di Bellman-Ford: descrizione, cenni sulla correttezza e analisi della complessià. 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.
• 04 mag 2013. Sezioni 14.3 - 14.6 - 14.6.1 - 14.6.2 del testo principale [T1]; Capitolo 12 degli Appunti. Consiglio anche la Sezione 25.1 di [T2]. Problema dei cammini minimi tra tutte le coppie. Risoluzione del problema iterando gli algoritmi per cammini da sorgente unica, analisi della complessià. Matrice di adiacenza pesata. Cammini minimi e moltiplicazione di matrici. Algoritmo di Floyd-Warshall. Struttura di un cammino minimo. Formula ricorsiva. 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.
• 11 mag 2013. Sezioni 14.3 - 14.6 - 14.6.1 - 14.6.2 del testo principale [T1]; Lucidi ed Esempi della lezione. Consiglio anche la Sezione 25.1 di [T2]. Paradigmi di programmazione: divide-et-impera, programmazione dinamica e tecnica greedy. Discussione ed esempi.

Prove di Esame

Top

• A.A. 2010/2011
• Esame(12-01-13) del vecchio corso da 9 crediti.
• ...

mace@unive.it