Lezioni del Modulo di
Algoritmi e Strutture Dati 2011/12
3/10/11:
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.
5/10/11:
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.
Dispense:
Clicca
qui.
12/10/11:
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.
17/10/11: 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.
19/10/11: Lower
bound per il problema dell’ordinamento basato
sull’albero di decisione.
Dispense: Clicca qui.
24/10/11: 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.
26/10/11: 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.
2/11/11: 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.
7/11/11: 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.
9/11/11: 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/11: Alberi binari di ricerca:
minimo, massimo, predecessore, successore, ricerca, inserimento e cancellazione.
Dispense: Clicca qui.
16/11/11: Alberi AVL: rotazione di base. Rotazione sinistro-sinistro e sinistro-destro. Esercizi di preparazione alla prova intermedia.
Dispense:
Clicca
qui.
23/11/11: Prova intermedia.
28/11/11: Inserimento e cancellazione
di un elemento in un albero AVL. Cancellazioni a cascata in un albero AVL.
Dispense:
Clicca
qui.
30/11/11: 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.
05/12/11: 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.
07/12/11: 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.
12/12/11: Visita di un grafo. Paradigma
di visita generica.
Dispense: Clicca qui.
14/12/11:
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.
21/12/11:
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/1/12:
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.
16/1/12:
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.
18/1/12:
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.
23/1/12: 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.
25/1/12: Algoritmo di Prim e analisi della complessità. Algoritmo di Borůvka e analisi della complessità.
Dispense: Clicca qui.