 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
Programmes in which this activity is taught
|
INFO2
|
Ingénieur civil informaticien
|
| |
|
LINF2
|
Licence en informatique
|
| |
Other credits in programs
|
INFO21
|
Première année du programme conduisant au grade d'ingénieur civil informaticien
|
(4 credits)
|
Mandatory
|
|
LINF21/GN
|
Première licence en informatique (informatique générale)
|
(4 credits)
|
Mandatory
|
|
LINF21/GS
|
Première licence en informatique (informatique de gestion)
|
(4 credits)
| |
|
MAP22
|
Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées
|
(4 credits)
| |
|
MAP23
|
Troisiè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)
| |
|
