Le lezioni si terranno mercoledì 14.00-17.00 e venerdì 9.00-12.00 in aula 2, presso la sede di Latina, in via A. Doria 3
Le lezioni si terranno in presenza presso la sede di Ingegneria di Latina, in via A. Doria, 3.
Tutte le informazioni riguardanti le procedure di accesso alle sedi Sapienza sono disponibili qui. Si segnala, in particolare, l'obbligo di indossare la mascherina all'interno dei locali.
Per garantire il tracciamento delle presenze, è obbligatoria la prenotazione Prodigit.
| Settimana | Mercoledì | Venerdì |
|---|---|---|
| 26/09-02/10/2022 |
Introduzione agli algoritmi e loro costo. Numeri di Fibonacci. [Slide e appunti]. [T1] 1.1-1.4 |
Notazione asintotica O-grande, Omega-grande, Theta-grande.
Esempi.
Teorema sull'andamento asintotico di un polinomio con dimostrazione.
Esercizi sulla notazione asintotica. [Slide e appunti]. [T1] 1.5 - 1.7, 1.10, 2.1 - 2.2 |
| 03-09/10/2022 |
Limitazione inferiore e superiore al costo di un algoritmo.
Metodi di analisi (caso peggiore, caso migliore, caso medio).
Soluzione di equazioni di ricorrenza: metodo dell'albero della
ricorsione,
metodo dell'iterazione, metodo della sostituzione.
Principio di induzione matematica ed
esempio di applicazione (formula di Gauss per la somma di interi).
[Slide e appunti]. [T1] 2.3 - 2.5.2. |
Soluzione di equazioni di ricorrenza: teorema Master (senza dimostrazione).
Esempi di applicazione del teorema Master.
Introduzione ai tipi di dato astratto.
Il tipo di dato astratto Dizionario. [Slide e appunti]. [T1] 2.5.3. Cap. 3 (Introduzione) |
| 10-16/10/2022 |
I tipi di dato astratto Pila e Coda.
Tecniche di rappresentazione dei dati.
Implementazione con rappresentazione indicizzata e collegata di
Dizionario, Pila e Coda.
[Slide e appunti]
[T1] 3.1.1, 3.1.2, 3.2 |
Introduzione al 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.
[Slide e appunti] [T1] 3.3, fino a 3.3.3. |
| 17-23/10/2022 |
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).
Realizzazione in C del tipo Albero con lista dei figli in
rappresentazione collegata.
[Slide e appunti] [T1] 3.3.3 |
Il problema dell'ordinamento. L'approccio incrementale.
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
SelectionSort, InsertionSort, BubbleSort, introduzione a Heapsort.
[Slide e appunti] [T1] 4.2 |
| 24-30/10/2022 |
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
HeapSort.
[Slide e appunti] [T1] 4.3 |
Algoritmi con approccio divide et impera (descrizione, pseudocodice, analisi):
MergeSort, QuickSort.
Dimostrazione del lower bound per ordinamento basato su confronti.
[Slide e appunti] [T1] 4.4, 4.5, 4.1 |
| 31-06/11/2022 |
Il problema della ricerca.
Alberi binari di ricerca (BST): ricerca, inserimento, cancellazione. Introduzione agli alberi AVL: definizione. [Slide e appunti] [T1] 6.1. |
Alberi AVL: analisi della profondità (con dimostrazione), rotazioni. [Slide e appunti] [T1] 6.2.1, 6.2.2 |
| 8-14/11/2021 |
Alberi AVL: inserimento e cancellazione; costo delle operazioni.
Tabelle ad accesso diretto. Introduzione alle hash table: generalità,
esempi.
[Slide e appunti] [T1] 6.2.3, 7.1, 7.2 |
Esercizi sugli alberi AVL. Esercizi d'esame su notazione O-grande, equazioni di ricorrenza, algoritmi ricorsivi, ordinamento, costo di MergeSort. |
| 15-21/11/2021 | Prova Intermedia. |
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. [Slide e appunti] [T1] 7.3.1, 7.3.2 |
| 21-27/11/2022 |
Grafi: generalità e nozioni preliminari.
Strutture dati per la rappresentazione di grafi
(e costo delle operazioni comuni):
liste di archi, liste di adiacenza, matrice di adiacenza.
Algoritmo di visita generica (con costo). [Slide e appunti] [T1] 11.1 - 11.3.1 (escluso) |
Lezione cancellata. |
| 28/11-4/12/2022 |
Algoritmi di visita di un grafo (con costo): in ampiezza, in profondità (iterativo e ricorsivo).
La relazione di raggiungibilità [Slide e appunti] [T1] 11.3.1 - 11.3.3. |
Componenti connesse e fortemente connesse di un grafo;
calcolo.
Visita di grafi non connessi.
Minimo albero ricoprente, definizione e proprietà.
[Slide e appunti] [T1] 11.4, 11.5 (fino a 11.5.2 escluso), 12.1. |
| 5-11/12/2022 |
Regola del ciclo. Regola del taglio.
Algoritmo generico per la costruzione del minimo albero ricoprente
(descrizione, dimostrazione di terminazione e correttezza).
Algoritmi per il calcolo del minimo albero ricoprente
(descrizione e costo, con e senza ottimizzazione):
algoritmi di Kruskal, Prim, Borůvka. [Slide e appunti] [T1] 12 (esclusi 12.2.1 e 12.3.1). |
Festa |
12-18/12/2022 |
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 e Ford per il calcolo delle distanze (descrizione e analisi).
[Slide e appunti] [T1] 13, fino a 13.1.5. |
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.2 - 13.5.1 (escluso) |
| 19-25/12/2022 | Esercizi d'esame. Fine corso. | - |
L'esame prevede (anche per gli iscritti fino all'A.A. 2019-2020 incluso):
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.