Foundations of Computer Science 1
A.Y. 2018/2019
Learning objectives
Main goal of this course is to introduce the notion of computability by means of simple programming languages. 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 part is devoted to computational complexity and in particular to NP-complete problems.
Expected learning outcomes
Comprehension of the main notions of computability. Capability to recognize undecidable or hard problems in the main cases. Capability to formalize computational models.
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
First semester
Course syllabus
Introduction to computability: computable functions, existence of non-computable functions, pairing functions. Reduced RAM model and the associated programming language. While language. Equivalence between RAM programs and While programs. Partial recursive functions. Church's thesis.
Acceptable programming systems. Recursion theorem. Isomorphism theorem. Undecidable problems. Recursive sets and recursively enumerable sets. Reducibility between problems. Rice's theorem.
Formal languages and grammars. Chomsky hierarchy. Deterministic and nondeterministic finite state automata. Closure properties of regular languages. Pumping lemma for regular languages.
Turing machines. Deterministic and non-deterministic models. Time and space complexity. Classes P and NP. Polynomial time reducibility. NP-complete problems. Cook's theorem. Introduction to space complexity: classes L, NL, Pspace and Savitch's theorem.
Acceptable programming systems. Recursion theorem. Isomorphism theorem. Undecidable problems. Recursive sets and recursively enumerable sets. Reducibility between problems. Rice's theorem.
Formal languages and grammars. Chomsky hierarchy. Deterministic and nondeterministic finite state automata. Closure properties of regular languages. Pumping lemma for regular languages.
Turing machines. Deterministic and non-deterministic models. Time and space complexity. Classes P and NP. Polynomial time reducibility. NP-complete problems. Cook's theorem. Introduction to space complexity: classes L, NL, Pspace and Savitch's theorem.
Professor(s)