Algoritmi e Principi dell'Informatica

Docente: Davide Martinenghi
Esercitatore: Nicolò Felicioni

Avvisi

Note generali

Le lezioni e le esercitazioni, oltre che in presenza, saranno anche disponibili in streaming nelle seguenti aule virtuali:

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
22/2/2022 10.15-13.15 26.16 Introduzione al corso. Concetto di alfabeto, linguaggio. Automi a stati finiti.  
23/2/2022 14.15-17.15 T.2.1 Pumping Lemma. Famiglie di linguaggi e chiusura.  
24/2/2022 09.15-11.15 9.1.2 Automi a pila. Proprietà automi a pila.  
1/3/2022 10.15-13.15 26.16 Macchine di Turing.  
2/3/2022 14.15-17.15 T.2.1 Esercitazione. Slide es. FSA
3/3/2022 09.15-11.15 9.1.2 Esercitazione. Slide es. PDA
8/3/2022 10.15-13.15 26.16 Non determinismo. Grammatiche formali. Grammatiche regolari.  
10/3/2022 09.15-11.15 9.1.2 Esercitazione. Slide es. TM
15/3/2022 10.15-13.15 26.16 Grammatiche non contestuali. Grammatiche generali. Espressioni regolari.  
16/3/2022 14.15-17.15 T.2.1 Esercitazione. Slide es. ND
17/3/2022 09.15-11.15 9.1.2 Esercitazione. Slide es. grammatiche
22/3/2022 10.15-13.15 26.16 Tesi di Church. Enumerazioni.  
23/3/2022 14.15-17.15 T.2.1 Macchina di Turing universale. Problemi definibili e calcolabili.  
24/3/2022 09.15-11.15 9.1.2 Esercitazione.  
29/3/2022 10.15-13.15 26.16 Problemi indecidibili. Diagonalizzazione.  
30/3/2022 14.15-17.15 T.2.1 Semidecidibilità. Teorema di Rice. Riduzione di problemi. linee guida su decidibilità
31/3/2022 09.15-11.15 9.1.2 Esercitazione.  
5/4/2022 10.15-13.15 26.16 MFO/MSO. Logica per descrivere proprietà. dispense su MFO/MSO
6/4/2022 14.15-17.15 T.2.1 Esercitazione. Slide es. decidibilità
7/4/2022 09.15-11.15 9.1.2 Esercitazione. Slide es. logica
9/4/2022 09.30-10.30 T.1.x Prima prova in itinere (aule T.1.1, T.1.2 e T.1.3)  
14/4/2022 09.15-11.15 9.1.2 Introduzione alla complessità del calcolo. Analisi asintotica.  
20/4/2022 14.15-17.15 T.2.1 Complessità di automi. Accelerazione lineare. Macchina RAM.  
21/4/2022 09.15-11.15 9.1.2 Esercitazione.  
26/4/2022 10.15-13.15 26.16 Correlazione polinomiale. Algoritmi e pseudocodice. Insertion-sort.  
27/4/2022 14.15-17.15 T.2.1 Ricorrenze. Mergesort. Albero di ricorsione. Metodo della sostituzione.  
3/5/2022 10.15-13.15 26.16 Esercitazione. Slide es. complessità TM e RAM
4/5/2022 14.15-17.15 T.2.1 Teorema dell'esperto. Heapsort.  
5/5/2022 09.15-11.15 9.1.2 Esercitazione.  
10/5/2022 10.15-13.15 26.16 Complessità di Heapsort. Quicksort. Counting sort.  
11/5/2022 14.15-17.15 T.2.1 Pila. Coda. Hashtable.  
12/5/2022 09.15-11.15 9.1.2 Esercitazione. Slide es. complessità e ricorrenze
17/5/2022 10.15-13.15 26.16 Tecniche di ispezione. Alberi binari di ricerca.  
18/5/2022 14.15-17.15 T.2.1 Alberi rosso-neri. Grafi  
19/5/2022 09.15-11.15 9.1.2 Esercitazione. Slide es. algoritmi su array
24/5/2022 10.15-11.15 26.16 Descrizione della prova finale.  
24/5/2022 11.15-13.15 26.16 Argomenti avanzati  
26/5/2022 09.15-11.15 9.1.2 Esercitazione. Appunti es. su BST
31/5/2022 10.15-13.15 26.16 Esercitazione. Slide es. su BST, Slide es. su hash table, Appunti es. alberi
1/6/2022 14.15-17.15 T.2.1 Esercitazione. Appunti es. grafi