Lezioni del Modulo di
Algoritmi e Strutture Dati 2008/09
30/09/08:
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.
2/10/08:
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.
7/10/08:
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.
9/10/08:
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.
14/10/08: 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.
16/10/08: Lower
bound per il problema dell’ordinamento basato
sull’albero di decisione.
Dispense: Clicca qui.
21/10/08: 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.
23/10/08: 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.
28/10/08: 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.
30/10/08: 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.
4/11/08: 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.
6/11/08: Alberi binari di ricerca:
minimo, massimo, predecessore, successore, ricerca, inserimento e cancellazione.
Dispense: Clicca qui.
11/11/08: 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.
13/11/08: 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.
18/11/08: 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.
2/12/08: 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.
4/12/08: Visita di un grafo. Paradigma
di visita generica.
Dispense: Clicca qui.
9/12/08:
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.
11/12/08: 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.
8/1/09: 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.
13/1/09: 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.
15/1/09: Algoritmo di Prim.
Analisi della complessità. Algoritmo di Boruvka e
cenni sull'analisi di complessità.
Dispense: Clicca qui.
20/1/09:
Approfondimento: Riepilogo. Esercizi di preparazione alla prova finale.