Lezioni di Algoritmi e Strutture
Dati 2006/07
3/10/06: 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.
4/10/06: 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.
5/10/06: Definizione
formale di complessità asintotica: notazioni O,Ω,Θ,o,ω. Esempi.
Analisi di un algoritmo: caso peggiore, migliore e medio. Esempio: ricerca di
un elemento in una lista non ordinata. Approfondimento: Esercizi sulla
notazione asintotica.
Dispense: Clicca qui.
10/10/06: 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 e teorema principale. Esempi.
Dispense: Clicca qui.
11/10/06: Il problema
dell’ordinamento. Algoritmo INSERTION SORT. Analisi della complessità temporale nel caso migliore, peggiore e medio.
Analisi della complessità spaziale. Approfondimento: Algoritmo REVERSE INSERTION SORT.
Dispense: Clicca qui.
12/10/06: Algoritmo SELECTION SORT. Analisi della complessità
temporale. Delimitazione inferiore e superiore alla complessità di un problema.
Lower bound per il problema
dell’ordinamento basato sull’albero di decisione.
Dispense: Clicca qui.
17/10/06: Algoritmo
ottimale per la fusione ordinata di 2 sequenze ordinate. Algoritmo MERGE SORT. Analisi della complessità temporale.
Dispense: Clicca qui.
18/10/06: 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.
19/10/06: 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.
24/10/06: Code
di priorità: 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. Heap binomiale: struttura e proprietà. Analisi delle operazioni.
Esempi. Cenni sugli heap di Fibonacci.
Dispense: Clicca qui.
25/10/06: 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.
25/10/06:
Alberi binari di ricerca: minimo, massimo, predecessore, successore, ricerca,
inserimento e cancellazione.
Dispense: Clicca qui.
31/10/06: 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. Approfondimento:
Cancellazioni a cascata in un albero AVL.
Dispense: Clicca qui.
2/11/06:
Approfondimento: Esercizi di riepilogo di preparazione alla prova
parziale.
14/11/06: 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.
15/11/06: 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.
16/11/06:
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. Visita di un grafo. Paradigma di visita generica.
Dispense: Clicca qui.
22/11/06: Visita di un grafo. Visita in ampiezza di un
grafo diretto/non diretto. Proprietà dell’albero BFS. Visita in profondità di
un grafo diretto/non diretto. Proprietà dell’albero DFS. Approfondimento:
trasformazione da rappresentazione tramite matrice di adiacenza a liste di
adiacenza.
Dispense: Clicca qui.
23/11/06: Il problema
dell'albero dei cammini minimi a sorgente singola in un grafo pesato.
Definizioni e proprietà fondamentali dei cammini minimi. Tecnica del rilassamento.
Algoritmo di Bellman e Ford
per grafi pesati senza cicli negativi. Esempi.
Dispense: Clicca qui.
28/11/06: Algoritmo basato sull’ordinamento topologico per
il problema dell'albero dei cammini minimi a sorgente singola in un grafo
pesato aciclico. 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.
Dispense: Clicca qui.
29/11/06: 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 ammortizzata. Approfondimento: esempio di esecuzione
dell’algoritmo di Floyd e Warshall.
Dispense: Clicca qui.
30/11/06: 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. Approfondimento:
Analisi della complessità.
Dispense: Clicca qui.
5/12/06: Algoritmo di Prim.
Analisi della complessità. Algoritmo di Boruvka e
cenni sull’analisi di complessità.
Dispense: Clicca qui.
6/12/06:
Approfondimento: Riepilogo. Esercizi di preparazione alla prova finale.