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). 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.
* CAL - Calcolabilita'
Le funzioni ricorsive primitive (r.p.). Dimostrazione della ricorsività primitiva di varie funzioni elementari. 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. 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 teorema di ricorsione. Il teorema di Rice.
* CAL - Calcolabilita'
Il linguaggio di programmazione LOOP di Meyer e Ritchie . LOOP-calcolabilità delle funzioni r.p.. Equivalenza tra funzioni r.p. e funzioni LOOP-calcolabili. Teoremi di limitazione alla crescita delle funzioni r.p.. Profondità di nidificazione dei cicli LOOP. La gerarchia Ln. Non ricorsività primitiva della funzione di Ackermann. Inverso del teorema di limitazione alla crescita. 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.
* CAL - Calcolabilita'
Elementi di teoria della calcolabilit?. Introduzione informale alla nozione di algoritmo. Il modello pi? generale di automa: la macchina di Turing. Funzioni numeriche calcolate da una macchina di Turing. Macchina universale di Turing. Le macchine a registri. Linguaggi elementari di programmazione per macchine a registri. Funzioni numeriche calcolate da macchine a registri. Equivalenza fra i diversi modelli. Tesi di Church-Turing.
* CAL - Calcolabilita'
Linguaggi di programmazione Sn. Simulazione in Sn delle funzioni calcolabili in S. Introduzione del linguaggio di T di Post-Turing e T-calcolabilità delle funzioni parzialmente calcolabili in Sn. S-calcolabilità delle funzioni calcolabili da programmi di Post-Turing. Equivalenza tra MdT a quadruple, MdT a quintuple e programmi di Post Turing. Equivalenza tra MdT con nastro infinito bidirezionale e MdT con nastro infinito in una sola direzione. MdT non deterministiche.
* CAL - Calcolabilita'
Processi di Thue e simulazione di MdT non deterministiche mediante processi di Thue. Definizione di grammatica. Equivalenza tra i linguaggi accettati da MdT non deterministiche e i linguaggi generati da grammatiche. Ricorsività primitiva degli operatori di derivabilità in una grammatica. Equivalenza tra linguaggi r.e. e linguaggi generati da una grammatica. Caratterizzazioni degli insiemi r.e. Il teorema della forma normale di Kleene. Il problema della corrispondenza di Post e la sua insolubiltà algoritmica. Equivalenza tra funzioni S-calcolabili e funzioni µ-ricorsive. Non ricorsiva enumerabilità dell'insieme di indici delle funzioni ricorsive totali.
COM - Complessita'
Cenni al decimo problema di Hilbert e agli insiemi diofantei. Il teorema di Matjasievic. Il problema della complessità. La complessità astratta. Gli assiomi di Blum. Teorema del collegamento ricorsivo tra misure di complessità. Il teorema della lacuna. Il teorema dell'accelerazione 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. I sette Problemi del Millennio come riproposizione dei problemi di Hilbert al Convegno del 1900.