Corso impartito dal 23 settembre 2019 al 18 dicembre 2019
Le lezioni si terranno lunedì 15.00-18.00 e mercoledì 10.00-13.00 in aula 5, presso la sede di Latina, in via A. Doria 3
Ricevimento studenti: per appuntamento, inviare un'email.
| Settimana | Lunedì | Mercoledì |
|---|---|---|
| 23-29/09/2019 |
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. |
| 30/09-6/10/2019 |
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 ricorsione
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. |
| 7-13/10/2019 |
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. Esercizio d'esame su costo computazionale (17/01/2019, es.2). [T1] 3.3 - 3.3.1 incluso. |
| 14-20/10/2019 |
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.
Visite di alberi (descrizione, pseudocodice, analisi):
in profondità iterativa e ricorsiva, in ampiezza.
Esercizi in aula: imnplementazione in C del tipo astratto
Dizionario con rappresentazione indicizzata;
Conteggio del numero dei nodi di un albero (soluzione ricorsiva).
[T1] 3.3.2. |
Il problema dell'ordinamento. L'approccio incrementale. Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi): SelectionSort, InsertionSort, BubbleSort. [T1] 4.2. |
| 21-27/10/2019 |
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
HeapSort.
[T1] 4.3.
Algoritmi con approccio divide et 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. [T1] 4.1, 4.6 (fino a BucketSort escluso). |
| 28/10-03/11/2019 |
Algoritmi di ordinamento di interi (descrizione, pseudocodice, analisi):
BucketSort, RadixSort.
Il problema della ricerca.
Alberi binari di ricerca (BST).
Introduzione agli alberi AVL. [T1] 4.6, 4.7, 6.1, 6.2 fino a 6.2.1 escluso. |
Alberi AVL: analisi della profondità (dimostrazione);
rotazioni. [T1] 6.2.2 e dimostrazione di profondità su appunti e slide. |
| 04-10/11/2019 |
Alberi AVL: ricerca, inserimento e cancellazione;
analisi del costo delle operazioni.
Tabelle ad accesso diretto. Introduzione alle hash table: generalità,
esempi. [T1] 6.2.3, 7.1. |
Hash table: uniformità semplice, collisioni;
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.2, 7.3. |
| 11-17/11/2019 |
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.
Algoritmi di visita di un grafo: generico, in ampiezza, in profondità (iterativo). [T1] 11.1 - 11.3. |
Grafi: visita in profondità ricorsiva;
la relazione di raggiungibilità, componenti connesse e fortemente connesse, calcolo
delle componenti connesse e fortemente connesse.
Visita di grafi non connessi. [T1] 11.4 - 11.5 (escluso 11.5.2). |
| 18-24/11/2019 |
Minimo albero ricoprente, definizione e proprietà.
Regola del ciclo. Regola del taglio. Algoritmo generico (con dimostrazione
di terminazione e correttezza).
capitolo 12, fino a 12.2 (escluso). |
Algoritmi per il calcolo del minimo albero ricoprente (descrizione e analisi di complessità):
algoritmo di Kruskal; algoritmo di Prim; algoritmo di Borůvka.
Cammini minimi: definizione e proprietà.
Distanza tra nodi.
[T1] 12.2-12.4, esclusi 12.2.1 e 12.3.1; capitolo 13, fino a 13.1.3 escluso. |
| 25/11 - 1/12/2019 |
Algoritmo per il calcolo dei cammini minimi a partire dalle
distanze tra i nodi (descrizione e analisi).
Albero dei cammini minimi.
Algoritmo di Bellman e Ford per il calcolo delle distanze (descirizione e analisi).
[T1] 13.1.3 - 13.3. |
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 (descrizione e analisi). [T1] 13.4 - 13.5, escluso 13.5.1. |
| 2-8/12/2019 | Esercizi d'esame. Implementazione di tipi astratti (Pila con rappresentazione collegata). | Implementazione del tipo astratto Albero (con lista dei figli). |
| 9-15/12/2019 | Esercizi d'esame. | Esercizi d'esame. |
| 16-22/12/2019 | Esercizi d'esame. Fine corso. |