Informatica Teorica - Consorzio Nettuno - Polo di Roma

Programma d'esame

Il seguente programma si riferisce al testo di Ausiello G., d'Amore F. e Gambosi G., Linguaggi, modelli, complessità, Franco Angeli Editore.

1. Linguaggi formali e automi Linguaggi.

Operazioni sui linguaggi. Espressioni regolari. Grammatiche di Chomsky. Linguaggi di tipo 0, 1, 2, 3. Linguaggi regolari e automi a stati finiti. Linguaggi non contestuali e automi a pila.

Capitolo 1, Sezione 1.4 ed 1.5 Capitolo 2, tutto Capitolo 3, tutto tranne le dimostrazioni dei teoremi 3.13, 3.14, 3.15, e tranne la Sezione 3.8 Capitolo 4, tutto tranne le dimostrazioni dei teoremi 4.15, 4.16, 4.18, e tranne le Sezioni 4.6 e 4.9

2. Macchine di Turing e calcolabilità secondo Turing

Macchine di Turing. Calcolabilità secondo Turing. Linguaggi e problemi decidibili e semidecidibili. Equivalenza tra linguaggi di tipo 0 e linguaggi semidecidibili. Macchina di Turing universale. Non decidibilità del problema della terminazione. Altri esempi di problemi non decidibili e funzioni non calcolabili.

Capitolo 5, tutto tranne la Sezione 5.11

3. Modelli di calcolo per linguaggi imperativi e funzionali

Le macchine a registri. Equivalenza tra macchine di Turing e macchine e registri. Tesi di Church-Turing. Funzioni ricorsive. Il formalismo di Mc Carthy. Il linguaggio LISP.

Capitolo 6, tutto tranne la Sezione 6.5

Dispensa LISP disponibile nel sito del corso.

4. Complessità di algoritmi e problemi

Complessità di algoritmi. Complessità di problemi e classi di complessità spaziali e temporali. Problemi risolubili in tempo polinomiale e in tempo esponenziale. Modelli di calcolo non deterministici. La classe NP. Problemi NP-difficili ed NP-completi.

Capitolo 8, tutto tranne Sezione 8.4 e tranne le dimostrazioni dei teoremi 8.5 ed 8.6 Capitolo 9, solo le Sezioni 9.1, 9.3, 9.4.