Insegnamento COMPUTABILITY AND COMPLEXITY
- Corso
- Matematica
- Codice insegnamento
- A002385
- Curriculum
- Matematica per la crittografia
- Docente
- Arturo Carpi
- Docenti
-
- Arturo Carpi
- Ore
- 42 ore - Arturo Carpi
- CFU
- 6
- Regolamento
- Coorte 2021
- Erogato
- 2022/23
- Attività
- Affine/integrativa
- Ambito
- Attività formative affini o integrative
- Settore
- INF/01
- Tipo insegnamento
- Opzionale (Optional)
- Tipo attività
- Attività formativa monodisciplinare
- Lingua insegnamento
- INGLESE
- 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)
Michael Sipser, Introduction to the Theory of Computation, Cengage, 2013 - 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. Inoltre, tale colloquio permetterà di valutare la capacità di comunicazione dello studente sui temi del corso con un appropriato linguaggio tecnico.
Su richiesta dello studente, l'esame potrà essere tenuto in lingua italiana, 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. Teorema di recursione, teorema del punto fisso e teorema di Rice. Teorema di corrispondenza di Post.
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.
Il sistema crittografico Merkle-Helmann.
Classi di Complessità spaziale. Le classi L, NL, PSPACE, NPSPACE. Il teorema di Savitch.