Insegnamento CALCOLABILITÀ E COMPLESSITÀ COMPUTAZIONALE
| Nome del corso di laurea | Informatica |
|---|---|
| Codice insegnamento | GP004154 |
| Curriculum | Comune a tutti i curricula |
| Docente responsabile | Arturo Carpi |
| Docenti |
|
| Ore |
|
| CFU | 6 |
| Regolamento | Coorte 2018 |
| Erogato | Erogato nel 2018/19 |
| Erogato altro regolamento | |
| Attività | Caratterizzante |
| Ambito | Discipline informatiche |
| Settore | INF/01 |
| Anno | 1 |
| Periodo | Primo Semestre |
| Tipo insegnamento | Obbligatorio (Required) |
| Tipo attività | Attività formativa monodisciplinare |
| Lingua insegnamento | ITALIANO |
| Contenuti | 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. |
| Testi di riferimento | 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) |
| Obiettivi formativi | Il corso fornirà allo studente la conoscenza dei principali metodi e risultati della Teoria della Calcolabilità e della Complessità e l'abilità di applicarli per individuare la complessità di problemi in diversi campi. |
| Prerequisiti | Per seguire con profitto il corso è opportuno che lo studente abbia familiarità con le nozioni di base della teoria deri linguaggi formali e con l'analisi di complessità degli algoritmi. Tali nozioni sono comunemente presenti nei corsi di base delle lauree triennali in Informatica. |
| Metodi didattici | Lezioni frontali |
| Altre informazioni | - |
| Modalità di verifica dell'apprendimento | L'esame consiste in una prova orale. Tale prova sarà un colloquio volto a verificare l'apprendimento dei principali aspetti teorici della disciplina nonché la capacità di applicare tali conoscenze per individuare la complessità di problemi in diversi campi. Su richiesta dello studente, l'esame potrà essere tenuto in lingua Inglese o Francese. Per informazioni sui servizi di supporto agli studenti con disabilità e/o DSA visita la pagina http://www.unipg.it/disabilita-e-dsa |
| Programma esteso | 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. |