| Settimana | Lunedì | Giovedì |
|---|---|---|
| 22-28/09/2025 | Lezione cancellata. | Lezione cancellata. |
| 29/09-05/10/2025 |
Introduzione al corso.
Introduzione agli algoritmi e loro costo. Numeri di Fibonacci. [Slide e appunti]. [T1] Cap 1. Video |
Modello a costi uniformi.
Notazione asintotica O-grande, Omega-grande, Theta-grande.
Esempi.
Teorema sull'andamento asintotico di un polinomio.
Esercizi sulla notazione asintotica.
Limitazione inferiore e superiore al costo di un algoritmo.
Metodi di analisi (caso peggiore, caso migliore, caso medio). [Slide e appunti]. [T1] 2.1 - 2.4. Video |
| 6-12/10/2025 |
Soluzione di equazioni di ricorrenza: metodi dell'albero della
ricorsione, dell'iterazione, della sostituzione.
Principio di induzione matematica ed esempio di applicazione (formula di Gauss per la somma di interi).
Esempi di applicazione dei tre metodi. Algoritmo di ricerca binaria ricorsivo.
[Slide e appunti]. [T1] 2.4 - 2.5.3 (escluso). Video |
Cenni all'approccio divide et impera.
Soluzione di equazioni di ricorrenza: teorema Master (senza dimostrazione).
Esempi di applicazione del teorema Master.
Algoritmi di ricerca binaria iterativo e ricorsivo.
Introduzione ai tipi di dato astratti.
Il tipo di dato astratto Dizionario.
Tecniche di rappresentazione dei dati: indicizzata e collegata.
Implementazione con rappresentazione indicizzata e collegata di Dizionario.
[Slide e appunti]. [T1] 3 - 3.1 (incluso). Video |
| 13-19/10/2025 |
I tipi di dato astratti Pila e Coda.
Implementazione con rappresentazione indicizzata e collegata di
Pila e Coda.
Realizzazione in C del Dizionario con rappresentazione mediante SCL
(Codice). [Slide e appunti]. [T1] 3.2. Video della lezione |
Il tipo di dato astratto Albero.
Rappresentazioni indicizzate di alberi: vettore dei padri; vettore posizionale.
Rappresentazioni collegate di alberi: puntatori ai figli, lista dei figli, primo figlio-fratello successivo. [Slide e appunti]. [T1] 3, fino a 3.3.3 (escluso). Video |
| 20-26/10/2025 | Visite di alberi (descrizione, pseudocodice, analisi): generica, in profondità iterativa e ricorsiva, in ampiezza. [Slide e appunti]. [T1] 3.3.3. Video |
Il problema dell'ordinamento. L'approccio incrementale.
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
SelectionSort, InsertionSort, BubbleSort.
Conteggio del numero dei nodi di un albero (soluzione ricorsiva).
Implementazione in C delle strutture dati per la modellazione del tipo Albero con rappresentazione collegata
(Codice). [Slide e appunti]. [T1] 4.2. Video |
| 27/10-02/11/2025 |
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
HeapSort. [Slide e appunti] [T1] 4.3. Video |
Algoritmi con approccio divide et impera (descrizione, pseudocodice, analisi):
MergeSort, QuickSort (senza dimostrazione complessità caso medio).
Dimostrazione del lower bound per ordinamento basato su confronti. [Slide e appunti] [T1] 4.4, 4.5, 4.1. Video |
| 3-9/11/2025 |
Il problema della ricerca.
Alberi binari di ricerca (BST): ricerca, inserimento, cancellazione.
Alberi AVL: definizione, analisi della profondità (con dimostrazione). [Slide e appunti] [T1] Cap. 6, fino a 6.2.2 (escluso) Video |
Alberi AVL: rotazioni, inserimento e cancellazione; costo delle operazioni.
Esercizi su alberi AVL. [Slide e appunti] [T1] 6.1-6.2. Video |
| 10-16/11/2025 |
Esercizi d'esame su implementazione di funzioni ricorsive e alberi AVL. [Appunti]. Video |
Esercizi d'esame su implementazione di funzioni ricorsive, alberi AVL, equazioni di ricorrenza e algoritmi di
ricerca. [Appunti]. Video non disponibile per malfunzionamento della rete. |
| 17-23/11/2025 | Prova Intermedia. |
Correzione esercizi della prova intermedia.
Hash tables: introduzione, generalità,
esempi, uniformità semplice.
Risoluzione delle collisioni mediante liste di collisione. [Slide e appunti] [T1] Cap. 7, fino a 7.3.1 incluso. Video della lezione Video aggiuntivi su esercizi di programmazione in C:
|
| 24-30/11/2025 |
Hash tables: risoluzione delle collisioni mediante indirizzamento aperto;
scansione lineare e hashing doppio.
Costo della scansione nel caso medio per i metodi di scansione lineare e hashing doppio.
Esercizi sulle hash tables. [Slide e appunti] [T1] 7.3.2 Video |
Grafi: generalità e nozioni preliminari.
Strutture dati per la rappresentazione di grafi
(e costo delle operazioni comuni):
liste di adiacenza, matrice di adiacenza.
Algoritmo per la visita generica.
[Slide e appunti] [T1] Cap. 11, fino a 11.3.1 escluso. Video |
| 1-7/12/2025 |
Algoritmi per la visita di grafi e analisi del costo:
in ampiezza, in profondità (iterativo e ricorsivo).
La relazione di raggiungibilità.
Componenti connesse di un grafo non orientato e loro calcolo.
Visita di grafi non connessi.
Componenti fortemente connesse di un grafo orientato e loro calcolo.
Visita di grafi non fortemente connessi.
[Slide e appunti] [T1] Da 11.3.1 a 11.5.1 incluso. Video |
Minimo albero ricoprente, definizione e proprietà.
Regola del ciclo. Regola del taglio.
Algoritmo generico per la costruzione del minimo albero ricoprente
(descrizione).
Algoritmi per il calcolo del minimo albero ricoprente
(descrizione e costo): algoritmi di Kruskal, Prim, Borůvka.
[Slide e appunti] [T1] Cap. 12, esclusi 12.2.1 e 12.3.1. Video |
8-14/12/2025 | Festa. |
(Lezione Online).
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. Tecnica del rilassamento.
Algoritmo di Bellman-Ford per il calcolo delle distanze (descrizione e analisi).
Esempio di applicazione dell'algoritmo.
[Slide e appunti] [T1] 13 - 13.3 (incluso). |
| 15-21/12/2025 |
Ordinamento topologico: definizione e algoritmo
per il calcolo (descrizione e analisi). Algoritmo di Bellman-Ford
per il calcolo
delle distanze in grafi diretti aciclici (descrizione e analisi).
Algoritmo di Dijkstra (descrizione e analisi). [Slide e appunti] [T1] 13.3 - 13.5.1 (escluso) Video |
L'esame prevede per tutti (indipendentemente dall'anno di iscrizione):
Le Istruzioni per la consegna del progetto saranno comunicate al termine del corso.
Le date per la discussione del progetto sono indicate insieme agli appelli d'esame.