Algoritmi e Principi dell'Informatica

Registrazioni delle lezioni dell'A.A. 2021/2022

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