Algoritmi e Strutture Dati [modulo A]

  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: 24 maggio 2010)

Comunicazioni
Programma del Corso
Lezioni in Dettaglio
Prove di Esame

Comunicazioni

Attenzione: Le lezioni di martedì 27 aprile e di giovedì 29 sono sospese.
Ricevimento: previo appuntamento via e-mail.
Orario lezioni:
- martedì ore 18:00, aula 2.
- giovedì 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

20 ott 2009. Sezioni 1.1 - 1.2 - 1.3 del testo principale [T1]. Introduzione agli algoritmi. Numeri di Fibonacci: algoritmo numerico e algoritmo ricorsivo.
22 ott 2009. Sezioni 1.3 - 1.4 - 1.5 - 1.6 - 1.7 del testo principale [T1]. Numeri di fibonacci: analisi dell'algoritmo ricorsivo, algoritmo iterativo, algoritmo basato su potenze ricorsive. Occupazione di memoria. Cenni sulla notazione asintotica.
27 ott 2009. Sezioni 1.7 - 2.1 del testo principale [T1]. Analisi della complessità di algoritmi basati su potenze ricorsive. Modelli di calcolo. Problemi proposti: Problema 1.3, [T1] pag. 19.
29 ott 2009. Sezioni 2.1 - 2.2 - 2.3 - 2.4 del testo principale [T1]. Criteri di costo uniforme e logaritmico. Notazione asintotica. Delimitazioni inferiori e superiori. Metodi di analisi. Ricerca sequenziale. Esercizi proposti: Esercizio 2.1 - 2.2 - 2.5, [T1] pag. 55. Problema 2.1, [T1] pag. 57.
03 nov 2009. Sezioni 17.2 - 2.4 del testo principale [T1]. Serie aritmetica. Serie geometrica. Serie aritmetica-geometrica. Analisi degli algoritmi di Ricerca Sequenziale e Ricerca Binaria.
05 nov 2009. Sezioni 2.5.1 - 2.5.2 del testo principale [T1]. Analisi di algoritmi ricorsivi: metodo di iterazione e di sostituzione. Esempi.
10 nov 2009. 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.
12 nov 2009. 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.
17 nov 2009. Esercitazione. Problemi 2.1 - 2.5 del testo principale [T1].
19 nov 2009. 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.
24 nov 2009. Esercitazione. Problema 3.6 del testo principale [T1].
26 nov 2009. Capitolo 4, Sezioni 4.1 - 4.2 del testo principale [T1]. Problema dell'ordinamento. Limitazione inferiore del numero di confronti. Insertion Sort. Selection Sort. Bubble Sort.
01 dic 2009. Capitolo 4, Sezioni 4.3.1 - 4.4 del testo principale [T1]. Consiglio anche la Sezione 2.3.1 di [T2]. Mergesort: analisi, correttezza e complessità. Heap binari.
03 dic 2009. Capitolo 4, Sezioni 4.3 (tutta) del testo principale [T1]. Consiglio anche le Sezioni 6.1 - 6.2 - 6.3 - 6.4 di [T2]. Heapsort: procedure Heapify e BuildMaxHeap. Algoritmo HeapSort: correttezza, complessità, esempi di esecuzione.
10 dic 2009. 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, intuizioni per il 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.
15 dic 2009. 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.
17 dic 2009. 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.
23 feb 2010. 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.
25 feb 2010. 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.
02 mar 2010. Esercitazione. Esercizi 4.7 - 4.12; problemi 4.1 - 4.7 - 4.12 - 4.13 del testo principale [T1].
04 mar 2010. Capitolo 7 del testo principale [T1]. 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 [lucidi della lezione].
09 mar 2010. Esercitazione. Esercizi 6.1 - 6.4; problemi 6.1 - 6.2 - 6.3 del testo principale [T1].
11 mar 2010. 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à.
16 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. Potenza della matrice di adianceza.
18 mar 2010. 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.
23 mar 2010. 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.
25 mar 2010. 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.
30 mar 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.
08 apr 2010. 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à.
13 apr 2010. 08 apr 2010. 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.
15 apr 2010. 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 e analisi della complessià.
20 apr 2010. Sezione 14.3 - del testo principale [T1]. Consiglio anche la Sezione 25.1 di [T2]. Algoritmo di Bellman-Ford: correttezza e simulazione di esecuzione. Introduzione al problema dei cammini minimi tra tutte le coppie. Risoluzione del problema iterando gli algoritmi per cammini da sorgente unica, analisi della complessià.
22 apr 2010. Sezione 25.2 di [T2]. Matrice di adiacenza pesata. Cammini minimi e moltiplicazione di matrici.
04 mag 2010. Sezioni 14.6 - 14.6.1 - 14.6.2 del testo principale [T1]. Consiglio anche la Sezione 25.1 di [T2]. 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.
06 mag 2010. Sezioni 10.3 - 10.3.2 Paradigmi di programmazione: tecnica greedy. Descrizione generale. Esempio: ricoprimento di punti con intervalli.
11 mag 2010. Sezioni 10.2 - 11.3 del testo principale [T1]. Consiglio anche la Sezione 16.2 di [T2]. Paradigmi di programmazione: programmazione dinamica. Descrizione generale. Esempi: problema dello zaino (sia 0-1 che frazionario), problema della massima sotto-sequenza comune.
18 mag 2010. Ricevimento generale.
25 mag 2010. Ricevimento generale.

Prove di Esame

Top

mace@dsi.unive.it