Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Complessita'. Problemi e linguaggi. Problemi decisionali e funzionali. Classi di Complessita' in tempo deterministiche: Riassunto dei principali risultati.
COM - Complessita'
Classi non deterministiche e classi in spazio. Principali risultati. Riduzioni, completezza, ed esempi. Teoremi di Cook. NP-completezza di alcuni problemi fondamentali mediante riduzione.
* CAL - Calcolabilita'
Il teorema S-m-n per la While calcolabilita' e gli Specializzatori. Il Teorema di ricorsione di Kleene, il Teorema di Rice e le proprieta' di programmi e il Teorema di Rice-Shapiro. Applicazioni alla programmazione. Riducibilit? funzionale. Studio della relazione. Insiemi ricorsivi e completi. Insiemi creativi e produttivi. Secondo Teorema di Ricorsione e Teorema di Myhill. Insiemi semplici: esistenza di un insieme semplice.
* CAL - Calcolabilita'
Richiamo dei formalismi delle funzioni primitive ricorsive, ricorsive parziali e Macchine di Turing. Equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili. Calcolabilita' e Linguaggi di Programmazione. Il linguaggio While: Sintassi, semantica e funzioni While-calcolabili. Turing completezza del linguaggio While. Il linguaggio For. Equivalenza tra funzioni For-calcolabili e funzioni primitive ricorsive. Indecidibilita' dell'halting problem senza aritmetizzazione.
* ALF - Automi e Linguaggi Formali
Linguaggi liberi dal contesto. Grammatiche libere dal contesto e alberi di derivazione. Grammatiche ambigue. Le forme normali di Chomsky e di Greibach. Il pumping lemma per i linguaggi liberi e le sue applicazioni. Proprieta' di chiusura e di decidibilita' dei linguaggi liberi. Grammatiche lineari destre e sinistre, grammatiche di tipo 0 e 1 e gerarchia di Chomsky.
* ALF - Automi e Linguaggi Formali
Richiami sui linguaggi regolari. Automi a stati finiti deterministici e non-deterministici, e loro equivalenza. Espressioni regolari. Pumping Lemma per i linguaggi regolari e sue applicazioni. Proprieta' di chiusura e di decidibilita' dei linguaggi regolari. Il teorema di Myhill-Nerode; unicita' e determinazione dell'automa minimo.