Università degli Studi di Perugia

Prova orale

n.d.

nessuna

Teoria della computabilità:
Alfabeti, stringhe, linguaggi.
La Macchina di Turing. Macchine di Turing e linguaggi. Macchine di Turing e funzioni. Codifica di Goedel. La Tesi di Church-Turing.
Macchine di Turing a più nastri. Macchine di Turing non deterministiche.
Problemi risolubili algoritmicamente e problemi insolubili. La Macchina Universale. Il Problema dell'arresto.
Insiemi decidibili e semidecidibili. Il Decimo Problema di Hilbert.
Funzioni Ricorsive. Calcolabilità secondo Church. Le funzioni parziali ricorsive

Teoria della complessità:
Classi di Complessità Temporale. La classe P e la Tesi di Edmonds-Cook-Karp. La classe NP. Il problema P=NP. Problemi NP-completi. Il teorema di Cook-Levin.
Classi di Complessità spaziale. Le classi L, NL, PSPACE, NPSPACE. Il teorema di Savitch.

Macchina di Turing. Codifica di Goedel. La Tesi di Church-Turing.
Problemi insolubili. La Macchina Universale. Il Problema dell'arresto. Il Decimo Problema di Hilbert.
Funzioni parziali ricorsive

Tesi di Edmonds-Cook-Karp. Classi P e NP. Problemi NP-completi. Classi L, NL, PSPACE, NPSPACE.

Lezioni frontali

C. Toffalori, F. Corradini, S. Leonesi, S. Mancini, Teoria della computabilità e della complessità, McGraw-Hill
J. Hopcroft, R. Motwani, J. Ullman, Automi, linguaggi e calcolabilità, Pearson
M. Davis, Computability and Unsolvability, Dover (ediz. Italiana: Abete, 1974)

Conoscere i principali metodi e risultati della Teoria della Calcolabilità e della Complessità e poterli applicare per individuare la complessità di problemi in diversi campi.

3/10/2011 - 13/01/2012

n.d.

Facoltativa

Dipartimento di Matematica e Informatica

Giovedì ore 16-18

Venerdì ore 11-13

Dipartimento di Matematica e Informatica, 2. piano