mag 17 2008
Informatica Teorica
| Docente: | Arturo Carpi |
| Indirizzo: | insegnamenti comuni |
| Anno accademico: | 2007/2008 |
| Ore di teoria: | 48 |
| Ore di pratica: | 0 |
| CFU | 6 |
| Sito ufficiale: |
Prerequisiti
Elementi di Linguaggi Formali.
Obiettivi
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.
Programma
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.
Modalità di valutazione
Prova orale.
Testi consigliati
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).
