Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Teorema di Cook; esempi di problemi NP-completi.
COM - Complessita'
Classi naturali di complessità e relazioni di inclusione.
* CAL - Calcolabilita'
Problemi decidibili e semidecidibili; riducibilità tra problemi; TM universale; proprietà di chiusura dei linguaggi (semi)decidibili.
* CAL - Calcolabilita'
TM (Turing Machine), RAM (Random Access Machine); funzioni calcolabili; Tesi di Church e tesi di Church estesa.
* ALF - Automi e Linguaggi Formali
Bisimulazione, congruenza osservazionale, altre congruenze.
* ALF - Automi e Linguaggi Formali
Sistemi di transizione e algebre di processi.
* ALF - Automi e Linguaggi Formali
Automi a stati finiti: linguaggi regolari.
V - Varie
Sistemi di riscrittura.
V - Varie
Lambda-calcolo.