Algoritmi e Strutture Dati [modulo A]   Anno Accademico 2009/2010   Corso per Studenti Part Time   Docente Dr. Damiano Macedonio   Dipartimento di Informatica   Università Ca’ Foscari di Venezia

Contenuti   (ultimo aggiornamento: 25 aprile 2011)

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

Comunicazioni

• Ricevimento: previo appuntamento via mail.
• Orario lezioni:
  • lunedì ore 18:00, Aula 2.
  • martedì ore 18:00, Aula 2.

Programma del Corso

• 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.
• 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 (Second Edition), MIT Press, 2001.
    Traduzione italiana a cura di Livio Colussi edita da McGraw-Hill, Milano, 2005.

Lezioni in Dettaglio

Top

• 25 ott 2010. Lucidi della lezione. Introduzione al corso.
• 02 nov 2010. Sezioni 1.1 - 1.2 - 1.3 del testo principale [T1]. Introduzione agli algoritmi. Numeri di Fibonacci: algoritmo numerico e algoritmo ricorsivo. Analisi dell'algoritmo ricorsivo con l'albero delle ricorrenze.
• 08 nov 2010. Sezioni 1.3 - 1.4 - 1.5 - 1.6 del testo principale [T1]. Numeri di fibonacci: algoritmo iterativo. Occupazione di memoria. Cenni sulla notazione asintotica.
• 15 nov 2010. Sezione 1.7 del testo principale [T1]. Numeri di fibonacci: algoritmo basato su potenze ricorsive. Analisi della complessità di algoritmi basati su potenze ricorsive. Problemi proposti: Problema 1.3, [T1] pag. 19.
• 16 nov 2010. Sezioni 2.1 - 2.2 del testo principale [T1]. Rapporto tra classi di complessità. Dipendenza delle prestazioni degli algoritmi dalla tecnologia. Modelli di calcolo. Criteri di costo uniforme e logaritmico. Notazione asintotica. Delimitazioni inferiori e superiori.
• 23 nov 2010. Sezioni 17.2 - 2.3 - 2.4 del testo principale [T1]. Delimitazioni inferiori e superiori Metodi di analisi. Ricerca sequenziale. Analisi della ricerca sequenziale nel caso migliore e nel caso pessimo. Esercizi proposti: Esercizio 2.1 - 2.2 - 2.5, [T1] pag. 55. Problema 2.1, [T1] pag. 57.
• 29 nov 2010. Sezioni 2.4.2 - 17.2.1 del testo principale [T1]. Serie aritmetica. Serie geometrica. Serie aritmetica-geometrica. Analisi degli algoritmi di Ricerca Sequenziale e Ricerca Binaria. Caso migliore, caso pessimo e caso medio.
• 30 nov 2010. Sezioni 2.4.2 - 2.5.1 - 2.5.2 del testo principale [T1]. Ricerca Binaria ricorsiva: analisi nel caso pessimo. Analisi di algoritmi ricorsivi: metodo di iterazione e di sostituzione. Esempi.
• 07 dic 2010. Sezioni 2.5.2 - 2.5.3 del testo principale [T1]. Analisi di algoritmi ricorsivi: metodo di sostituzione. Esempi. Analisi delle relazioni di ricorrenza derivate da algoritmi basati sulla tecnica "divide et impera".
• 14 dic 2010. Sezione 2.5.3 del testo principale [T1]. Teorema fondamentale delle ricorrenze: enunciato, dimostrazione e applicazioni. Esercizi proposti: Esercizio 2.6 - 2.7 - 2.9 - 2.11, [T1] pagg. 55/56. Problema 2.5 - 2.7 - 2.8 - 2.9 - 2.10, [T1] pagg. 57/58/59.
• 20 dic 2010. Sezioni 2.5.3 - 2.5.4 del testo principale [T1]. Esercizi. Applicazioni del teorema fondamentale. Analisi dell'albero della ricorsione. Cambiamenti di variabile.
• 21 dic 2010. Correzione e discussione degli esercizi proposti.
• 01 gen 2011. Sezioni 3.1.1 (fino pag. 66) - 3.1.2 - 3.2 - 3.3 del testo principale [T1]. Strutture dati elementari. Dizionari, implementati con array e liste. Pile e code. Alberi.
• 07 feb 2011. Sezioni 3.3.1 - 3.3.2 - 3.3.3 del testo principale [T1]. Alberi: rappresentazioni indicizzate, rappresentazioni collegate, visite in profondità (preordine, simmetrica, postordine), visita in ampiezza.
• 08 feb 2011. Capitolo 4, Sezione 4.2 del testo principale [T1]. Problema dell'ordinamento. Ordinamento in tempo quadratico: Insertion Sort, Selection Sort, Bubble Sort.
• 15 feb 2011. Capitolo 4, Sezione 4.1 del testo principale [T1]. Alberi di decisione. Limitazione inferiore del numero di confronti per algoritmi di ordinamento.
• 21 feb 2011. Capitolo 4, Sezione 4.4 del testo principale [T1]. Consiglio anche la Sezione 2.3.1 di [T2]. Mergesort: analisi, correttezza e complessità.
• 22 feb 2011. Capitolo 4, Sezione 4.3 del testo principale [T1]. Consiglio anche le Sezioni 6.1 - 6.2 - 6.3 - 6.4 di [T2]. Heap binari: definizione, altezza, numero di nodi interni e foglie. Heapsort: descrizione generale dell'algoritmo con esempio di esecuzione e procedura Heapify in dettaglio.
• 28 feb 2011. Capitolo 4, Sezione 4.3 del testo principale [T1]. Consiglio anche le Sezioni 6.1 - 6.2 - 6.3 - 6.4 di [T2]. Procedura BuildMaxHeap: descrizione, correttezza e complessità. Algoritmo HeapSort: correttezza, complessità, esempi di esecuzione.
• 01 mar 2011. Sezione 4.5 del testo principale [T1]. Consiglio anche le Sezioni 7.1 - 7.2 di [T2]. Quicksort: procedura Partition. Esempio di esecuzione. Correttezza. Complessità: analisi del caso peggiore e del caso migliore.
• 07 mar 2011. Sezione 4.5 del testo principale [T1]. Quicksort: analisi della complessità nel caso medio. Definizione di coda di priorità Esercizi proposti: Esercizio 4.4 - 4.7 - 4.12, [T1] pagg. 114/115. Problema 4.1 - 4.7 - 4.11 - 4.12 - 4.13, [T1] pagg. 115/116/117.
• 08 mar 2011. Sezione 6.5 di [T2]. Capitolo 5, Sezioni 5.1 - 5.1.1 del testo principale [T1]. Consiglio anche le Sezioni 9.1 - 9.2 di [T2]. Coda di priorità implementata da Heap binomiale. Statistiche d'ordine e problema della selezione. Ricerca del minimo. Ricerca del minimo e massimo simultaneamente. Ricerca del secondo minimo.
• 14 mar 2011. Sezione 6.5 di [T2]. Capitolo 5, Sezioni 5.1 - 5.1.1 - 5.1.2 - 5.2 (solo analisi del caso migliore e caso pessimo) del testo principale [T1]. Consiglio anche le Sezioni 9.1 - 9.2 di [T2]. Coda di priorità implementata da Heap binomiale. Statistiche d'ordine e problema della selezione. Ricerca del minimo. Ricerca del minimo e massimo simultaneamente. Ricerca del secondo minimo. Algoritmi HeapSelection e Quickselection.
• 15 mar 2011. Sezioni 5.3 - 6.1 del testo principale [T1]. Consiglio anche le Sezioni 9.3 - 12.1 - 12.2 di [T2]. Selezione in tempo lineare nel caso peggiore: tecnica della ''mediana delle mediane''. Alberi binari di ricerca: definizione, propietà, visita in ordine, ricerca di una chiave, ricerca del minimo/massimo, ricerca del predecessore/successore.
• 21 mar 2011. Sezioni 6.1 - 6.2.1 del testo principale [T1]. Consiglio anche la Sezione 12.3 di [T2]. Alberi binari di ricerca: inserimento e cancellazione. Alberi AVL: fattore di bilanciamento e definizione.
• 22 mar 2011. Sezione 6.2.1 - 6.2.2 - 6.2.3 del testo principale [T1]. Alberi AVL: altezza, ri-bilanciamento tramite rotazioni, ricerca, inserimento e cancellazione. Esercizi proposti: Esercizio 6.1 - 6.4 - 6.5 - 6.6, [T1] pagg. 174/175. Problema 6.1 - 6.2 - 6.3 - 6.4 - 6.6, [T1] pagg. 175/176.
• 28 mar 2011. Sezione 12.0 - 12.1 del testo principale [T1]. 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à.
• 29 mar 2010. Sezione 12.1 - 12.2 del testo principale [T1]. 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.
• 04 apr 2011. Sezione 12.3 del testo principale [T1]. Visite di grafi non orientati. Visita in ampiezza e in profondità. Proprietà della visita in ampiezza. Albero di copertura. Albero dei cammini minimi.
• 05 apr 2011. Sezioni 13.0 - 13.1 del testo principale [T1]. Consiglio anche le Sezioni 23.0 - 23.1 di [T2]. Grafi pesati. Alberi di copertura minimi: definizione, proprietà e teorema fondamentale.
• 11 apr 2011. Sezione 13.2 del testo principale [T1]. Consiglio anche la Sezione 23.2 di [T2]. Algoritmo di Kruskal: correttezza, complessità ed esempio di esecuzione. Cenni alla gestione di insiemi disgiunti.
• 12 apr 2010. Sezione 13.3 del testo principale [T1]. Consiglio anche la Sezione 23.2 di [T2]. Algoritmo di Prim: correttezza, complessità ed esempio di esecuzione. Esercizi proposti: Esercizio 13.2 - 13.3 - 13.4 - 13.5 - 13.8, [T1] pagg. 174/175. Problema 13.1 - 13.2 - 13.3 - 13.4, [T1] pagg. 375/376.
• 18 apr 2011. Sezione 14.1 del testo principale [T1]. 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à.
• 19 apr 2011. Sezioni 14.2 - 14.5 del testo principale [T1]. Consiglio anche le Sezioni 24.4 - 24-6 di [T2]. Cammini minimi da sorgente unica. Procedura di inizializzazione e di rilassamento: principali proprietà. Algoritmo di Dijkstra: pseudocodice e discussione della complessità a seconda delle strutture dati usate.
• 02 mag 2011. Sezione 14.3 del testo principale [T1]. Consiglio anche la Sezione 24.2 di [T2]. Algoritmo di Dijkstra: dimostrazione della correttezza e simulazione di esecuzione. Discussione del comportamento dell'algoritmo di Dijkstra in caso di pesi negativi. Algoritmo di Bellman-Ford: pseudocodice, cenni sulla correttezza e analisi della complessià.
• 03 mag 2011. Sezioni 14.3 - 14.6 - 14.6.1 - 14.6.2 del testo principale [T1]. 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.

Prove di Esame

Top

• ...

mace@dsi.unive.it