Learning outcomes

This course aims at providing an introduction to the theories of computability and complexity in computer science.

Goals

This course aims at providing an introduction to the theories of computability and complexity in computer science.

Content

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.

Assessment method

Written exam. The exam consists of questions asessing the student's comprehension of the matter and capability of reproducing parts of the theory.

Sources, references and any support material

  • W. Vanhoof, Calculabilité et complexité, course notes.
  • D. Harel, Algorithmics - The spirit of computing, Addison-Wesley,2004.
  • J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation, Pearson, 3th ed., 2007
  • N.D. Jones, Computability and Complexity, The MIT Press, 1997.
  • B.M. Moret, The Theory of Computation, Addison-Wesley, 1998.
  • C.H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  • A. Setzer, Computability theory, 2003.
  • T.A. Sudkamp, Languages and Machines, Pearson International, 2006.

Language of instruction

Français