Prof. Simone Martini

Far riflettere gli studenti sulle limitazioni dei procedimenti algoritmici, limiti sia intrinseci sia dettati dalle risorse a disposizione. Gli studenti incontreranno il concetto di funzione calcolabile, di linguaggio formale, di automa, di classe di complessitą e le loro reciproche relazioni. Dopo aver superato l'esame si ritiene che lo studente: conosca l'esistenza di problemi intrinsecamente irrisolubili per via algoritmica; abbia una chiara idea delle relazioni note tra le classi di complessitą logaritmica, polinomiale deterministica e non deterministica, esponenziale; conosca le prime nozioni relative ai linguaggi formali e alle loro relazioni con gli automi.

1.Calcolabilitą. Modelli di calcolo: la Macchina di Turing. Funzioni calcolabili e problemi decidibili. Enumerazione delle funzioni calcolabili, funzione universale. Tesi di Church. Esistenza di problemi non decidibili. Problemi semidecidibili.

2. Complessitą. Macchine di Turing con risorse limitate. Classi di complessitą. Alcune classi: P, NP, EXP, PSPACE. Riduzioni polinomiali e problemi completi. NP-completezza, teorema di Cook, esempi di problemi NP completi.

3. Linguaggi formali. Grammatiche a struttura di frase. Linguaggi regolari, espressioni regolari, automi finiti. Linguaggi liberi dal contesto, alberi di derivazione; automi a pila.

Appunti delle lezioni.

N.J. Cutland, Computability: An introduction to recursive function theory, Cambridge Univ.Press, Cambridge 1980.

J.E. Hopcroft e J.D. Ullman, Introduction to automata, languages and computation, Addison-Wesley, Reading 1979.