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 aim of the course is to get the students familiar with some basic notions of theoretical computer science, namely computability and complexity theories.

At the end of the course, the students should be able to rigorously define those notions (as well as all the mathematical tools that are necessary to achieves this, such as Turing machines, or the notion of reduction...), to illustrate those notions thanks to actual examples, to explain their scope, and to explain their practical application. For instance, students will be expected to comment and explain a complexity proof that has not been studied at the course. However, they will not be asked to produce new proofs.

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