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.
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.
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.
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.
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.