UCL - computability and complexity

[INGI1123]

[30h + 30h] 4 credits

This course is taught in the 2d semester.

Teacher(s): Yves Deville, Baudouin Le Charlier(supplée Yves Deville)

Language: French

Level: First

Aims
Main themes
Content and teaching methods
Other information (prerequisite, evaluation (assessment methods), course materials recommended readings, ...)

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.