| Settimana | Mercoledì | Venerdì |
|---|---|---|
| 23-29/09/2024 |
Introduzione al corso.
Introduzione agli algoritmi e loro costo. Numeri di Fibonacci. [Slide e appunti]. [T1] 1.1-1.5. 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. [Slide e appunti]. [T1] 2.1 - 2.3. Video |
| 30/09-06/10/2024 |
Metodi di analisi (caso peggiore, caso migliore, caso medio).
Soluzione di equazioni di ricorrenza: metodo 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 sequenziale iterativo.
[Slide e appunti]. [T1] 2.4 - 2.5 (fino a 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.
Algoritmo di ricerca binario 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] 2.5.3, 3-3.1. Video |
| 7-13/10/2024 | Lezione cancellata. |
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).
Introduzione al tipo di dato Albero. [Slide e appunti]. [T1] 3.2, 3.3, fino a 3.3.1 incluso. Video |
| 14-20/10/2024 |
Rappresentazioni indicizzate di alberi: vettore dei padri; vettore posizionale.
Rappresentazioni collegate di alberi: lista di figli.
Visite di alberi: algoritmo di visita generica.
Implementazione in C delle strutture dati per la modellazione del tipo Albero con rappresentazione collegata
(Codice). [Slide e appunti]. [T1] 3.3.1 - 3.3.3. Video |
Lezione registrata: |
| 21-27/10/2024 | Lezione cancellata. |
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.
Conteggio del numero dei nodi di un albero (soluzione ricorsiva).
[Slide e appunti]. [T1] 3.3.3. Video |
| 28/10-03/11/2024 |
Il problema dell'ordinamento. L'approccio incrementale.
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
SelectionSort, InsertionSort, BubbleSort, HeapSort (cenni).
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, fino a 4.5 (incluso), escluso 4.3. Video |
Festa. |
| 4-10/11/2024 |
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 |
Seminario su Intelligenza Artificiale (ore 10.00, Sala Conferenze presso facoltà di Economia). |
| 11-17/11/2024 |
Alberi AVL: rotazioni, inserimento e cancellazione; costo delle operazioni.
Esercizi su alberi AVL. [Slide e appunti] [T1] 6.1-6.2. Video |
Esercizi d'esame su implementazione di funzioni ricorsive,
algoritmi di ordinamento, equazioni di ricorrenza, alberi AVL. [Appunti]. Video |
| 18-24/11/2024 | Prova Intermedia. Correzione esercizi della prova intermedia. Video | Esercizi di programmazione in C: implementazione dell'algoritmo QuickSort in loco; implementazione del tipo di dato astratto albero. Video |
| 25/11-1/12/2024 |
Lezione online.
Hash tables: introduzione, generalità,
esempi, uniformità semplice.
Risoluzione delle collisioni mediante liste di collisione.
Costo delle operazioni nel caso peggiore e nel caso medio.
Introduzione alla risoluzione delle collisioni mediante indirizzamento aperto. [Slide e appunti] [T1] Cap. 7, fino a 7.3.1 incluso. Video |
Hash table: risoluzione delle collisioni mediante indirizzamento aperto;
scansione lineare e hashing doppio. Costo della scasione nel caso medio per
i metodi di scansione lineare e hashing doppio.
Grafi: generalità e nozioni preliminari. [Slide e appunti] [T1] 7.3.2; 11, 11.1. Video |
| 2-8/12/2024 |
Strutture dati per la rappresentazione di grafi
(e costo delle operazioni comuni):
liste di archi, liste di adiacenza, matrice di adiacenza. [Slide e appunti] [T1] 11.1 - 11.2 (incluso) Video |
Algoritmi per la visita di grafi e analisi del costo:
generica, 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.
Implementazione del tipo di dato astratto Albero in rappresentazione con
liste di adiacenza. [Slide e appunti] [T1] 11.3 - 11.4 (incluso). Video | 9-15/12/2024 |
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. [Slide e appunti] [T1] 13 - 13.2 (incluso). Video |
Algoritmo di Bellman e Ford per il calcolo delle distanze (descrizione 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 (descrizione e analisi). [Slide e appunti] [T1] 13.3 - 13.5.1 (escluso) Video |
| 16-22/12/2024 | Strutture dati per la rappresentazione di grafi con archi pesati. Esercizi d'esame. Fine corso. [Slide e appunti] Video | - |
L'esame prevede per tutti (indipendentemente dall'anno di iscrizione):
Istruzioni per la consegna del progetto (in caso di problemi con il sistema di assegnazione, contattare il docente).
Le date per la discussione del progetto sono indicate insieme agli appelli d'esame.