Lezioni del Modulo di Teoria di Algoritmi e
Strutture Dati
A.A. 2016/17
20/9/16:
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.
22/09/16:
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.
28/09/16:
Analisi di un algoritmo: caso peggiore, migliore e medio. Esempio: il problema
della ricerca. Ricerca sequenziale in un insieme non ordinato. Ricerca
binaria in un insieme ordinato. Analisi della complessità temporale nel caso
migliore, peggiore e medio. Complessità di un algoritmo e delimitazione
(inferiore e superiore) alla complessità di un problema.
Dispense:
Clicca
qui.
04/10/16:
Soluzione di equazioni di ricorrenza: metodo della ricorsione
e metodo iterativo. Il teorema principale: dimostrazione ed esempi.
Dispense:
Clicca
qui.
05/10/16: 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.
12/10/16: Approfondimento: variante dell’ INSERTION
SORT con utilizzo della ricerca binaria.
Algoritmo BUBBLE SORT.
Lower
bound per il problema dell’ordinamento basato
sull’albero di decisione.
Dispense:
Clicca
qui.
18/10/16 (3 ore):
Approfondimento: albero di decisione
per il SELECTION SORT.
Algoritmo
ottimale per la fusione ordinata di 2 sequenze ordinate. Algoritmo MERGE
SORT. Analisi della complessità temporale.
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. e Clicca
qui.
19/10/16: 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.
25/10/16: 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.
26/10/16: 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.
3/11/16: 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: minimo, massimo,
predecessore, successore, ricerca, inserimento e cancellazione.
Dispense:
Clicca
qui.
08/11/16: Prova intermedia, h. 11:30 Aula A1.6.
15/11/16: Alberi binari di
ricerca bilanciati. 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.
17/11/16: 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/11/16: Grafi:
definizioni fondamentali. 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.
24/11/16: Visita di un
grafo. Paradigma di visita generica.
Dispense:
Clicca
qui.
30/11/16:
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 dei cammini minimi a sorgente
singola in grafi pesati diretti aciclici. Esempi.
Dispense:
Clicca
qui.
1/12/16:
Algoritmo di Bellman
e Ford per il problema dei cammini minimi a sorgente singola in grafi pesati
diretti senza cicli negativi. Esempi.
Dispense:
Clicca
qui.
6/12/16:
Algoritmo di Dijkstra per il problema dell'albero dei
cammini minimi a sorgente singola in grafi pesati (diretti e non diretti) con
pesi non negativi. Esempi.
Dispense:
Clicca
qui.
13/12/16:
Algoritmo di Floyd e Warshall per il problema del
cammino minimo tra tutte le coppie di nodi in grafi pesati diretti senza cicli
negativi. Esempi.
Dispense:
Clicca
qui.
15/12/16:
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.
20/12/16: 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.
21/12/16:
Algoritmo di Prim e analisi della complessità. Algoritmo
di Borůvka e analisi della complessità.
Dispense:
Clicca
qui.