Lezioni del Modulo di
Algoritmi e Strutture Dati 2010/11
11/10/10:
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.
13/10/10:
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.
18/10/10:
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.
20/10/10:
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.
25/10/10: 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.
27/10/10: Lower
bound per il problema dell’ordinamento basato
sull’albero di decisione.
Dispense: Clicca qui.
3/11/10: 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.
8/11/10: 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.
10/11/10: 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.
15/11/10: 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.
17/11/10: 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.
24/11/10:
Prova intermedia.
29/11/10: Correzione della prova
intermedia.
1/12/10: Alberi binari di ricerca: minimo,
massimo, predecessore, successore, ricerca, inserimento e cancellazione.
Dispense: Clicca qui.
6/12/10: 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.
20/12/10: 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.
22/12/10: 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.
10/1/11 (3 ore): 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. Visita di un grafo. Paradigma di visita generica.
Dispense: Clicca qui e qui.
12/1/11
(3 ore): 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.
17/1/11:
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.
19/1/11:
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.
24/1/11: 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.
26/1/11: Algoritmo di Prim e analisi della complessità. Algoritmo di Borůvka e analisi della complessità.
Dispense: Clicca qui.