Automi E Linguaggi 2021/2022

L'insegnamento intende fornire una visione introduttiva dell'Informatica Teorica. "Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi e dei processi per la rappresentazione dell'informazione e per la sua elaborazione. Come accade per altre discipline tecnico-scientifiche, anche nel caso dell'informatica esiste un insieme di concetti, di principi, di proprietà logico-matematiche che ne costituiscono il fondamento teorico. Su tale fondamento si basano i progettisti per realizzare modelli formali di sistemi e processi di calcolo, per progettare nuovi strumenti informatici e nuove applicazioni e per analizarne e certificarne le prestazioni." (dalla voce Informatica Teorica nell'Enciclopedia Treccani della Scienza e della Tecnica, 2007). In pratica, AUTOMI E LINGUAGGI fornisce i rudimenti di teoria dei linguaggi, teoria della calcolabilità e teoria della complessità. 

Programma sintetico

• TEORIA DEI LINGUAGGI: Linguaggi regolari e automi finiti deterministici e non deterministici. Espressioni regolari e loro equivalenza con gli automi finiti. Pumping lemma per i linguaggi regolari. Chiusura dei linguaggi regolari rispetto a vari operatori. Linguaggi "context-free" e loro grammatiche. Automi pushdown non deterministici e loro equivalenza con le grammatiche "context-free". Pumping lemma per i linguaggi "context-free". Automi pushdown deterministici, linguaggi "context-free" deterministici e loro proprietà. Parsing dei linguaggi "context-free". Grammatiche LR(k), LR(1), LR(0).
• TEORIA DELLA CALCOLABILITÀ: Macchine di Turing. Linguaggi ricorsivamente enumerabili linguaggi ricorsivi. Varianti di macchine di Turing e loro equivalenza. Macchine di Turing non deterministiche. Enumeratori. Definizione di algoritmo e tesi di Church-Turing. Problemi decidibili e indecidibili. Il metodo di diagonalizzazione. Esempi di linguaggi non decidibili. Macchina di Turing universale. Riduzione tra linguaggi.  Il problema PCP (Post Correspondence Problem). Riducibilità many-one. Funzioni calcolabili. Teorema di Rice. Teorema della ricorsione. Sistemi formali, modelli e teorie dei modelli. Decidibilità di teorie logiche.  Riducibilità di Turing and macchine di Turing ad oracolo. Complessità di Kolmogorov. 
• TEORIA DELLA COMPLESSITÀ: Complessità temporale. La classe P. La classe NP. Esempi di problemi in P ed in NP. La classe co-NP. La classe EXPTIME. NP-hardness e NP-completezza. Il problema di soddisfacibilità SAT. Esempi di problemi NP-completi: SAT, 3SAT, CLIQUE, VERTEX COVER, HAMPATH, UHAMPATH, SUBSET SUM. Complessità spaziale. Il teorema di Savitch. Le classi PSPACE e EXPSPACE. Problemi PSPACE-completi e EXPSPACE-completi.