Parte I Linguaggi Regolari e Automi a Stati Finiti
- Introduzione e Preliminari matematici
- Automi a Stati Finiti
- Operazioni di Chiusura di Linguaggi Regolari
- Nondeterminismo I parte
- Nondeterminismo II parte
- Espressioni Regolari
- Pumping Lemma
Parte II Linguaggi Liberi e Automi a Pila
- Grammatiche Context-Free
- Ambiguità e Forma Normale di Chomsky
- Automi a Pila
- PDA=CFG
- Problemi su PDA, CFG, CFL
Parte III Calcolabilità
- Macchine di Turing
- Varianti di MdT
- Nondeterminismo
- Tesi di Church
- Decidibilità
- Enumerabilità e Diagonalizzazione
- Indecidibilità
- Indecidibilità e Linguaggi
- Riducibilità
Parte IV Introduzione alla Teoria della Complessità
- Misure di complessità algoritmica
- La classe P
- La classe NP
- NP-Completezza
- Problemi NP-completi
- Complessità di Spazio e Teorema di Savitch
- Teacher: NICOLA GALESI