119553 - LINGUAGGI FORMALI, COMPUTABILITA' E COMPLESSITA'

Il corso introduce le principali metodologie per l'analisi della calcolabilitá e della complessitá di un problema decisionale. Argomenti trattati (Conoscenze): - introduzione ai problemi decisionali e relazione con i problemi funzionali e di ottimizzazione. - linguaggi regolari, Pumping Lemma, esistenza di linguaggi non regolari, automi a stati finiti - linguaggi liberi dal contesto, Pumping Lemma, esistenza di linguaggi non liberi dal contesto, automi a pila - modello della macchina di Turing e tesi di Church-Turing - riduzioni many one e riduzioni di Turing; esistenza di problemi non decidibil, esempi di problemi noti non decidibili, teorema di Rice - concetto di classe di complessitá - la classe P e la classe NP, e relazione tra P ed NP - problemi NP-completi - approssimazione a problemi NP-completi - le classi NLOGSPACE, PSPACE, e NPSPACE, e teorema di Satvich - altre classi importanti e teoremi di separazione. - accenno alla relazione che sussiste tra la teoria della computabilitá e l'intelligenza artificiale moderna Al termine del corso lo studente sará capace di (Abilitá) - riconoscere un problema decisionale calcolabile da uno non calcolabile (in certi casi semplici) - riconoscere la classe di complessitá di un problema calcolabile (in certi casi semplici) - comprendere la matematica alla base di un problema e le questioni relative alla sua classificazione - comprendere il ruolo giocato da problemi classici come la soddifacibilità di formule logiche, proposizionali, sub-proposizionali, e al primo ordine