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:

  • Parte_1 (12 min, senza riquadro oratore);

  • Parte 2 (2 min, con riquadro oratore)

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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