Lezioni del Modulo di Algoritmi e Strutture
Dati 2012/13
1/10/12:
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.
3/10/12:
Algoritmi lineari in n per determinare l'n-esimo numero della
sequenza di Fibonacci. Primi accenni alla complessità asintotica: notazione
Θ. 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.
Dispense:
Clicca
qui.
10/10/12:
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 (enunciato). Esempi.
Dispense:
Clicca
qui.
15/10/12:
Il teorema principale: dimostrazione ed esempi.
Dispense:
Clicca
qui.
17/10/12: 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.
22/10/12: Lower bound per il problema dell’ordinamento basato sull’albero
di decisione.
Dispense:
Clicca
qui.
24/10/12: 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.
29/10/12: 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.
31/10/12: 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.
5/11/12: 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.
12/11/12: 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.
14/11/12: Alberi binari di
ricerca: minimo, massimo, predecessore, successore, ricerca, inserimento e
cancellazione.
Dispense: Clicca qui.
19/11/12: Alberi AVL:
rotazione di base. Rotazione sinistro-sinistro e sinistro-destro.
Dispense:
Clicca
qui.
21/11/12: Inserimento e
cancellazione di un elemento in un albero AVL. Cancellazioni a cascata in un
albero AVL. Esercizi di preparazione alla prova intermedia.
Dispense:
Clicca
qui.
28/11/12: Prova intermedia.
3/12/12: 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.
5/12/12: 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/12/12: Correzione prova
parziale. Grafi: definizioni fondamentali.
12/12/12: Rappresentazioni
in memoria di grafi: lista di archi, lista di adiacenza, matrice di adiacenza. Prestazioni
temporali sulle operazioni fondamentali dipendentemente dalla rappresentazione
in memoria utilizzata.
Dispense:
Clicca
qui.
17/12/12: Visita di un
grafo. Paradigma di visita generica.
Dispense:
Clicca
qui.
19/12/12:
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.
Dispense:
Clicca
qui.
7/1/13:
Algoritmo di Bellman e Ford per il problema dell'albero
dei cammini minimi in un grafo pesato senza cicli negativi. Esempi.
Dispense:
Clicca
qui.
9/1/13:
Algoritmo di Dijkstra per il problema dell'albero dei
cammini minimi a sorgente singola in un grafo pesato con pesi non negativi.
Esempi.
Dispense:
Clicca
qui.
14/1/13:
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.
16/1/13:
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.
21/1/13: 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.
23/1/13:
Algoritmo di Prim e analisi della complessità.
Algoritmo di Borůvka e analisi della
complessità.
Dispense: Clicca qui.