Alfabeti e linguaggi-la classificazione di Chomsky
Automi a stati finiti deterministici e non deterministici-Espressioni regolari
Grammatiche non contestuali-Automi a pila deterministici e non deterministici
La Macchina di Turing-La Macchina di Turing non deterministica-La Macchina di Turing Universale-La macchina RAM-La tesi di Church-Turing-Terminazione di una Macchina di Turing-Classi di Complessità-la classe P-la classe NP-Riduzioni polinomiali-La classe NP-completa
1. G. Ausiello, F. D’Amore, G. Gambosi: Linguaggi Modelli e complessità, Franco Angeli Editore, 2003
2. J. Hopcroft, R. Motawani, J. D. Ullman: Automi Linguaggi e Calcolabilità, Addison Wesley, 2009
3. H. R.Lewis, C. H. Papadimitriou: Elements of The theory of Computation, Prentice-Hall, 1998.
Articoli vari forniti dal docente
Obiettivi Formativi
Il corso si propone di introdurre gli argomenti classici dell’informatica teorica.
Fornire allo studente la comprensione dei necessari collegamenti fra gli aspetti teorici dell’informatica e le problematiche applicative nello sviluppo di sistemi Hardware/software.
Prerequisiti
Conoscenza dei fondamenti della programmazione acquisita normalmente nei corsi di primo livello
Metodi Didattici
Lezioni frontali con esercitazioni
Altre Informazioni
CALENDARIO ESAMI INFORMATICA TEORICA
I Sessione:
- 10 gennaio 2013
- 31 gennaio 2013
- 21 febbraio 2013
II Sessione:
- 13 giugno 2013
- 4 luglio 2013
- 18 luglio 2013
III sessione:
- 5 Settembre 2013
Le date di esame sono vincolanti per l'iscrizione all'esame. Sulla base delle iscrizioni il docente stabilirà il calendario degli orali.
Modalità di verifica apprendimento
Prova orale
Programma del corso
Relazioni e linguaggi: Relazioni, funzioni, insiemi finiti ed infiniti-algoritmi di chiusura-alfabeti e linguaggi-operazioni sui linguaggi-la classificazione di Chomsky
Linguaggi regolari:Automi a stati finiti-Automi a stati finiti non deterministici-Eliminazione del non determinismo-Espressioni regolari e grammatiche regolari.
Linguaggi non contestuali:Grammatiche non contestuali-Proprietà dei linguaggi non contestuali-Forme Normali-Automi a pila-Automi a Pila non deterministici-Le grammatiche LL(k)-Parsing a discesa ricorsiva.
Modelli di calcolo:La Macchina di Turing-La Macchina di Turing non deterministica-La Macchina di Turing Universale-La macchina RAM, analisi della complessità con costi uniformi e logaritmici
Decidibilità e Computabilità:La tesi di Church-Turing-Il problema della terminazione di una Macchina di Turing-Problemi indecidibili.
Complessità computazionale: Classi di Complessità-la classe P-la classe NP-Esempi di problemi-Riduzioni polinomiali-Esempi di riduzioni polinomiali-La classe NP-completa