Calendario delle lezioni
Per i calendari delle lezioni degli a.a. precedenti si veda questa pagina
Per i calendari delle lezioni relative alla programmazione C si vedano le informazioni fornite dal prof. Franceschini su questo sito.
Simulazione lezione
18 febbraio 2021, simulazione svolta interamente a distanza.
19 studenti partecipanti
Argomenti:
Verifica delle funzionalità
Presentazione sintetica dati OPIS 2019/20
Link alla dispensa Powerpoint:
Link alla lezione registrata:
Lezioni 1-2
24 febbraio 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 21
A distanza, studenti partecipanti: 57
Argomenti:
Presentazione del corso
Introduzione
concetti di algoritmo, struttura dati, efficienza, costo computazionale
modello del calcolatore
criteri di costo uniforme e logaritmico
Link alle dispense:
01_Introduzione.pptx (slide 1-27)
Link alla lezione registrata:
Lezioni 3-4
25 febbraio 2021 ore 14:00-16:00, lezioni svolte in modalità mista:
In Aula II Matematica, studenti presenti: 12
A distanza, studenti partecipanti: 52
Argomenti:
Esempio di applicazione dei criteri di costo uniforme e logaritmico
Notazione asintotica (1)
Definizione e significato degli insiemi O, Ω e Θ
Esempi
Algebra della notazione asintotica
Esempi
Metodo del limite
Esercizi assegnati
Dimostrare le regole relative all'algebra della notazione asintotica che non sono state dimostrate a lezione
Calcolare l'ordine asintotico stretto di alcune funzioni assegnate
Link alle dispense:
01_Introduzione.pptx (slide 28-30)
Link alla lezione registrata:
Lezioni 5-6
1 marzo 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 12
A distanza, studenti partecipanti: 50
Argomenti:
Notazione asintotica (2)
Valutazione del costo computazionale di un algoritmo
Pseudocodice
Un primo esempio: costo computazionale di un programma che trova il massimo in un vettore
Esempi di problemi che si possono risolvere in modo più o meno efficiente e loro costo computazionale
Somma dei primi n interi
Valutazione di un polinomio in un punto
Link alle dispense:
Link alla lezione registrata:
Lezioni 7-8
3 marzo 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 13
A distanza, studenti partecipanti: 53
Argomenti:
Il problema della ricerca
Ricerca sequenziale e suo costo computazionale nel caso migliore, peggiore e medio
Ricerca binaria e suo costo computazionale nel caso migliore, peggiore e medio
La Ricorsione (1)
Funzioni matematiche ricorsive
Algoritmi ricorsivi: aspetti principali
Ricerca sequenziale: pseudocodice ricorsivo
Ricerca binaria: pseudocodice ricorsivo
Link alle dispense:
05_Ricorsione.pptx (slide 1-15)
Link alla lezione registrata:
Lezione 8 marzo 2021 annullata
La lezione dell'8 marzo 2021 è stata annullata per l'impossibilità (a causa del malfunzionamento del sistema Sapienza di autenticazione dei docenti) di aprire dall'aula V di Matematica la sessione Zoom per gli studenti a distanza.
Lezioni 9-10
10 marzo 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 14
A distanza, studenti partecipanti: 35
Argomenti:
La Ricorsione (2)
Calcolo dei numeri di Fibonacci
Esercizi svolti
esercizi su vettori
torri di Hanoi
Soluzioni delle equazioni di ricorrenza (1)
metodo iterativo; esempi
Link alle dispense:
05_Ricorsione.pptx (slide 16-35)
06_Equazioni_Ricorrenza.pptx (slide 1-12)
Link alla lezione registrata:
Lezioni 11-12
15 marzo 2021 ore 11:00-13:00, lezioni svolte esclusivamente a distanza.
Studenti partecipanti: 51
Argomenti:
Soluzioni delle equazioni di ricorrenza (2)
maggiorazione e minorazione del costo per il calcolo dei numeri di Fibonacci col metodo iterativo
metodo di sostituzione; esempi
metodo dell'albero; esempi
metodo del teorema principale (senza dimostrazione); esempi
Esercizi assegnati (contenuti nelle slide della lezione)
Link alle dispense:
06_Equazioni_Ricorrenza.pptx (slide 13-37)
Link alla lezione registrata:
Lezioni 13-14
17 marzo 2021 ore 9:00-11:00, lezioni svolte esclusivamente a distanza.
Studenti partecipanti: 46
Argomenti:
Esercizi sulle equazioni di ricorrenza svolti in classe
Link alle dispense:
07_Esercizi_EquazRicorr.pptx (slide 1-53)
Link alla lezione registrata:
Lezioni 15-16
22 marzo 2021 ore 11:00-13:00, lezioni svolte esclusivamente a distanza.
Studenti partecipanti: 46
Argomenti:
Esercizi svolti in classe: dallo pseudocodice all'equazione di ricorrenza
Il problema dell'ordinamento (1)
introduzione al problema dell'ordinamento
algoritmo Insertion sort
algoritmo Selection sort
algoritmo Bubble sort
limite inferiore al costo computazionale
esercizi assegnati (contenuti nelle slide della lezione)
Link alle dispense:
07_Esercizi_EquazRicorr.pptx (slide 54-58)
Link alla lezione registrata:
Lezioni 17-18
24 marzo 2021 ore 9:00-11:00, lezioni svolte esclusivamente a distanza.
Studenti partecipanti: 41
Argomenti:
Il problema dell'ordinamento (2)
algoritmo Mergesort e suo costo computazionale
esercizi svolti (contenuti nelle slide della lezione)
esercizi assegnati (contenuti nelle slide della lezione)
Link alle dispense:
Link alla lezione registrata:
Lezioni 19-20
29 marzo 2021 ore 11:00-13:00, lezioni svolte esclusivamente a distanza.
Studenti partecipanti: 38
Argomenti:
Il problema dell'ordinamento (3)
algoritmo Quicksort
costo computazionale del quicksort nel caso migliore, peggiore e medio (con dimostrazione)
esercizio svolto (contenuto nelle slide della lezione)
esercizi assegnati (contenuti nelle slide della lezione)
Soluzione degli esercizi proposti nelle lezioni 15-16 del 22 marzo 2021 (ordinamenti semplici)
Link alle dispense:
Link alla lezione registrata:
https://drive.google.com/file/d/1GCjp2ymyjba-dl5S1IHpPofA85gas6jL/view?usp=sharing - ATTENZIONE: la registrazione è congelata dal minuto 49:23 al minuto 51:02 a causa della caduta del collegamento di rete fissa e del conseguente ricollegamento tramite la rete cellulare.
Lezioni 21-22
31 marzo 2021 ore 9:00-11:00, lezioni svolte esclusivamente a distanza.
Studenti partecipanti: 34
Argomenti:
Il problema dell'ordinamento (4)
struttura dati Heap
funzioni Heapify e Buildheap
algoritmo Heapsort (pseudocodice, esempio e costo computazionale)
esercizi assegnati (contenuti nelle slide della lezione)
Link alle dispense:
Link alla lezione registrata:
1-6 aprile 2021: Vacanze di Pasqua
Lezioni 23-24
7 aprile 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 8
A distanza, studenti partecipanti: 32
Argomenti:
Il problema dell'ordinamento (5)
algoritmi di ordinamento lineari
Counting sort (pseudocodice e costo computazionale)
Counting sort con dati satellite (pseudocodice e costo computazionale)
Bucket sort (descrizione generale dell'algoritmo)
esercizi assegnati (contenuti nelle slide della lezione)
Soluzione di alcuni degli esercizi proposti nelle lezioni 17-18 del 24 marzo 2021 (Mergesort)
Link alle dispense:
Link alla lezione registrata:
Lezioni 25-26
12 aprile 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 5
A distanza, studenti partecipanti: 31
Argomenti:
Strutture dati fondamentali (1)
insiemi dinamici ed operazioni su di essi
implementazione di un insieme dinamico su un vettore non ordinato
implementazione di un insieme dinamico su un vettore ordinato
la struttura dati lista
operazioni elementari su liste: scorrimento, ricerca, inserimento in testa, eliminazione
la struttura dati lista doppiamente puntata
eliminazione di un elemento dalla lista doppiamente puntata
Esercizi assegnati (contenuti nelle slide della lezione)
Soluzione degli esercizi proposti nelle lezioni 21-22 del 31 marzo 2021 (Heapsort)
Link alle dispense:
Link alla lezione registrata:
Lezioni 27-28
14 aprile 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 7
A distanza, studenti partecipanti: 26
Argomenti:
Strutture dati fondamentali (2)
la struttura dati coda e le operazioni enqueue e dequeue
la struttura dati coda con priorità e le operazioni enqueue e dequeue
la struttura dati pila e le operazioni push e pop
funzionamento della pila di sistema (system stack) per la gestione delle chiamate di funzione
Esercizio svolto in classe:
Simulare il comportamento di una coda mediante l'uso di due pile
Esercizi assegnati (contenuti nelle slide della lezione)
Soluzione degli esercizi proposti nelle lezioni 23-24 del 7 aprile 2021 (Counting sort e Bucket sort)
Link alle dispense:
Link alla lezione registrata:
Lezioni 29-30
19 aprile 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 1
A distanza, studenti partecipanti: 29
Argomenti:
Soluzione degli esercizi proposti nelle lezioni 19-20 del 29 marzo 2021 (Quicksort)
Soluzione degli esercizi proposti nelle lezioni 25-26 del 12 aprile 2021 (Liste)
Strutture dati fondamentali (3)
Alberi (1)
definizione tramite la nozione di grafo
caratterizzazione degli alberi
alberi binari completi: relazione tra altezza e numero di nodi
Link alle dispense:
Link alla lezione registrata:
Lezioni 31-32
21 aprile 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 7
A distanza, studenti partecipanti: 26
Argomenti:
Strutture dati fondamentali (4)
Alberi (2)
memorizzazione degli alberi:
tramite record e puntatori
posizionale
tramite vettore dei padri
visite di alberi: inordine, preordine e postordine
pseudocodice ricorsivo
costo computazionale tramite equazione di ricorrenza e metodo di sostituzione
Esercizi svolti in classe: applicazioni delle visite
Esercizi assegnati (contenuti nelle slide della lezione)
Link alle dispense:
15_Alberi.pptx (slide 19-30)
Link alla lezione registrata:
Lezioni 33-34
26 aprile 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 3
A distanza, studenti partecipanti: 26
Argomenti:
Rivisitazione di un esercizio proposto nelle lezioni 25-26 del 12 aprile 2021 (Liste)
Soluzione degli esercizi proposti nelle lezioni 27-28 del 14 aprile 2021 (Code e Pile)
Soluzione degli esercizi proposti nelle lezioni 31-32 del 21 aprile 2021 (Alberi e visite)
Link alle dispense:
13.1_Soluzioni_esercizi_liste.pptx (slide 20-26)
Link alla lezione registrata:
Lezioni 35-36
28 aprile 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 4
A distanza, studenti partecipanti: 30
Argomenti:
Dizionari (1)
definizione di dizionario e problematiche associate
tabelle ad indirizzamento diretto
tabelle hash
il problema delle collisioni
soluzione al problema delle collisioni tramite liste di trabocco
soluzione al problema delle collisioni tramite indirizzamento aperto
scansione lineare
scansione quadratica
hashing doppio
Link alle dispense:
Link alla lezione registrata:
Lezioni 37-38
3 maggio 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 9
A distanza, studenti partecipanti: 20
Argomenti:
Dizionari (2)
alberi binari di ricerca (1)
definizione
algoritmo di ricerca e suo costo computazionale
algoritmi di ricerca del massimo, minimo, successore e predecessore e loro costo computazionale
algoritmo di inserimento e suo costo computazionale
algoritmo di cancellazione e suo costo computazionale
esercizi svolti in classe (contenuti nelle slide della lezione)
esercizi assegnati (contenuti nelle slide della lezione)
Link alle dispense:
Link alla lezione registrata:
Lezioni 39-40
5 maggio 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula Picone Matematica, studenti presenti: 11
A distanza, studenti partecipanti: 20
Argomenti:
Dizionari (3)
alberi binari di ricerca (2)
alberi Red-Black
definizione
dimostrazione dell'altezza logaritmica
introduzione ai meccanismi di ribilanciamento: cambi di colore e rotazioni
pseudocodice della rotazione sinistra
rotazioni: casi 1, 2 e 3
esercizi assegnati (contenuti nelle slide della lezione)
Link alle dispense:
Link alla lezione registrata:
Lezioni 41-42
10 maggio 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 7
A distanza, studenti partecipanti: 21
Argomenti:
Soluzione degli esercizi proposti nelle lezioni 37-38 del 3 maggio 2021 (Alberi binari di ricerca)
Soluzione degli esercizi proposti nelle lezioni 39-40 del 5 maggio 2021 (Alberi Red-Black)
Compilazione in aula dei questionati OPIS
Link alle dispense:
Link alla lezione registrata:
Lezioni 43-44
12 maggio 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 15
A distanza, studenti partecipanti: 8
Argomenti:
Grafi (1)
definizione di grafo, grafo diretto, grafo pesato
definizione di passeggiata, cammino, cammino semplice
definizione di circuito e ciclo
relazione di raggiungibilità e sue caratteristiche
definizione di componente connessa
definizione di sottografo, sottografo indotto, sottografo ricoprente
rappresentazioni in memoria
liste di adiacenza
matrice di adiacenza
matrice di incidenza
lista di archi
confronto del costo computazionale spaziale e temporale per alcune operazioni elementari
esercizi assegnati (contenuti nelle slide della lezione)
Link alle dispense:
Link alla lezione registrata:
Lezioni 45-46
17 maggio 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 6
A distanza, studenti partecipanti: 18
Argomenti:
Grafi (2)
aspetti generali delle visite
differenza concettuale fra visita in ampiezza e visita in profondità
implementazioni possibili: iterativa (tramite coda o pila) e ricorsiva (solo per visita in profondità)
definizione di albero di visita
archi dell'albero e archi non dell'albero
Visita in ampiezza (1)
pseudocodice della visita in ampiezza
esempio di funzionamento della visita in ampiezza
costo computazionale della visita in ampiezza
Link alle dispense:
21_Grafi2_Visite.pptx (slide 1-18)
Elenco n.1 degli esercizi che verranno illustrati a lezione (problemi tratti da compiti scritti svolti totalmente in presenza)
Elenco n. 2 degli esercizi che verranno illustrati a lezione (problemi tratti da compiti scritti svolti totalmente a distanza)
Link alla lezione registrata:
https://drive.google.com/file/d/1fpJcqNH2V88dyFIsZF5pyyxYPfweAZra/view?usp=sharing - ATTENZIONE: alle ore 12:20:28 e 12:25:50 l'aula ha perso la connessione Internet per circa un minuto, per cui io ho perso il collegamento con la sessione Zoom e la registrazione si è congelata, per riprendere appena la connessione Internet si è ristabilita. Mi scuso per l'inconveniente, che non è dipeso dalla mia volontà.
Lezioni 47-48
19 maggio 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 4
A distanza, studenti partecipanti: 25
Argomenti:
Grafi (3)
Visita in ampiezza (2)
proprietà degli archi non dell'albero
proprieta' della distanza dalla radice
Visita in profondità
pseudocodice della visita in profondità
costo computazionale della visita in profondità
proprietà degli archi non dell'albero
relazione fra lunghezza dei cammini e numero di archi del grafo
Somiglianze fra le visite
esercizi assegnati (contenuti nelle slide della lezione)
Soluzione degli esercizi proposti nelle lezioni 43-44 del 12 maggio 2021 (Grafi)
Link alle dispense:
21_Grafi2_Visite.pptx (slide 19-38)
Link alla lezione registrata:
Lezioni 49-50
24 maggio 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 2
A distanza, studenti partecipanti: 23
Argomenti:
Soluzione degli esercizi proposti nelle lezioni 47-48 del 19 maggio 2021 (Visite di grafi)
Grafi (4)
algoritmo di Dijkstra (1)
la rete Internet è modellata come un grafo pesato sul quale individuare i cammini di costo minimo
cenni storici sull'evoluzione del sistema telefonico e della rete Internet
commutazione di circuito vs commutazione di pacchetto
cenni sul funzionamento store-and-forward dei router
fenomeni che possono modificare i cammini minimi: caduta di linee o di router, congestione
Link alle dispense:
Link alla lezione registrata:
Lezioni 51-52
26 maggio 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 4
A distanza, studenti partecipanti: 24
Argomenti:
Grafi (5)
algoritmo di Dijkstra (2)
descrizione introduttiva dell'algoritmo di Dijkstra
pseudocodice dell'algoritmo
esempio dettagliato di funzionamento su un grafo pesato
costo computazionale dell'algoritmo in funzione dell'implementazione della coda con priorità
dimostrazione per induzione della correttezza dell'algoritmo
Link alle dispense:
22_Dijkstra.pptx (slide 23-43)
Link alla lezione registrata:
Lezioni 53-54
31 maggio 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 3
A distanza, studenti partecipanti: 20
Argomenti:
Soluzione di esercizi tratti da vecchi compiti (prima parte)
Link alle dispense:
Link alla lezione registrata:
https://drive.google.com/file/d/1qNewH6liS8OmWLylgDA0qME7Pw_PQtJs/view?usp=sharing - ATTENZIONE: anche oggi purtroppo, alle ore 11:34:44, l'aula ha perso la connessione Internet, per cui io ho perso il collegamento con la sessione Zoom e la registrazione si è temporaneamente congelata per circa un minuto.
Lezioni 55-56
7 giugno 2021 ore 11:00-13:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 3
A distanza, studenti partecipanti: 18
Argomenti:
Soluzione di esercizi tratti da vecchi compiti (seconda parte)
Link alle dispense:
Link alla lezione registrata:
https://drive.google.com/file/d/1t9Xufef3iUCad9LXLUrQFr0a4PgsMoks/view?usp=sharing
Lezioni 57-58
9 giugno 2021 ore 9:00-11:00, lezioni svolte in modalità mista:
In Aula V Matematica, studenti presenti: 10
A distanza, studenti partecipanti: 5
Argomenti:
Assegnazione di un esercizio da risolvere in classe per autovalutazione
Link alle dispense:
Link alla lezione registrata:
https://drive.google.com/file/d/1bcMp19X9HRYHPenbci5J1itteRnDSAfk/view?usp=sharing ATTENZIONE: andate direttamente al minuto 2 e 26 secondi della registrazione perché inizialmente avevo il microfono spento.
Lezioni 59-60
14 giugno 2021 ore 11:00-13:00, lezioni svolte a distanza:
Studenti partecipanti:
Argomenti:
Simulazione di esame scritto a distanza a canali congiunti (mediante uso di Zoom e del software Exam.net e SEB)
ATTENZIONE:
tutti gli studenti che hanno richiesto l'esame a distanza saranno invitati, individualmente tramite mail
i docenti NON saranno in aula
leggere attentamente le istruzioni e prepararsi con tutti i dispositivi e il software necessario