Algoritmi e Strutture Dati [parti I e II]

  Algoritmi e Strutture Dati [parti I e II - 9 CFU]
  Anno Accademico 2011/2012
  Corso per Studenti Part Time

  Docente Dr. Damiano Macedonio
  Dipartimento di Informatica
  Università Ca’ Foscari di Venezia

Contenuti (ultimo aggiornamento: 27 aprile 2012)

Comunicazioni
Programma del Corso
Lezioni in Dettaglio
Prove di Esame

Comunicazioni

Ricevimento: sabato prima della lezione, previo appuntamento via mail.
Orario lezioni:
- sabato ore 10:30-13:45 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

08 ott 2011. Introduzione al corso [lucidi ].
08 ott 2011. 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.
15 ott 2011. Sezioni 1.3 - 1.4 - 1.5 - 1.6 - 1.7 del testo principale [T1]. Numeri di fibonacci: algoritmo iterativo e algoritmo basato su potenze ricorsive. Occupazione di memoria. Cenni sulla notazione asintotica.
22 ott 2010. Sezione 1.7 - 2.1 - 2.2 del testo principale [T1]. Analisi della complessità di algoritmi basati su potenze ricorsive. Modelli di calcolo. Criteri di costo uniforme e logaritmico. Notazione asintotica. Delimitazioni inferiori e superiori. Rapporto tra classi di complessità. Dipendenza delle prestazioni degli algoritmi dalla tecnologia. Problemi proposti: 1.3, [T1] pag. 19. e 2.1, [T1] pag. 57. Esercizi proposti: 2.1 - 2.2 - 2.5, [T1] pag. 55.
29 ott 2010. Sezioni 17.2 - 2.3 - 2.4 - 17.2.1 del testo principale [T1]. Delimitazioni inferiori e superiori Metodi di analisi. Ricerca sequenziale. Analisi della ricerca sequenziale nel caso migliore e nel caso pessimo. Serie aritmetica. Serie geometrica. Serie aritmetica-geometrica. Analisi degli algoritmi di Ricerca Sequenziale e Ricerca Binaria. Caso migliore, caso pessimo e caso medio.
05 nov 2010. Sezioni 2.4.2 - 2.5.1 - 2.5.2 - 2.5.3 del testo principale [T1]. Ricerca Binaria ricorsiva: analisi nel caso pessimo. Analisi di algoritmi ricorsivi: metodo di iterazione e di sostituzione. Esempi. Analisi di algoritmi ricorsivi: metodo di sostituzione. Esempi. Introduzione delle relazioni di ricorrenza derivate da algoritmi basati sulla tecnica "divide et impera".
12 nov 2010. Sezione 2.5.3 del testo principale [T1]. Analisi delle relazioni di ricorrenza derivate da algoritmi basati sulla tecnica "divide et impera". 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.
19 nov 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.
26 nov 2010. Correzione e discussione degli esercizi proposti.
03 dic 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.
10 dic 2011. Sezioni 3.3.1 - 3.3.2 - 3.3.3 del testo principale [T1]. Alberi: definizione, rappresentazioni indicizzate, rappresentazioni collegate, visite.
17 dic 2011. Sezioni 3.3.1 - 3.3.2 - 3.3.3 del testo principale [T1]. Alberi: visite in profondità (preordine, simmetrica, postordine), visita in ampiezza. Esercizi proposti: Esercizio 3.4 - 3.5, [T1] pag. 80. Problema 3.3 - 3.6 - 3.7, [T1] pag. 81.
24 dic 2011. Discussione degli esercizi assegnati.
28 gen 2012. Capitolo 4, Sezione 4.2 del testo principale [T1]. Problema dell'ordinamento. Ordinamento in tempo quadratico: Insertion Sort, Selection Sort, Bubble Sort.
04 feb 2012. Capitolo 4, Sezioni 4.1 - 4.4 del testo principale [T1]. Consiglio anche la Sezione 2.3.1 di [T2]. Alberi di decisione. Limitazione inferiore del numero di confronti per algoritmi di ordinamento. Mergesort: analisi, correttezza e complessità.
11 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. Procedura BuildMaxHeap: descrizione, correttezza e complessità. Algoritmo HeapSort: correttezza, complessità, esempi di esecuzione.
18 feb 2012. Sezione 6.5 di [T2]. Sezione 4.5 del testo principale [T1]. Consiglio anche le Sezioni 7.1 - 7.2 di [T2]. Coda di priorità implementata da Heap binomiale. Procedura Partition per Quicksort: esempio di esecuzione, correttezza (con invarianti) e complessità. Algoritmo Quicksort: correttezza e complessità con analisi del caso peggiore, del caso migliore, del caso bilanciato 9-a-1 e cenni al caso medio. 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.
25 feb 2012. Capitolo 5, Sezioni Sezioni 5.1 - 5.1.1 - 5.1.2 - 5.2 (solo analisi del caso migliore e caso pessimo) - 5.3 del testo principale [T1]. Consiglio anche le Sezioni 9.1 - 9.2 - 9.3 di [T2]. Statistiche d'ordine e problema della selezione. Ricerca del minimo. Ricerca del minimo e massimo simultaneamente. Ricerca del secondo minimo. Algoritmi HeapSelection e Quickselection. Selezione in tempo lineare nel caso peggiore: tecnica della ''mediana delle mediane''.
03 mar 2012. Sezione 6.1 del testo principale [T1]. Consiglio anche le Sezioni 12.1 - 12.2 - 12.3 di [T2]. . Alberi binari di ricerca: definizione, propietà, visita in ordine, ricerca di una chiave, ricerca del minimo/massimo, ricerca del predecessore/successore, inserimento e cancellazione.
10 mar 2012. Sezioni 6.2.1 - 6.2.2 - 6.2.3 del testo principale [T1]. Alberi AVL: fattore di bilanciamento e definizione,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.
17 mar 2012. 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à.
24 mar 2012. 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.
31 mar 2012. 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.
14 apr 2012. 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.
21 apr 2012. Sezioni 13.2 - 13.3 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. 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.
05 mag 2012. 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à. Cammini minimi da sorgente unica.
12 mag 2012. Sezioni 14.2- 14.3 - 14.5 del testo principale [T1]. 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, dimostrazione della correttezza e simulazione di esecuzione. 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.
19 mag 2012. 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

A.A. 2010/2011
...

mace@dsi.unive.it