Università degli Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica
Via Vetoio, Località Coppito, 67010 L'AQUILA

Lezioni del Modulo di Teoria di Algoritmi e Strutture Dati

A.A. 2021/22

29/09/21: 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.

30/09/21: 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.

5/10/21: Definizione formale di complessità asintotica: notazioni O,Ω,Θ,o,ω. Esempi.

Dispense: Clicca qui.

6/10/21: 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.

12/10/21 (Dott.ssa Giovanna Melideo): Soluzione di equazioni di ricorrenza: metodo della ricorsione e metodo iterativo. Il teorema principale: dimostrazione ed esempi.

Dispense: Clicca qui.

13/10/21: 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/21: 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.

20/10/21: Approfondimento: albero di decisione per il SELECTION SORT e per INSERTION SORT-1.

Algoritmo ottimale per la fusione ordinata di 2 sequenze ordinate. Algoritmo MERGE SORT. Analisi della complessità temporale.

Dispense: Clicca qui.

26/10/21 (Dott.ssa Giovanna Melideo): Code di priorità: l’heap binario. Algoritmo HEAP SORT. Procedure di creazione e di mantenimento dell’heap.

Dispense: Clicca qui.

27/10/21: Analisi della complessità temporale di HEAP SORT. Esempi. Algoritmo QUICKSORT. Partizionamento in loco. Analisi del caso peggiore. Analisi del caso medio. Algoritmi di ordinamento lineari: INTEGER SORT.

Dispense: Clicca qui.

2/11/21: Algoritmi di ordinamento lineari: BUCKET SORT, RADIX SORT. Code di priorità. Implementazioni elementari con liste e array ordinati e non ordinati. l’heap d-ario.

Dispense: Clicca qui.

3/11/21: 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 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.

Prova parziale: La prima prova parziale (scritto) di Teoria e l’appello straordinario per i fuori corso si terranno in presenza martedì 9 Novembre 2021 ore 10.00 in A1.7, e potranno essere svolti a distanza dai soli studenti autorizzati alla DAD, sul canale privato dedicato del Team ”Algoritmi e Strutture Dati - A.A. 2021-2022”

16/11/21: 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.

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

23/11/21 (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.

24/11/21: 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.

30/11/21: Visita di un grafo. Paradigma di visita generica. 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.

Dispense: Clicca qui.

01/12/21: 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/21: 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.

14/12/21 (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.

Dispense: Clicca qui.

15/12/21: 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.

21/12/21: 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/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.

11/01/22: Algoritmo di Prim e analisi della complessità. Esempio di esecuzione dell'algoritmo di Prim. Algoritmo di Borůvka e analisi della complessità. Esempio di esecuzione dell'algoritmo di Borůvka.

Dispense: Clicca qui.