Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
Funzioni calcolabili e problemi decidibili. Esistenza di problemi indecidibili. Linguaggi riconosciuti da macchine di Turing. Generalizzazioni e restrizioni della macchina di Turing. Linguaggi riconosciuti dai diversi modelli di automi.
* ALF - Automi e Linguaggi Formali
Sistemi di riscrittura. Grammatiche. Linguaggi generati da grammatiche. La gerarchia di Chomsky e sue relazioni con la classificazione degli automi. Equivalenza tra grammatiche (generali) e macchine di Turing. Equivalenza tra Grammatiche Lineari Destre (o Lineari Sinistre) e FSA. Grammatiche Noncontestuali, o Context-Free (CF). Linguaggi generati da grammatiche CF. Albero Sintattico (o di Derivazione). Ambiguità nelle grammatiche e nei linguaggi CF. Forme Normali di Chomsky e di Greibach.
* ALF - Automi e Linguaggi Formali
Equivalenza tra grammatiche CF e automi a pila (PDA). Esempio delle espressioni in forma polacca. Lemma d'iterazione per i linguaggi CF. Esempi di linguaggi che non sono generati da grammatiche CF. Propriet? di chiusura per la famiglia dei linguaggi CF. Problemi de decisione per i linguaggi CF. Cenni sull'analisi sintattica.
* ALF - Automi e Linguaggi Formali
Automi a Stati Finiti (FSA) e linguaggi riconosciuti da FSA. Rappresentazione di un FSA col grafo degli stati. Lemma d'iterazione. Esempi di linguaggi non riconosciuti da FSA. Automi Finiti Deterministici (DFA) e Nondeterministici (NFA). Equivalenza tra NFA e DFA. Subset Construction. Applicazioni: algoritmi di string-matching. FSA con epsilon-transizioni. Proprietà di chiusura della famiglia dei linguaggi riconosciuti da FSA. Linguaggi ed Espressioni Regolari.
* ALF - Automi e Linguaggi Formali
Teorema di Kleene. Algoritmi per convertire un'espressione regolare in un DFA e viceversa. FSA bidirezionali (2-FSA).
* ALF - Automi e Linguaggi Formali
Equivalenza tra 2-DFA e 1-DFA (Teorema di Rabin-Shepherdson). Problemi di decisione per i linguaggi riconosciuti da FSA. Equivalenza e minimizzazione di FSA.
* CAL - Calcolabilita'
Nozione di calcolabilità. Enunciato e discussione della tesi di Church-Turing. Primi esempi di funzioni Turing-calcolabili. Definizione di produttività di una Macchina di Turing (MdT). Definizione della funzione p (produttività massima delle MdT a n stati). Dimostrazione della non Turing calcolabilità della funzione p. Le funzioni ricorsive primitive. Costruzione della funzione di Ackermann. Definizione di funzione epsilon-ricorsiva e µ-ricorsiva. Le funzioni ricorsive primitive (r.p.). Metodi di codifica ricorsivi primitivi. Numeri di Godel. Il linguaggio di programmazione S di Davis/Weyuker. Calcolabilità in S delle funzioni r.p. Il teorema della "fermata". Esistenza di programmi "universali". Insiemi ricorsivamente enumerabili (r.e.) e di insiemi ricorsivi.
* CAL - Calcolabilita'
Relazioni intercorrenti tra insiemi r.e. e insiemi ricorsivi. Il teorema di Post. Dimostrazione dell'esistenza di insiemi r.e ma non ricorsivi. Il teorema del parametro di Kleene. Il linguaggio di programmazione LOOP di Meyer e Ritchie. LOOP-calcolabilità delle funzioni r.p.. Equivalenza tra funzioni r.p. e funzioni LOOP-calcolabili. Profondità di nidificazione dei cicli LOOP. La gerarchia Ln. Non ricorsività primitiva della funzione di Ackermann. Calcolabilità in S della funzione di Ackermann. Introduzione del linguaggio WHILE come estensione del linguaggio LOOP. Dimostrazione della equivalenza tra il linguaggio S e il linguaggio WHILE.
COM - Complessita'
La complessità astratta. Gli assiomi di Blum. Cenni ad alcuni teoremi centrali della teoria di Blum. La complessità concreta. Calcolabilità in tempo polinomiale. Le classi di problemi P ed NP. Definizione di problema NP completo. Il problema della soddisfacibilità. Il teorema di Cook e la tesi di Cook-Karp. Cenni al problema P=?NP. Cenni al decimo problema di Hilbert e agli insiemi diofantei. Il teorema di Matjasievic. I sette Problemi del Millennio come riproposizione dei problemi di Hilbert al Convegno del 1900.