Lezioni di Algoritmi e Strutture Dati 2005/06

4/10/05: Introduzione. Problemi, algoritmi e programmi. Un problema esemplificativo: la sequenza di Fibonacci. Primi 4 algoritmi per determinare l’n-esimo numero della sequenza di Fibonacci. Complessità degli algoritmi come numero di linee di codice.

5/10/05: 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. Approfondimento: Problema della sequenza di Fibonacci generalizzata con F₁=a e F₂=b.

6/10/05: 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. Analisi di algoritmi ricorsivi: relazioni di ricorrenza. Esempio: ricerca di un elemento in un array ordinato. Risoluzione di equazioni di ricorrenza: metodo iterativo e metodo della sostituzione.

11/10/05: 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/05: 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.

13/10/05: Algoritmo ottimale per la fusione ordinata di 2 sequenze ordinate. Algoritmo MERGE SORT. Analisi della complessità temporale. Teorema principale (enunciato).

Dispense: Clicca qui.

19/10/05: 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.

20/10/05: Algoritmo QUICKSORT. Partizionamento in loco. Analisi del caso peggiore. Analisi del caso medio (cenni). Algoritmi di ordinamento lineari: INTEGER SORT, BUCKET SORT, RADIX SORT. Approfondimento: Algoritmo BUBBLE SORT.

25/10/05: 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/05: Alberi binari di ricerca: minimo, massimo, predecessore, successore, ricerca, inserimento e cancellazione.

Dispense: Clicca qui.

26/10/05: 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.

2/11/05: 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. Cenni sugli heap di Fibonacci.

3/11/05: Approfondimento: Esercizi di riepilogo di preparazione alla prova parziale.

15/11/05: Tabelle hash. Tabelle ad indirizzamento diretto. Fattore di carico. Funzioni 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.

16/11/05: Tecniche algoritmiche. Divide et impera: moltiplicazione di 2 interi di n cifre. Programmazione dinamica: distanza tra 2 stringhe. Metodo goloso: minimizzazione del tempo medio di attesa.

17/11/05: 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.

22/11/05: 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.

23/11/05: 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 con pesi anche negativi. Esempi.

24/11/05: Algoritmo di Dijkstra per il problema dell'albero dei cammini minimi a sorgente singola in un grafo pesato con pesi non negativi. Esempi. Cammino minimo tra tutte le coppie di nodi di un grafo con pesi anche negativi. Algoritmo di Floyd e Warshall.

29/11/05: Approfondimento: esempio di esecuzione dell’algoritmo di Floyd e Warshall. 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.

29/11/05: 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.

30/11/05: 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. Analisi della complessità. Approfondimento: esempio di esecuzione dell’algoritmo di Kruskal.

5/12/05: Il problema del minimo albero ricoprente: Algoritmo di Prim. Analisi della complessità. Algoritmo di Boruvka e cenni sull’analisi di complessità.

6/12/05: Approfondimento: dimostrazione del teorema del taglio. Correzione delle prove parziali.