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.
Condividi su