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 evidenzia, in particolare, l'obbligatorietà del possesso del Green Pass.
Le lezioni saranno fruibili anche da remoto, tramite conferenza Zoom (link).
Non è prevista la registrazione delle lezioni.
| Settimana | Mercoledì | Venerdì |
|---|---|---|
| 27/09-3/10/2021 |
Inizio corso.
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.
Limitazione inferiore e superiore al costo di un algoritmo.
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, 2.3 |
| 4-10/10/2021 |
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. Implementazione in C delle funzioni per il calcolo dei
numeri di fibonacci. [Slide e appunti]. [T1] 2.4 - 2.5.1. Codice. |
Soluzione di equazioni di ricorrenza: metodo dell'iterazione e
metodo della sostituzione.
Principio di induzione matematica ed
esempio di applicazione (formula di Gauss per la somma dei primi n interi).
Cenni all'approccio divide et impera.
Soluzione di equazioni di ricorrenza: teorema Master (senza dimostrazione).
Esempi di applicazione del teorema Master. [Slide e appunti]. [T1] 2.5.1, 2.5.2, 2.5.3 |
| 11-17/10/2021 |
Introduzione ai tipi di dato astratto.
I tipi di dato Dizionario, 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.
Implementazione in C degli algoritmi di ricerca sequenziale e binaria, nelle varianti iterativa e ricorsiva. (Codice). [Slide e appunti] [T1] 3.3, fino a 3.3.3. |
| 18-24/10/2021 |
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 |
| 25-31/10/2021 |
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 |
| 1-7/11/2021 |
Il problema della ricerca.
Alberi binari di ricerca (BST): ricerca, inserimento, cancellazione. Introduzione agli alberi AVL: definizione, analisi della profondità (dimostrazione) [Slide e appunti] [T1] 6.1, 6.2.1. |
Alberi AVL: rotazioni, ricerca, inserimento e cancellazione;
analisi del costo delle operazioni.
Esercizi sugli alberi AVL. [Slide e appunti] [T1] 6.2.2, 6.2.3 |
| 8-14/11/2021 |
Esercizi d'esame su
notazione O-grande, equazioni di ricorrenza,
algoritmi ricorsivi, ordinamento,
costo di MergeSort.
|
Prova Intermedia |
| 15-21/11/2021 |
Tabelle ad accesso diretto. Introduzione alle hash table: generalità,
esempi.
Hash table: uniformità semplice, collisioni;
risoluzione delle collisioni mediante liste di collisione.
[Slide e appunti] [T1] 7.1, 7.2, 7.3.1 |
Hash Table: risoluzione delle collisioni con indirizzamento aperto;
scansione lineare e hashing doppio; costo nel caso peggiore e nel caso medio.
Grafi: generalità e nozioni preliminari.
Strutture dati per la rappresentazione di grafi
(e costo delle operazioni comuni):
liste di archi. [Slide e appunti] [T1] 7.3.2., 11.1 |
| 22-28/11/2021 |
Strutture dati per la rappresentazione di grafi
(e costo delle operazioni comuni):
liste di adiacenza; matrice di adiacenza.
Algoritmi di visita di un grafo: generico, in ampiezza, in profondità (iterativo). [Slide e appunti] [T1] 11.2 - 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.
Implementazione grafo con lista di adiacenza. [Slide e appunti] [T1] 11.4 - 11.5 (fino a 11.5.2 escluso). Codice. |
| 29/11-5/12/2021 |
Minimo albero ricoprente, definizione e proprietà.
Regola del ciclo. Regola del taglio.
Algoritmo generico (dimostrazione di terminazione e correttezza, descrizione e analisi del costo).
[Slide e appunti] [T1] 12.1. |
Calcolo del minimo albero ricoprente:
algoritmi di Kruskal, Prim, Borůvka. 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). [Slide e appunti] [T1] 12, 13 (fino a 13.1.4, escluso). |
| 6-12/12/2021 |
Festa |
Albero dei cammini minimi.
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).
[Slide e appunti] [T1] 13.1.5 - 13.4. |
| 13-19/12/2021 |
Algoritmo di Dijkstra (descrizione e analisi). [Slide e appunti] [T1] 13.5, escluso 13.5.1. Esercizi d'esame. |
Esercizi d'esame. |
| 20-26/12/2021 | (Lezione online) Esercizi d'esame. Fine corso. | - |
L'esame prevede:
(Gli immatricolati fino all'A.A. 19-20 potranno sostenere l'esame da 5 quesiti oppure optare per il progetto e sostenere l'esame da 4).
Le istruzioni per la consegna del progetto sono disponibili qui.
Le date per la discussione del progetto sono indicate insieme agli appelli d'esame.