Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
La Macchina di Turing. Linguaggi accettati e decisi. Macchine di Turing a più nastri. Macchine di Turing non deterministiche.
* CAL - Calcolabilità
Problemi risolubili algoritmicamente e problemi insolubili: Tesi di Church. La Macchina universale. Il Problema dell'Arresto. Macchine auto-generanti: Teoremi di Turing e Rice. Il Decimo Problema di Hilbert.
* CAL - Calcolabilità
Funzioni Ricorsive Primitive. Funzioni parziali ricorsive
COM - Complessità
Classi di Complessità Temporale. La classe P e la Tesi di Edmonds-Cook-Karp. La classe NP.
COM - Complessità
Il problema P=NP. Problemi NP-completi. Il teorema di Cook-Levin. La gerarchia polinomiale.
COM - Complessità
Complessità spaziale. Le classi L, NL, PSPACE, NPSPACE. Il teorema di Savitch.