Lezioni del Modulo di Algoritmi e Strutture Dati 2009/10

 

19/10/09: Introduzione. Problemi, algoritmi e programmi. Un problema esemplificativo: la sequenza di Fibonacci. Primi 2 algoritmi per determinare l’n-esimo numero della sequenza di Fibonacci. Complessità degli algoritmi come numero di linee di codice.

Dispense: Clicca qui.

 

21/10/09: Algoritmi lineari in n per determinare l'n-esimo numero della sequenza di Fibonacci. Primi accenni alla complessità asintotica: notazione O(). Algoritmo basato sulle potenze ricorsive. Dimostrazione dell’identità di base col metodo induttivo. Algoritmo sulle potenze ricorsive: versione iterativa e ricorsiva. Analisi della complessità. Confronto tra i 6 algoritmi proposti.

Dispense: Clicca qui.

 

26/10/09: Definizione formale di complessità asintotica: notazioni O,Ω,Θ,o,ω. Esempi. Analisi di un algoritmo: caso peggiore, migliore e medio. Complessità di un algoritmo e complessità di un problema. Esempio: ricerca di un elemento in una lista non ordinata.

Dispense: Clicca qui.

 

28/10/09: Il problema della ricerca: ricerca esaustiva e ricerca binaria. Analisi della complessità temporale nel caso migliore, peggiore e medio. Soluzione di equazioni di ricorrenza: metodo della ricorsione, della sostituzione e teorema principale. Esempi.

Dispense: Clicca qui.

 

2/11/09: Il problema dell’ordinamento. SELECTION SORT e  INSERTION SORT: analisi della complessità temporale nel caso migliore, peggiore e medio. Analisi della complessità spaziale.

Dispense: Clicca qui.

 

4/11/09: Lower bound per il problema dell’ordinamento basato sull’albero di decisione. Algoritmo ottimale per la fusione ordinata di 2 sequenze ordinate. Algoritmo MERGE SORT. Analisi della complessità temporale.

Dispense: Clicca qui.

 

9/11/09: Code di priorità: l’heap binario. Algoritmo HEAP SORT. Procedure di creazione e di mantenimento dell’heap. Analisi della complessità temporale di HEAP SORT. Esempi.

Dispense: Clicca qui.

 

11/11/09: Algoritmo QUICKSORT. Partizionamento in loco. Analisi del caso peggiore. Analisi del caso medio. Algoritmi di ordinamento lineari: INTEGER SORT, BUCKET SORT, RADIX SORT.

Dispense: Clicca qui.

 

16/11/09: Code di priorità. Implementazioni elementari con liste e array ordinati e non ordinati. l’heap d-ario. Analisi delle operazioni di ricerca del minimo, inserimento, cancellazione, cancellazione del minimo, incremento di una chiave, decremento di una chiave, fusione.

Dispense: Clicca qui.

 

18/11/09: Heap binomiale: struttura e proprietà. Analisi delle operazioni di ricerca del minimo, inserimento, cancellazione, cancellazione del minimo, incremento di una chiave, decremento di una chiave, fusione. Esempi. Cenni sugli heap di Fibonacci.

Dispense: Clicca qui.

 

23/11/09: Il problema del dizionario. Risoluzione tramite array non ordinato, array ordinato, lista non ordinata, lista ordinata. Delimitazione inferiore al problema della ricerca in un insieme ordinata e non ordinato. Alberi binari di ricerca. Visita in ordine simmetrico. Esempi.

Dispense: Clicca qui.

 

30/11/09: Alberi binari di ricerca: minimo, massimo, predecessore, successore, ricerca, inserimento e cancellazione. Alberi binari di ricerca bilanciati. Alberi AVL.

Dispense: Clicca qui.

 

2/12/09: Alberi AVL: rotazione di base. Rotazione sinistro-sinistro e sinistro-destro. Inserimento e cancellazione di un elemento in un albero AVL. Cancellazioni a cascata in un albero AVL.

Dispense: Clicca qui.

 

7/12/09: Esercizi di preparazione alla prova intermedia.

 

9/12/09: Prova intermedia.

 

16/12/09: Tabelle ad indirizzamento diretto. Fattore di carico. Tabelle hash. Hashing perfetto. Hashing non perfetto. Uniformità semplice di una funzione hash. Gestione delle collisioni: liste di trabocco ed indirizzamento aperto. Metodi di scansione: scansione lineare ed hashing doppio.

Dispense: Clicca qui.

 

21/12/09: Tecniche algoritmiche. Richiami sul metodo divide et impera. Programmazione dinamica: distanza tra 2 stringhe. Metodo goloso: il problema del sequenziamento e il problema della minimizzazione del resto.

Dispense: Clicca qui.

 

4/1/10: Correzione prova intermedia.

 

11/1/10: Grafi: definizioni fondamentali. Rappresentazioni in memoria: lista di archi, lista di adiacenza, matrice di adiacenza. Prestazioni temporali sulle operazioni fondamentali dipendentemente dalla rappresentazione in memoria utilizzata.

Dispense: Clicca qui.

 

13/1/10: Visita di un grafo. Paradigma di visita generica. Visita in ampiezza di un grafo diretto/non diretto. Proprietà dell’albero BFS. Visita in profondità di un grafo diretto/non diretto. Proprietà dell’albero DFS. Approfondimento: trasformazione da rappresentazione tramite matrice di adiacenza a liste di adiacenza.

Dispense: Clicca qui.

 

18/1/10: Il problema del cammino minimo tra due nodi in un grafo pesato. Definizioni e proprietà fondamentali dei cammini minimi. Tecnica del rilassamento. Albero dei cammini minimi. Algoritmo basato sull’ordinamento topologico per il problema dell'albero dei cammini minimi in un grafo pesato aciclico. Algoritmo di Bellman e Ford per il problema dell'albero dei cammini minimi in un grafo pesato senza cicli negativi. Esempi.

Dispense: Clicca qui.

 

20/1/10: Algoritmo di Dijkstra per il problema dell'albero dei cammini minimi a sorgente singola in un grafo pesato con pesi non negativi. Esempi. Algoritmo di Floyd e Warshall per il problema del cammino minimo tra tutte le coppie di nodi di un grafo pesato senza cicli negativi.

Dispense: Clicca qui.

 

25/1/10: Il problema della gestione di insiemi disgiunti (Union-find). Definizione delle operazioni di creazione di un insieme, unione di 2 insiemi e ricerca del nome di un insieme associato ad un elemento. Approcci elementari al problema della gestione di insiemi disgiunti: alberi Quick-Find ed alberi Quick-union. Casi migliori e casi peggiori. Euristiche di bilanciamento per dimensione ed altezza degli alberi, e relativa analisi.

Dispense: Clicca qui.

 

27/1/10: Il problema del minimo albero ricoprente. Definizioni preliminari: tagli e cicli. Regola del taglio e regola del ciclo. Strategia golosa per la determinazione del minimo albero ricoprente. Algoritmo di Kruskal. Esempio di esecuzione dell'algoritmo di Kruskal. Analisi della complessità: casistica in base al metodo utilizzato per risolvere il problema Union-Find soggiacente.

Dispense: Clicca qui.

 

1/2/10: Algoritmo di Prim. Analisi della complessità. Algoritmo di Borůvka e cenni sull'analisi di complessità.

Dispense: Clicca qui.

 

3/2/10: Approfondimento: Esecuzione degli algoritmi di Kruskal, Prim e Borůvka. Analisi dettagliata della complessità dell’algoritmo di Borůvka.