This course aims at providing an introduction to the theories of computability and complexity in computer science.
This course aims at providing an introduction to the theories of computability and complexity in computer science.
In a first part we study the basic concepts underlying the theory of computability such as the notion of algorithm, countable sets, computable functions, (semi-)decidable sets and intractable problems. In a second part, we study computational models such as programming languages, lambda-caclculus, recursive functions and Turing machines, and we discuss some key results of computability: the halting problem, Rice's theorem, the relationship between interpretation and compilation and the Futamura projections. In a third section, we introduce the theory of complexity and we study the complexity classes P, NP and coNP. We introduce the class of NP-complete problems and discuss their relevance.
Written exam. The exam consists of questions asessing the student's comprehension of the matter and capability of reproducing parts of the theory.
| Training | Study programme | Block | Credits | Mandatory |
|---|---|---|---|---|
| Standard | 0 | 5 | ||
| Standard | 0 | 5 | ||
| Standard | 0 | 5 | ||
| Standard | 1 | 5 | ||
| Standard | 1 | 5 | ||
| Standard | 1 | 5 |