 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
Other credits in programs
|
FSA13BA
|
Troisième année de bachelier en sciences de l'ingénieur, orientation ingénieur civil
|
(4 credits)
| |
|
MAP22
|
Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées
|
(4 credits)
| |
|
MATH22/G
|
Deuxième licence en sciences mathématiques
|
(4 credits)
|
Mandatory
|
|
SINF13BA
|
Troisième année d'études de bachelier en sciences informatiques
|
(4 credits)
| |
|
SINF1PM
|
Année d'études préparatoires au master en sciences informatiques (60 et 120)
|
(4 credits)
| |
|
