Calcolabilità e Complessità
a.a. 2007/2008

Docente: R. Silvestri

Finalità

L'obiettivo del corso è introdurre alla teoria della calcolabilità e alla teoria della complessità computazionale.

Programma

Teoria degli automi e delle grammatiche

Cenni su modelli di calcolo. Automi a stati finiti (DFA). La classe dei linguaggi regolari: chiusura rispetto a unione, intersezione e complemento. Automi non deterministici (NFA). Equivalenza tra DFA e NFA (dimostrazione). Chiusura dei regolari rispetto a concatenazione di linguaggi e stella di Kleene. Espressioni regolari. Equivalenza tra espressioni regolari e DFA (dimostrazione). Pumping lemma per i regolari (dimostrazione). Teorema di Myhill-Nerode (dimostrazione solamente del fatto che se L è regolare allora l'indice della relazione di Nerode di L ha indice minore od uguale al numero degli stati di un qualsiasi automa che riconosce L). Uso della relazione di Nerode per determinare delimitazioni inferiori sul numero di stati di DFA e NFA.
Automi pushdown deterministici (DPDA). Chiusura della classe dei linguaggi accettati da DPDA rispetto al complemento (senza dimostrazione) e all'intersezione con linguaggi regolari. Automi pushdown non deterministici (NPDA). Chiusura dell classe dei linguaggi accettati da NPDA rispetto a unione, concatenazione di linguaggi, stella di Kleene e intersezione con linguaggi regolari. Grammatiche context-free (CFG). Alberi di derivazione e derivazioni più a sinistra. Equivalenza tra CFG e NPDA (dimostrazione solamente del verso da CFG a NPDA). Pumping lemma per linguaggi context-free (dimostrazione).

Teoria della calcolabilità

Macchine di Turing (TM) ad un nastro. Configurazioni di una TM. Linguaggi semi-decidibili (o riconoscibili) e linguaggi decidibili (o ricorsivi). Esempi di linguaggi decidibili. Macchine di Turing a k nastri (k-TM). Equivalenza tra k-TM e TM (dimostrazione). Macchine di Turing non deterministiche (NTM). Equivalenza tra NTM e TM (dimostrazione). Robustezza del concetto di decidibilità tramite TM e cenni ad altri modelli di calcolo: RAM. Tesi di Church-Turing.
Indecidibilità del problema dell'accettazione, metodo della diagonalizzazione (dimostrazione). Relazione tra decidibilità e semi-decidibilità. Indecibilità dei problemi della terminazione, del linguaggio vuoto e dell'equivalenza (dimostrazioni). Automi linearmente limitati (LBA). Decidibilità dei linguaggi context free tramite LBA (dimostrazione). Decidibilità del problema della terminazione per LBA (dimostrazione). Indecidibilità del problema del linguaggio vuoto per LBA (dimostrazione). Decidibilità del problema del linguaggio vuoto e indecidibilità del problema della totalità per CFG (dimostrazioni). Funzioni calcolabili e la m-riducibilità. Conservazione della decidibilità e della semi-decidibilità da parte della m-riducibilità.

Teoria della complessità

Modelli di calcolo e la misura delle risorse computazionali. Complessità temporale di macchine di Turing: esempi. Misura della complessità della simulazione di k-TM tramite TM (dimostrazione). Cenni ad altri modelli (RAM) che sono simulabili in tempo polinomiale da TM. Complessità temporale di macchine di Turing non deterministiche. Misura della complessità della simulazione di NTM tramite TM (dimostrazione). Classi di complessità temporali. La classe P. Crescita polinomiale e crescita esponenziale. Esempi di problemi in P: i linguaggi context free sono in P (dimostrazione). La classe NP. Verificabilità polinomiale. Riducibilità polinomiale e il concetto di NP-completezza. Teorema di Cook-Levin: NP-completezza di SAT (dimostrazione). Esempi di riduzioni polinomiali tra problemi.