Aims

- To understand, recognize and identify the limits of computing science

- To understand the foundations, the similarities and differences of the main computability models

- To identify, recognize and understand non computable and untractable problems

Main themes

- Computability : problems and algorithms, computable and non computable functions, reductions, undecidable classes of problems (Rice), fix point theorem, Church-Turing thesis

- Main computability models : Turing machines, recursive functions, lambda calculus, automates

- Complexity theory : complexity classes, NP-completeness, Cook's theorem, how to solve NP-complete problems

Content and teaching methods

see "Main themes"

Other information (prerequisite, evaluation (assessment methods), course materials recommended readings, ...)

- Prerequisites
This course presupposes the knowledge of material covered in the following course
(1) LINF2121 : Algorithmique et structures de données

- References
(1) Sipser M. Introduction to the Theory of Computation. PWS Publishing Company, 1997
(2) P. Wolper. Introduction à la calculabilité. (2nd edition) InterEditions, 2001.

For more information:

http://www.ucl.ac.be/etudes/cours/ingi2123.htm