Algoritmi e Principi dell'Informatica

Docente: Davide Martinenghi
Esercitatore: Nicolò Felicioni

Avvisi

Prova finale

Materiale

Ricevimento

Venerdì 10:30 - 12:30 previo appuntamento via email.

Esame

Scritto con eventuale discussione orale esclusivamente su richiesta del docente.

Calendario (provvisorio)

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