Lezioni del Modulo di
Teoria di Algoritmi e Strutture
Dati
A.A. 2020/21
6/10/20:
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.
7/10/20:
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.
14/10/20:
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.
20/10/20: 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.
21/10/20 (Dott.ssa Giovanna Melideo): Soluzione di equazioni di ricorrenza: metodo della
ricorsione e metodo iterativo. Il teorema principale: dimostrazione ed esempi.
Dispense: Clicca
qui.
27/10/20 (Dott.ssa Giovanna Melideo): Approfondimento:
variante dell’ INSERTION SORT con utilizzo della ricerca binaria.
Lower bound per il problema dell’ordinamento basato
sull’albero di decisione.
Dispense: Clicca
qui.
28/10/20: 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.
Dispense: Clicca
qui.
03/11/20: 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.
04/11/20: 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/10/20: 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.
11/10/20 (Dott.ssa Giovanna Melideo): 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/20: 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.
18/11/20: 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.
24/11/20 (Dott.ssa Giovanna Melideo): 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.
25/11/20: 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.
01/12/20 (Dott.ssa Giovanna Melideo): Visita di un grafo. Paradigma di visita generica.
Dispense: Clicca
qui.
02/12/20: 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.
7/12/20: 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.
15/12/20:
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.
16/12/20:
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.
22/12/20 (Dott.ssa Giovanna Melideo): 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.
12/01/21: 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.
13/01/21:
Algoritmo di Prim e analisi della complessità. Algoritmo di Borůvka e
analisi della complessità.
Dispense: Clicca qui.