Algoritmi e Principi dell'Informatica 2011-12 (modulo di Informatica Teorica)

Docente della parte di Informatica Teorica: Davide Martinenghi
Docente della parte di Informatica 3: Alessandro Campi
Esercitatore: Luigi Drago

Avvisi

Esame del 20/02/2012. Vedi: testo e soluzioni, voti. Visione compiti: 28/2/2012 alle 10.
Prova in itinere del 24/1/2012. Vedi: testo e soluzioni, voti.
Prova in itinere del 18/11/2011. Vedi: testo e soluzioni, voti.

Programma della parte di informatica teorica

I modelli dell'informatica
- Automi (a stati finiti, a pila, Macchine di Turing)
- Grammatiche
- Modelli non-deterministici (automi, reti di Petri)
- Uso della logica matematica per modellare sistemi e descriverne proprietà
Teoria della computazione
- Potenza dei modelli di calcolo
- Tesi di Church
- Problemi indecidibili
- Tecniche di dimostrazione di indecidibilità

Materiale per la parte di informatica teorica

Libro di testo: Informatica Teorica. Mandrioli, Spoletini, Informatica teorica (II edizione) De Agostini, 2011.
Eserciziario: Esercizi di Informatica Teorica (terza edizione). D. Mandrioli et al. Esculapio.
Le slide delle lezioni in inglese saranno aggiunte di volta in volta.
- Linguaggi formali e automi a stati finiti
- Automi a pila
- Introduzione alla logica
- Macchine di Turing
- Non-determinismo
- Grammatiche formali
- Espressioni regolari
- Logica per descrivere linguaggi, proprietà e sistemi
- Reti di Petri. Vedi anche esempi animati e una applet per costruirle.
- Computabilità
Vecchio materiale fornito as is:
- Vecchie slide delle lezioni in italiano: pdf.
- Vecchie slide delle esercitazioni: zip.
- Temi d'esame del corso API 2010-2011: zip.
- Temi d'esame del vecchio corso di Informatica Teorica: zip.

Ricevimento

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

Esame

Scritto con eventuale discussione orale su richiesta del docente. Durante il corso verranno anche svolte due prove in itinere (una di informatica teorica e una di informatica 3), a partecipazione facoltativa.

Calendario per la parte di informatica teorica

#	Orario	Argomenti	Aula
1	29/9/2011 14.15-17.15	Introduzione. Alfabeto, linguaggi, operazioni sui linguaggi. Automi a stati finiti come accettori di linguaggi.	N1.3
2	3/10/2011 14.15-17.15	Automi a stati finiti come traduttori. Linguaggi regolari. Automi a pila.	F0.1
3	3/10/2011 17.15-18.15	Esercizi su automi a stati finiti.	F0.1
4	6/10/2011 14.15-17.15	Proprietà automi a pila. Ripasso di logica.	N1.3
5	10/10/2011 14.15-17.15	Macchine di Turing. Non-determinismo negli automi a stati finiti.	F0.1
6	10/10/2011 17.15-19.15	Esercizi su automi a stati finiti e automi a pila.	F0.1
7	11/10/2011 15.15-18.15	Non-determinismo nelle macchine di Turing e negli automi a pila. Grammatiche formali.	N1.1
8	13/10/2011 14.15-17.15	Esercizi su automi a pila e macchine di Turing.	N1.3
9	17/10/2011 14.15-17.15	Grammatiche non ristrette. Espressioni regolari. Logica per descrivere linguaggi e proprietà.	F0.1
	17/10/2011 17.15-19.15	Lezione di informatica 3	F0.1
10	18/10/2011 15.15-18.15	Logica per descrivere sistemi. Reti di Petri.	N1.1
11	20/10/2011 14.15-17.15	Enumerazioni. Macchina di Turing universale. Problemi definibili e calcolabili.	N1.3
	24/10/2011 14.15-16.15	Lezione di informatica 3	F0.1
12	24/10/2011 16.15-19.15	Esercizi su macchine di Turing e grammatiche.	F0.1
13	25/10/2011 15.15-18.15	Esercizi su grammatiche, espressioni regolari, logica.	N1.1
14	27/10/2011 14.15-17.15	Problemi indecidibili. Diagonalizzazione.	N1.3
15	3/11/2011 14.15-17.15	Esercizi su reti di Petri e linguaggi. Esercizi su computabilità.	N1.3
16	7/11/2011 15.30-18.15	Esercizi su computabilità. Temi d'esame	F0.1
17	8/11/2011 15.15-18.15	Semidecidibilità. Teoremi di Kleene e di Rice. Riduzione di problemi.	N1.1
18	22/11/2011 15.15-18.15	Esercizi su computabilità. Temi d'esame	N1.1