Computability and complexity

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.