Computability and Computational Complexity
A.Y. 2024/2025
Learning objectives
A first goal is to introduce the notion of computability by means of simple programming languages. We recall that a fuction is computable (and a problem is called decidable) if it admits an algorithm for its computation (solution). In particular we aim to illustrate and motivate Church's Thesis, the undecidable problems and the main results of the theory of recursive functions. A second goal is devoted to the classification of decidable problem based on their computational complexity, given by the computation time and the memory space necessary to determine the solution. A special attention is paid to study and motivate the class of NP-complete problems.
Expected learning outcomes
Comprehension of the main notions of computability and decidability. Capability to recognize undecidable or hard problems in the main cases. Capability to formalize and study computational models.
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
First semester
Course syllabus
Introduction to computability: intuitively computable functions, existence of non-computable functions, pairing functions and their extensions. Reduced RAM model, sintax and semantics of its programming language. Sintax and semantics of While language. Example of compiler and interpreter. Equivalence between RAM programs and While programs. Coding of RAM programs by integer numbers. Partial recursive functions. Church's thesis.
Acceptable programming systems. Recursion theorem. Isomorphism theorem. Undecidable problems.
Special decision problems: halting, totality, equivalence. Recursive sets and recursively enumerable sets. Equivalent definitions of r.e. sets. Reducibility between problems. Rice's theorem.
Formal languages and grammars. Chomsky hierarchy: regular, context-free, context-sensitive and type 0 languages. Deterministic and nondeterministic finite state automata and their simulation properties. Closure properties and Pumping lemma for regular languages.
Turing machines. Deterministic and non-deterministic models and their simulation. Time and space complexity. Classes P and NP. Polynomial time reducibility and its main examples. NP-complete problems. Cook's Theorem. Introduction to space complexity: classes L, NL, Pspace. Complexity of reachability problem. Savitch's Theorem. Immermann-Szelepscényi Theorem.
Acceptable programming systems. Recursion theorem. Isomorphism theorem. Undecidable problems.
Special decision problems: halting, totality, equivalence. Recursive sets and recursively enumerable sets. Equivalent definitions of r.e. sets. Reducibility between problems. Rice's theorem.
Formal languages and grammars. Chomsky hierarchy: regular, context-free, context-sensitive and type 0 languages. Deterministic and nondeterministic finite state automata and their simulation properties. Closure properties and Pumping lemma for regular languages.
Turing machines. Deterministic and non-deterministic models and their simulation. Time and space complexity. Classes P and NP. Polynomial time reducibility and its main examples. NP-complete problems. Cook's Theorem. Introduction to space complexity: classes L, NL, Pspace. Complexity of reachability problem. Savitch's Theorem. Immermann-Szelepscényi Theorem.
Prerequisites for admission
General knowledge of basic algorithms, main data structures and at least one imperative programming language, with an elementary experience of computer programming.
Attending preliminary courses of Computer Programming and Algorithms, at an undergraduate level, is strongly suggested.
Attending preliminary courses of Computer Programming and Algorithms, at an undergraduate level, is strongly suggested.
Teaching methods
The course is based on traditional lectures.
Teaching Resources
- Web site of the course: http://users.mat.unimi.it/users/goldwurm/Calcolabilita
which will also include a link to the web site MyAriel for the new academic year.
- Class notes:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019.
- Other references:
A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, parte 1, Univ. degli Studi di
Milano, 1990.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1997.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.
which will also include a link to the web site MyAriel for the new academic year.
- Class notes:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019.
- Other references:
A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, parte 1, Univ. degli Studi di
Milano, 1990.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1997.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.
Assessment methods and Criteria
The final examination consists of an oral exam on the subjects of the syllabus. Skill required are the knowledge of the fundamental definitions, the ability to present and discuss the significant examples and the proof of the main results mentioned in the syllabus.
Final marks lie in the numerical range 0-30 and will be communicated just after the oral examination.
Final marks lie in the numerical range 0-30 and will be communicated just after the oral examination.
INF/01 - INFORMATICS - University credits: 6
Lessons: 42 hours
Professor:
Goldwurm Massimiliano
Shifts:
Turno
Professor:
Goldwurm MassimilianoEducational website(s)
Professor(s)