Docente: Davide Martinenghi
Esercitatore: Nicolò Felicioni
Scritto con eventuale discussione orale esclusivamente su richiesta del docente.
Orario | Aula | Argomenti | Materiale extra |
---|---|---|---|
21/2/2023 10.15-13.15 | 2.0.1 | Introduzione al corso. Concetto di alfabeto, linguaggio. Automi a stati finiti. | |
22/2/2023 14.15-17.15 | 6.0.1 | Pumping Lemma. Famiglie di linguaggi e chiusura. | |
23/2/2023 09.15-11.15 | T.1.3 | Automi a pila. Proprietà automi a pila. | |
28/2/2023 10.15-13.15 | 2.0.1 | Macchine di Turing. | |
1/3/2023 14.15-17.15 | 6.0.1 | Esercitazione. | Slide es. FSA |
2/3/2023 09.15-11.15 | T.1.3 | Esercitazione. | Slide es. PDA |
7/3/2023 10.15-13.15 | 2.0.1 | Non determinismo. Grammatiche formali. Grammatiche regolari. | |
9/3/2023 09.15-11.15 | T.1.3 | Esercitazione. | Slide es. TM |
14/3/2023 10.15-13.15 | 2.0.1 | Grammatiche non contestuali. Grammatiche generali. | |
15/3/2023 14.15-17.15 | 6.0.1 | Esercitazione. | Slide es. ND |
16/3/2023 09.15-11.15 | T.1.3 | Esercitazione. | |
21/3/2023 10.15-13.15 | 2.0.1 | Espressioni regolari. Tesi di Church. Enumerazioni. | |
22/3/2023 14.15-17.15 | 6.0.1 | Macchina di Turing universale. Problemi definibili e calcolabili. | |
23/3/2023 09.15-11.15 | T.1.3 | Problemi indecidibili. Diagonalizzazione. | |
28/3/2023 10.15-13.15 | 2.0.1 | Esercitazione. | Slide es. grammatiche |
29/3/2023 14.15-17.15 | 6.0.1 | Semidecidibilità. Teorema di Rice. Riduzione di problemi. | linee guida su decidibilità |
30/3/2023 09.15-11.15 | T.1.3 | Esercitazione. | |
4/4/2023 10.15-13.15 | 2.0.1 | MFO/MSO. Logica per descrivere proprietà. | dispense su MFO/MSO |
5/4/2023 14.15-17.15 | 6.0.1 | Esercitazione. | Slide es. decidibilità |
6/4/2023 09.15-11.15 | T.1.3 | Esercitazione. | Slide es. logica |
12/4/2023 14.15-17.15 | 6.0.1 | Introduzione alla complessità del calcolo. Analisi asintotica. | |
13/4/2023 09.15-11.15 | T.1.3 | Esercitazione. | |
18/4/2023 10.15-13.15 | 2.0.1 | Complessità di automi. Accelerazione lineare. Macchina RAM. | |
21/4/2022 09.30-10.45 | n.d. | Prima prova in itinere | |
26/4/2023 14.15-17.15 | 6.0.1 | Correlazione polinomiale. Algoritmi e pseudocodice. Insertion-sort. | |
27/4/2023 09.15-11.15 | T.1.3 | Ricorrenze. Mergesort. Albero di ricorsione. Metodo della sostituzione. | |
2/5/2023 10.15-13.15 | 2.0.1 | Esercitazione. | Slide es. complessità TM e RAM |
9/5/2023 10.15-13.15 | 2.0.1 | Teorema dell'esperto. Heapsort. | |
10/5/2023 14.15-17.15 | 6.0.1 | Complessità di Heapsort. Quicksort. Counting sort. | |
11/5/2023 09.15-11.15 | T.1.3 | Esercitazione. | |
16/5/2022 10.15-13.15 | 2.0.1 | Pila. Coda. Hashtable. | |
17/5/2023 14.15-17.15 | 6.0.1 | Tecniche di ispezione. Alberi binari di ricerca. | |
18/5/2023 09.15-11.15 | T.1.3 | Esercitazione. | Slide es. complessità e ricorrenze |
23/5/2023 10.15-13.15 | 2.0.1 | Alberi rosso-neri. Grafi | |
24/5/2023 14.15-16.15 | 6.0.1 | Argomenti avanzati | |
25/5/2023 09.15-11.15 | T.1.3 | Esercitazione. | Slide es. algoritmi su array |
30/5/2023 10.15-11.15 | 2.0.1 | Descrizione della prova finale. | |
30/5/2023 11.15-13.15 | 2.0.1 | Esercitazione. | Appunti es. su BST |
31/5/2023 14.15-17.15 | 6.0.1 | Esercitazione. | Slide es. su BST, Slide es. su hash table, Appunti es. alberi |
1/6/2023 09.15-11.15 | T.1.3 | Esercitazione. | Appunti es. grafi |