Le lezioni si terranno mercoledì 10.00-13.00 e venerdì 10.00-13.00 in aula 5, presso la sede di Latina, in via A. Doria 3
Le lezioni saranno accessibili tramite conferenza Zoom.
Meeting ID: 891 5486 1466
Passcode: 366983
Cliccare
qui
per accedere da browser (conferenza attiva solo durante l'orario di lezione).
Si potrà assistere alle lezioni anche in diretta streaming Youtube.
Il link per accedere a ciascuna lezione sarà indicato nel
diario delle lezioni.
Lo stesso link permetterà successivamente di accedere
alla registrazione della lezione.
ATTENZIONE: per la registrazione è necessario utilizzare un account Google (non quello Sapienza). Le informazioni associate a tale account (nome, cognome, foto, etc.) saranno visibili a tutti i partecipanti.
| Settimana | Mercoledì | Venerdì |
|---|---|---|
| 5-11/10/2020 |
Inizio corso.
Introduzione agli algoritmi e loro costo. Numeri di Fibonacci [Slide e appunti]. [T1] 1.1-1.4 Link Youtube |
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 Link Youtube |
| 12-18/10/2020 |
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 dell'iterazione. [Slide e appunti]. [T1] 2.4 - 2.5.1 Link Youtube |
Soluzione di equazioni di ricorrenza: metodo della sostituzione.
Principio di induzione matematica ed
esempio di applicazione (formula di Gauss per la somma dei primi n interi).
Strategia Divide et Impera.
Soluzione di equazioni di ricorrenza: teorema Master (senza dimostrazione).
Esempi di applicazione del teorema Master.
Implementazione iterativa in C dell'algoritmo di ricerca binaria
(file). [Slide e appunti]. [T1] 2.5.2, 2.5.3 Link Youtube |
| 19-25/10/2020 |
Introduzione ai tipi di dato astratto.
Il tipo di dato Dizionario, Pila e Coda.
Tecniche di rappresentazione dei dati.
Implementazione indicizzata di Dizionario e
sua realizzazione in C senza ordinamento
(file). [Slide e appunti] [T1] 3.1.1 e 3.2 Link Youtube |
Implementazione collegata di Dizionario senza ordinamento e
sua realizzazione in C.
(file).
Implementazione indicizzata di Pila.
Introduzione al tipo di dato Albero.
[Slide e appunti] [T1] 3.1.2, 3.2, 3.3, fino a 3.3.1 escluso. Link Youtube |
| 26/10-1/11/2020 |
Rappresentazioni indicizzate di alberi: vettore dei padri; vettore posizionale.
Rappresentazioni collegate di alberi: lista di figli;
primo figlio e fratello successivo.
Realizzazione in C del tipo Albero con lista dei figli in
rappresentazione collegata.
Visite di alberi: algoritmo di visita generica, con
dimostrazione di terminazione, costo e correttezza.
[Slide e appunti] [T1] 3.3.1, 3.3.2 Link Youtube |
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 Link Youtube |
| 2-8/11/2020 |
Il problema dell'ordinamento. L'approccio incrementale.
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
SelectionSort, InsertionSort, BubbleSort, Heapsort (prima parte).
[Slide e appunti] [T1] 4.1, 4.2 Link Youtube |
Algoritmi con approccio incrementale (descrizione, pseudocodice, analisi):
HeapSort (seconda parte).
Algoritmi con approccio divide et impera (descrizione, pseudocodice, analisi):
MergeSort.
[Slide e appunti] [T1] 4.3,4.4 Link Youtube |
| 9-15/11/2020 |
Algoritmi con approccio divide et impera (descrizione, pseudocodice, analisi): QuickSort.
Dimostrazione del lower bound per ordinamento basato su confronti.
Esercizi d'esame su costo di MergeSort, notazione O-grande e progetto di funzione ricorsiva
(esame 9/6/2020, es. 1 e 5).
[Slide e appunti] [T1] 4.1, 4.5 Link Youtube |
Algoritmi di ordinamento di interi (descrizione, pseudocodice, analisi):
IntegerSort, BucketSort, RadixSort.
Il problema della ricerca. Introduzione agli alberi binari di ricerca (BST):
ricerca di un elemento. [Slide e appunti] [T1] 4.6, 4.7, 6.1, fino a inserimento escluso. Link Youtube |
| 16-22/11/2020 |
Alberi binari di ricerca (BST): inserimento, cancellazione.
Introduzione agli alberi AVL: definizione, analisi della profondità (dimostrazione)
[Slide e appunti] [T1] 6.1, 6.2.1 Link Youtube |
Alberi AVL: rotazioni, ricerca, inserimento e cancellazione;
analisi del costo delle operazioni. [Slide e appunti] [T1] 6.2.2, 6.2.3 Link Youtube |
| 23-29/11/2020 |
Tabelle ad accesso diretto. Introduzione alle hash table: generalità,
esempi. 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.1, 7.2, 7.3 Link Youtube |
Grafi: generalità e nozioni preliminari.
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.1 - 11.3 Link Youtube |
| 30/11-6/12/2020 |
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. Minimo albero ricoprente, definizione e proprietà. Regola del ciclo. Regola del taglio. Algoritmo generico. Algoritmi per il calcolo del minimo albero ricoprente: algoritmo di Kruskal. [Slide e appunti] [T1] 11.4 - 11.5 (escluso 11.5.2). 12, fino a 12.2 (escluso). Link Youtube |
Algoritmi per il calcolo del minimo albero ricoprente
(dimostrazione di terminazione e correttezza, descrizione e analisi del costo):
algoritmo di Kruskal; algoritmo di Prim; algoritmo di 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.2-12.4, esclusi 12.2.1 e 12.3.1; capitolo 13, fino a 13.1.4 (escluso). Link Youtube |
| 7-13/12/2020 |
Albero dei cammini minimi.
Algoritmo di Bellman e Ford per il calcolo delle distanze (descirizione 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.3 - 13.4. Link Youtube |
Algoritmo di Dijkstra (descrizione e analisi). [Slide e appunti] [T1] 13.5, escluso 13.5.1. Link Youtube |
| 14-20/12/2020 |
Esercizio d'esame 11/02/2020. Link Youtube |
Esercizio d'esame 13/06/2019. Fine corso. (Registrazione non disponibile) |