Corso impartito dal 25 settembre 2018 al 19 dicembre 2018
Le lezioni si terranno martedì 14.00-17.00 e mercoledì 10.00-13.00 in aula 7, presso la sede di Latina, in via A. Doria 3
Ricevimento studenti: per appuntamento, inviare un'email.
| Settimana | Martedì | Mercoledì |
|---|---|---|
| 24-30/09/2018 |
Inizio corso.
Introduzione agli algoritmi e loro costo. Numeri di Fibonacci. [T1] 1.1-1.4 |
Notazione asintotica O-grande, Omega-grande, Theta-grande.
Esempi.
Limitazione inferiore e superiore al costo di un algoritmo.
Teorema sull'andamento asintotico di un polinomio con dimostrazione [Slide e appunti].
Esercizi sulla notazione asintotica [Slide e appunti]. [T1] 1.5 - 1.7, 1.10, 2.1 - 2.2, 2.3. |
| 1-7/10/2018 |
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 ed
esempio di applicazione (formula di Gauss per la somma dei primi n interi) [Slide e appunti]. [T1] 2.4 - 2.5.1, 2.5.2. |
Strategia Divide et Impera.
Soluzione di equazioni di ricorrenza: teorema Master con dimostrazione.
Esempi di applicazione del teorema Master. [T1] 2.5.3. |
| 8-14/10/2018 |
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 e Pila. [Slide e appunti] [T1] Cap.3 fino a 3.2 incluso. |
Tipo di dato Albero.
Rappresentazioni indicizzate di alberi:
vettore dei padri; vettore posizionale.
Rappresentazioni collegate di alberi: lista di figli;
primo figlio e fratello successivo.
Visite di alberi: algoritmo di visita generica, con
dimostrazione di terminazione, costo e correttezza. [T1] 3.3.3, "Visita in profondità" esclusa. |
| 15-21/10/2018 |
Visite di alberi (descrizione, pseudocodice, analisi):
in profondità iterativa e ricorsiva, in ampiezza.
Il problema dell'ordinamento. L'approccio incrementale.
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
SelectionSort, InsertionSort, BubbleSort.
Esercizi. [T1] 3.3.3 da "Visita in profondità", 4.2. |
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): HeapSort. Introduzione agli algoritmi con approccio divide ed impera: MergeSort. [T1] 4.3. |
| 22-28/10/2018 |
Algoritmi con approccio divide ed impera (descrizione, pseudocodice, analisi):
MergeSort, QuickSort. [T1] 4.4 - 4.5. |
Dimostrazione del lower bound per ordinamento basato su confronti.
Algoritmi di ordinamento di interi (descrizione, pseudocodice, analisi):
IntegerSort, BucketSort, RadixSort. [T1] 4.1, 4.6, 4.7. |
| 29/10-04/11/2018 | Lezione cancellata per allerta meteo. |
Il problema della ricerca.
Alberi binari di ricerca (BST).
Introduzione agli alberi AVL.
Alberi AVL: analisi della profondità (dimostrazione). [T1] 6.1, 6.2, fino a 6.2.1 escluso (dimostrazione su appunti e slide). |
| 05-11/11/2018 |
Alberi AVL: rotazioni, ricerca, inserimento e cancellazione;
analisi del costo delle operazioni. [T1] 6.2.2 e 6.2.3. |
|
| 12-18/11/2018 |
Tabelle ad accesso diretto. Introduzione alle tabelle hash: generalità,
esempi, funzioni hash, uniformità semplice, collisioni. [T1] 7.1, 7.2. |
Tabelle hash: risoluzione delle collisioni
mediante liste di collisione e indirizzamento aperto;
scansione lineare e hashing doppio; costo nel caso peggiore e nel caso medio. [T1] 7.3. |
| 19-25/11/2018 |
Grafi: generalità e nozioni preliminari.
Strutture dati per la rappresentazione di grafi
(e costo delle operazioni comuni):
lista di archi; liste di adiacenza; liste di incidenza; matrice di adiacenza. [T1] 11.1 - 11.2. |
Grafi, algoritmi di visita: generico, in ampiezza, in profondità (iterativo e ricorsivo). [T1] 11.3. |
| 26/11 - 2/12/2018 |
La relazione di raggiungibilità, componenti connesse e fortemente connesse, calcolo
delle componenti connesse e fortemente connesse. Visita di grafi non connessi.
Minimo albero ricoprente, definizione e proprietà.
Regola del ciclo. Regola del taglio. Algoritmo generico. [T1] 11.4 - 11.5 (escluso 11.5.2). capitolo 12, fino a 12.2 (escluso). |
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 Kruskal; algoritmo di Prim; algoritmo di Borůvka. [T1] capitolo 12, esclusi 12.2.1 e 12.3.1. |
| 3-9/12/2018 |
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).
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 (descrizioner e analisi). [T1] capitolo 13, fino a 13.5 (escluso 13.5.1). |
| 10-16/12/2018 | Esercizi d'esame. | Esercitazione al calcolatore. |
| 17-23/12/2018 | Esercizi d'esame. Fine corso. | - |