Algoritmi e Strutture Dati [modulo A]   Anno Accademico 2011/2011   Corso di Laurea in Informatica   Docenti Dr. Damiano Macedonio   Dipartimento di Informatica   Università Ca’ Foscari di Venezia

Contenuti   (ultimo aggiornamento: 01 aprile 2011)

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

Comunicazioni

• Esito degli elaborati di laboratorio.
• Ricevimento: su appuntamento, via e-mail.
• Orario lezioni:
  • lunedì ore 14:00, aula 2.
  • martedì ore 15:45, aula 2.
  • venerdì ore 14:00, aula 2 [Dott. Nicola Rebagliati].
• Alcuni siti di interesse per il corso:
  • Corso di Algoritmi e Strutture Dati, prof. Alberto Montresor, Università di Trento.
  • Corso di Algoritmi e Strutture Dati, prof. Giuseppe F. Italiano, Università di Roma Tor Vergata.
  • Corso di Algoritmi e Strutture Dati, prof. Moreno Marzolla, Università di Bologna.

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 set 2010. Lucidi della lezione. Introduzione al corso.
• 21 set 2010. Sezioni 1.1 - 1.2 - 1.3 - 1.4 del testo principale [T1]. Introduzione agli algoritmi. Numeri di Fibonacci: algoritmo numerico, algoritmo ricorsivo, algoritmo iterativo.
• 24 set 2010. Sezioni 1.4 - 1.5 - 1.6 - 1.7 del testo principale [T1]. Numeri di fibonacci: analisi dell'algoritmo iterativo e suo miglioramento. Occupazione di memoria. Cenni sulla notazione asintotica. Calcolo dei numeri di Fibonacci con potenza di matrici.
• 27 set 2010. Sezione 1.7 del testo principale [T1]. Analisi del'algoritmo per il calcolo dei numeri di Fibonacci basato su potenze ricorsive. Confronto tra classi di complessità. Problemi proposti: Problema 1.3, [T1] pag. 19.
• 28 set 2009. Sezioni 2.1 - 2.2 - del testo principale [T1]. Modelli di calcolo. Criteri di costo uniforme e logaritmico. Notazione asintotica. Esercizi proposti: Esercizio 2.1 - 2.2 - 2.5, [T1] pag. 55. Problema 2.1, 2.2, 2.3 [T1] pag. 57.
• 01 ott 2010. Sezioni 2.3 - 2.4 del testo principale [T1]. Delimitazioni inferiori e superiori. Metodi di analisi. Ricerca sequenziale. Analisi degli algoritmi di Ricerca Sequenziale e Ricerca Binaria.
• 04 ott 2010. Sezioni 2.5.1 - 17.2 del testo principale [T1]. Richiami: serie aritmetica, serie geometrica e serie aritmetica-geometrica. Analisi di algoritmi ricorsivi: metodo di iterazione. Esempi.
• 05 ott 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".
• 08 ott 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.
• 11 ott 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.
• 12 ott 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. Alberi liberi e loro principali proprietà.
• 18 ott 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. Visita di grafi.
• 19 ott 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. Grafi pesati. Alberi di copertura minimi.
• 25 ott 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à, tecnica del ''taglia e cuci'', teorema fondamentale e suo corollario.
• 26 ott 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.
• 02 nov 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, [T1] pagg. 175/176.
• 15 nov 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à.
• 16 nov 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.
• 22 nov 2010. Sezione 14.3 del testo principale [T1]. Consiglio anche la Sezione 24.2 di [T2]. Algoritmo di Dijkstra: 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: idee generali.
• 23 nov 2010. Sezione 14.3 - del testo principale [T1]. Consiglio anche la Sezione 25.1 di [T2]. Algoritmo di Bellman-Ford: pseudocodice, analisi della complessià e correttezza. Simulazione di esecuzione. Confronto con algoritmo di Dijkstra. Introduzione al problema dei cammini minimi tra tutte le coppie. Risoluzione del problema iterando gli algoritmi per cammini minimi da sorgente unica, analisi delle complessià.
• 29 nov 2010. Sezione 25.2 di [T2]. Matrice di adiacenza pesata. Cammini minimi e moltiplicazione di matrici. Metodo dei quadrati ripetuti.
• 30 nov 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. 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.
• 14 dic 2010. Sezioni 10.2-10.3-11.3 del testo principale [T1]. Consiglio anche la Sezione 16.2 di [T2]. Paradigmi di programmazione: tecnica greedy e programmazione dinamica. Descrizione generale. Esempio: problema dello zaino sia frazionario che 0-1.

Prove di Esame

Top

• Esito degli elaborati di laboratorio.
• Prova di Analisi e Progettazione di Algoritmi del 29 marzo 2011: risultati
• Prova del 18 gennaio 2011: Parte I, Parte II. [Risultati]
  Orali: martedì 25 gennaio 2011 ore 9:30, Aula 1.
  Visione compiti: martedì 25 gennaio 2011 ore 9:30, Aula 1.
  Correzione (parti I e II): lunedì 31 gennaio 2011 ore 14:00, Aula 2.
• Prova di Analisi e Progettazione di Algoritmi del 18 gennaio 2011: testo. [Risultati]

mace@dsi.unive.it