Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
Grammatiche a struttura di frase e Gerarchia di Chomsky.
* CAL - Calcolabilita'
Insiemi creativi, produttivi e semplici. Riduzioni.
COM - Complessita'
Classi di complessità in tempo e spazio. Riduzioni. P ed NP.
* ALF - Automi e Linguaggi Formali
Linguaggi liberi dal contesto, alberi di derivazione; automi a pila.
* CAL - Calcolabilita'
Esistenza di problemi non decidibili. Problemi semidecidibili.
* ALF - Automi e Linguaggi Formali
Linguaggi regolari, espressioni regolari, automi finiti.
* CAL - Calcolabilita'
Funzioni calcolabili e problemi decidibili.
* CAL - Calcolabilita'
Enumerazione delle funzioni calcolabili, funzione universale. Tesi di Church.
* CAL - Calcolabilita'
Modelli di calcolo: la Macchina di Turing. Halting Problem e Teorema SMN.