Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
Automi a stati finiti e non determinismo.
* ALF - Automi e Linguaggi Formali
Espressioni regolari , linguaggi non regolari. Grammatiche libere dal contesto.
* ALF - Automi e Linguaggi Formali
Automi a pila. Linguaggi non liberi dal contesto.
* CAL - Calcolabilita'
Macchine di Turing e loro varianti, concetto di algoritmo.
* CAL - Calcolabilita'
Decidibilita': linguaggi decidibili, il problema dell'alt.
* CAL - Calcolabilita'
Riducibilita': esempi di problemi indecidibili
COM - Complessita'
La classe P, la classe NP.
COM - Complessita'
NP completezza.
COM - Complessita'
Teorema di Savitch, la classe PSPACE.