Computability and complexity

• Notion of problem and its relation with the notion of language -Notion of algorithm and its formalization into Turing machines -Recursive functions -The class of recursively enumerable languages -The class of recursive languages -The notion of reduction between problems -The class P -The class NP -Other complexity classes

The course aims to familiarize students with some fundamental concepts of computer science, namely the theories of decidability and complexity.

By the end of the course, students should be able to rigorously define these notions (along with the necessary mathematical tools to reach these definitions: Turing machines, the notion of reduction, etc.), illustrate them with concrete examples, explain their significance, and describe their practical applications. For example, students will be expected to understand and explain a complexity proof not covered in class, or to adapt a proof seen in class to a variation of a problem studied during the course.

Ex cathedra lectures, with some exercises given during the lectures.

References, bibliography, and recommended reading

Introduction to the theory of computation, Michael Sipser, MIT press.

P. Wolper, Introduction à la Calculabilit́e, Dunod, 978-2-10-049981-6

Contacts

Prof. Jean-Francois Raskin

email: jraskin [at] ulb.ac.be

Campus

Plaine

Method(s) of evaluation

• Oral examination
• Other

Oral examination

Other

Oral exam, with written preparation.

Mark calculation method (including weighting of intermediary marks)

100% oral exam.

Language(s) of evaluation

• english