Study-unit COMPUTABILITY AND COMPLEXITY
| Course name | Mathematics |
|---|---|
| Study-unit Code | A002041 |
| Curriculum | Matematica per la crittografia |
| Lecturer | Arturo Carpi |
| Lecturers |
|
| Hours |
|
| CFU | 6 |
| Course Regulation | Coorte 2023 |
| Supplied | 2024/25 |
| Learning activities | Affine/integrativa |
| Area | Attività formative affini o integrative |
| Sector | INF/01 |
| Type of study-unit | Opzionale (Optional) |
| Type of learning activities | Attività formativa monodisciplinare |
| Language of instruction | English |
| Contents | Turing machine. Goedel coding. Church-Turing thesis. Unsolvable problems. Universal Turing machine. halting problem. Hilbert tenth problem. Partial recursive functions. Edmonds-Cook-Karp thesis. Classes P and NP. NP complete problems. Classes L, NL, PSPACE, NPSPACE. |
| Reference texts | 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 |
| Educational objectives | The course will furnish to the student the knowledge of the main methods and results of the Computability and Complexity Theory. Moreover it will give the ability to apply this knowledge to identify the complexity of practical problems in various fields. |
| Prerequisites | In order to attend the course,the student should have some basic knowledge of Formal Language Theory and of algorithm complexity analysis. This notions are present in the fundamental courses of the first level degree courses in Informatics. |
| Teaching methods | Lectures |
| Other information | - |
| Learning verification modality | The final evaluation consists is an oral exam. The goal of this exam is to verify the acquisition of the main theoretical aspect of the discipline and the ability to apply such knowledge in order to evaluate the structural complexity of problems in different fields. Moreover, the ability of discussing the themes of the course using a proper technical language will be evaluated. On student request, exam may be given in Italian, English or French. |
| Extended program | Theory of computability: Alphabets, strings, languages. Turing machine. Turing machines and languages. Turing machines and functions. Goedel coding. Church-Turing thesis. Multi-tape Turing machines. Non deterministic Turing machines. Algorithmically solvable problems and unsolvable problems. Universal Turing machines. halting problem. Decidable and semi-decidable sets. Hilbert tenth problem. Recursion theorem, fix-point theorem and Rice's theorem. Post correspondence theorem. Recursive function. Church-computabilty. Partial recursive functions. Complexity theory: Time complexity classes. The class P and Edmonds-Cook-Karp thesis. The class NP. The problem P=NP. NP-completeness. Cook-levin theorem. Merkle-Helmann crypto-system. Space complexity classes. The classes L, NL, PSPACE, NPSPACE. Savitch theorem. |