| Orario | Argomenti | Video | |
|---|---|---|---|
| 25/2/2021 09.15-11.15 | Introduzione al corso. Concetto di alfabeto, linguaggio. | Lezione 1 | |
| 26/2/2021 16.15-19.15 | Automi a stati finiti. Pumping Lemma. | Lezione 2 | |
| 2/3/2021 10.15-13.15 | Esercitazione. | Esercitazione 1: Parte 1, Parte 2 | |
| 3/3/2021 14.15-17.15 | Esercitazione. | Esercitazione 1 | |
| 4/3/2021 09.15-11.15 | Famiglie di linguaggi e chiusura. Automi a pila. | Lezione 3 | |
| 5/3/2021 16.15-19.15 | Proprietà automi a pila. Macchine di Turing. | Lezione 4 | |
| 10/3/2021 14.15-17.15 | Esercitazione online. | Esercitazione 2 | |
| 12/3/2021 16.15-19.15 | Varianti di macchine di Turing. Non determinismo. | Lezione 5 | |
| 16/3/2021 10.15-13.15 | Esercitazione online. | Esercitazione 3 | |
| 18/3/2021 09.15-11.15 | TM non deterministiche. Grammatiche formali. | Lezione 6 | |
| 19/3/2021 16.15-19.15 | Grammatiche regolari e non contestuali. | Lezione 7 | |
| 23/3/2021 10.15-13.15 | Esercitazione online. | Esercitazione 4 | |
| 25/3/2021 09.15-11.15 | Grammatiche generali. | Lezione 8 | |
| 26/3/2021 16.15-19.15 | Espressioni regolari. Ripasso di logica. Logica per descrivere linguaggi. | Lezione 9 | |
| 30/3/2021 10.15-13.15 | Esercitazione online. | Esercitazione 5 | |
| 1/4/2021 09.15-11.15 | MFO/MSO. | Lezione 10 | |
| 7/4/2021 14.15-17.15 | Esercitazione online. | Esercitazione 6: Parte 1, Parte 2 | |
| 8/4/2021 09.15-11.15 | Logica per descrivere proprietà. Tesi di Church. | Lezione 11 | |
| 9/4/2021 16.15-19.15 | Enumerazioni. Macchina di Turing universale. Problemi definibili e calcolabili. | Lezione 12 | |
| 13/4/2021 10.15-13.15 | Esercitazione online. | Esercitazione 7 | |
| 16/4/2021 16.15-19.15 | Problemi indecidibili. Diagonalizzazione. Semidecidibilità. | Lezione 13 | |
| 20/4/2021 10.15-12.15 | Teorema di Rice. Riduzione di problemi. | Lezione 14 | |
| 27/4/2021 10.15-13.15 | Esercitazione. | Esercitazione 8 | |
| 28/4/2021 14.15-17.15 | Esercitazione. | Esercitazione 8 | |
| 29/4/2021 09.15-11.15 | Introduzione alla complessità del calcolo. Analisi asintotica. | Lezione 15 | |
| 30/4/2021 16.15-19.15 | Complessità di automi. Accelerazione lineare. Macchina RAM. Ricerca binaria. Criteri di costo. | Lezione 16 | |
| 4/5/2021 10.15-13.15 | Esercitazione. | Esercitazione 9 | |
| 6/5/2021 09.15-11.15 | Criterio logaritmico. Classe P. Teorema di correlazione polinomiale. | Lezione 17 | |
| 7/5/2021 16.15-19.15 | Ricorrenze. Teorema dell'esperto. | Lezione 18 | |
| 11/5/2021 10.15-13.15 | Esercitazione. | Esercitazione 10 | |
| 13/5/2021 09.15-11.15 | Ordinamento: Insert-sort, Mergesort, Quicksort. | Lezione 19 | |
| 14/5/2021 16.15-19.15 | Complessità di Quicksort. Counting sort. Strutture dati: pila, coda. | Lezione 20 | |
| 18/5/2021 10.15-13.15 | Esercitazione. | Esercitazione 11 | |
| 20/5/2021 09.15-11.15 | Strutture dati lineari, tabelle di hash. | Lezione 21 | |
| 21/5/2021 16.15-19.15 | Efficienza delle tabelle di hash, alberi, alberi rosso-neri. | Lezione 22 | |
| 25/5/2021 10.15-13.15 | Esercitazione. | Esercitazione 12 | |
| 27/5/2021 09.15-11.15 | Cancellazione da alberi rosso-neri. Heap. | Lezione 23 | |
| 28/5/2021 16.15-19.15 | Heapsort, Grafi | Lezione 24 | |
| 1/6/2021 10.15-13.15 | Esercitazione online. | Esercitazione 13 | |
| 3/6/2021 09.15-11.15 | Esercitazione online. | Esercitazione 14 | |