Corso impartito dal 27 settembre 2017 al 20 dicembre 2017
Le lezioni si terranno mercoledì e venerdì dalle 10.00 alle 13.00 in aula 1, presso la sede di Latina, in via A. Doria 3
Ricevimento studenti: Subito dopo le lezioni presso lo Studio 5 (sede di Latina). Inviare SEMPRE un'email, non più tardi del giorno precedente.
| Settimana | Mercoledì | Venerdì |
|---|---|---|
| 25/9-01/10/2017 | Introduzione agli algoritmi e loro costo. Numeri di Fibonacci. [T1] 1.1-1.4. | Notazione asintotica O-grande, Omega-grande, Theta-grande. Esempi. [T1] 1.5 - 1.7, 1.10, 2.1 - 2.2. |
| 2-8/10/2017 |
Limitazione inferiore e superiore al costo di un algoritmo.
Metodi di analisi (caso peggiore, caso migliore, caso medio).
Ricerca sequenziale iterativa: descrizione e analisi.
Ricerca binaria iterativa: descrizione e analisi.
Soluzione di equazioni di ricorrenza: metodo dell'albero della ricorsionee
e metodo della sostituzione.
Principio di induzione matematica (Esempio: formula di Gauss per la somma dei primi n interi).
Esempi di applicazione. [T1] 2.3, 2.4 - 2.5.1, 2.5.2. |
Strategia Divide et Impera.
Soluzione di equazioni di ricorrenza: teorema Master e dimostrazione. [T1] 2.5.3. |
| 9-15/10/2017 |
Esempi di applicazione del teorema Master.
Esercizi sulla notazione asintotica.
Teorema sull'andamento asintotico di un polinomio (con dimostrazione). [v. Slide] |
Introduzione ai tipi di dato astratto.
Il tipo di dato Dizionario, Pila e Coda.
Tecniche di rappresentazione dei dati.
Implementazioni indicizzate e collegate di Dizionario.
Tipo di dato Albero.
Rappresentazione di alberi con vettore dei padri. [T1] Introduzione al Cap.3, fino a 3.3.1, paragrafo "Vettore Padri" incluso. |
| 16-22/10/2016 |
Rappresentazione di alberi con vettore posizionale. Rappresentazione collegata di alberi. Algoritmi di visita: generica, profondità, ampiezza (descrizione, implementazione, costo). Esercizi. [T1] Cap.3, da 3.3.1 incluso. |
Esercitazione in Laboratorio (soluzione). |
| 23-29/10/2016 | Il problema dell'ordinamento. L'approccio incrementale. Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): SelectionSort, InsertionSort, BubbleSort [T1] 4.2. | Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): HeapSort. Algoritmi con approccio divide ed impera (descrizione, pseudocodice, analisi): MergeSort. [T1] 4.3 - 4.4. |
| 30/10-05/11/2017 | Festa (1 novembre) |
Algoritmi con approccio divide ed impera (descrizione, pseudocodice, analisi): QuickSort.
Dimostrazione del lower bound per ordinamento con modello di costi
basato su confronti.
Algoritmi di ordinamento di interi (descrizione, pseudocodice, analisi):
IntegerSort. [T1] 4.1, 4.5, 4.6 (solo IntegerSort). |
| 06-12/11/2017 |
Algoritmi di ordinamento di interi (descrizione, pseudocodice, analisi):
BucketSort, RadixSort.
Il problema della ricerca.
Alberi binari di ricerca (BST). [T1] 4.6, 4.7. 6.1. |
Introduzione agli alberi AVL.
Alberi AVL: analisi della profondità (dimostrazione);
rotazioni, ricerca e inserimento. [T1] 6.2 (fino al Lemma 6.2, incluso). |
| 13-19/11/2017 | Lezione cancellata. | Alberi AVL: cancellazione; analisi del costo delle operazioni. Tabelle hash: funzioni hash; collisioni; risoluzione delle collisioni mediante liste di collisione. [T1] 6.2 (dal Lemma 6.2). 7.1, 7.2, 7.3.1. |
| 20-26/11/2017 |
Tabelle hash: risoluzione delle collisioni mediante indirizzamento aperto;
scansione lineare e hashing doppio; costo nel caso peggiore e nel caso medio.
Grafi: generalità e nozioni preliminari. [T1] 7.3.2, 11.1. |
Esercitazione in Laboratorio (soluzione). |
| 27/11 - 3/12/2017 |
Strutture dati per la rappresentazione di grafi
(e costo delle operazioni comuni):
lista di archi; liste di adiacenza; liste di incidenza; matrice di adiacenza.
Grafi, algoritmi di visita: generico, in ampiezza, in profondità (iterativo e ricorsivo). [T1] 11.2, 11.3. |
La relazione di raggiungibilità, componenti connesse e fortemente connesse, calcolo
delle componenti connesse e fortemente connesse. Visita di grafi non connessi.
Grafi: minimo albero ricoprente, definizione e proprietà.
Regola del ciclo. Regola del taglio. Algoritmo generico.
Algoritmi per il calcolo del minimo albero ricoprente (descrizione e analisi di complessità):
algoritmo di Kruskal. [T1] 11.4 - 11.5 (escluso 11.5.2). capitolo 12, fino a 12.3 (escluso, ed escluso 12.2.1). |
| 4-10/12/2017 |
Dimostrazione di terminazione e correttezza dell'algoritmo generico
per il calcolo del minimo albero ricoprente.
Algoritmi per il calcolo del minimo albero ricoprente (descrizione e analisi di complessità):
algoritmo di Prim; algoritmo di Borůvka. [T1] capitolo 12, esclusi 12.2.1 e 12.3.1. |
Festa (Immacolata). |
| 11-17/12/2017 |
Cammini minimi: definizione e proprietà.
Distanza tra nodi. Algoritmo per il calcolo dei cammini minimi a partire dalle
distanze tra i nodi (descrizione e analisi).
Albero dei cammini minimi. [T1] capitolo 13, fino a 13.2. |
Algoritmo di Bellman e Ford per il calcolo delle distanze (descirizione e analisi). [T1] capitolo 13, fino a 13.4. Ordinamento topologico: definizione e algoritmo per il calcolo (descrizione e analisi). Algoritmo per il calcolo delle distanze in grafi diretti aciclici (descrizione e analisi). Algoritmo di Dijkstra. [T1] 13.3 - 13.5 (escluso 13.5.1). |
| 18-25/12/2017 | Esercizi d'esame. Fine corso. | - |