algorithmic and programming language targeted in course LEPL1402 and discrete mathematics as seen in courses LINFO1114 or LEPL1108
The prerequisite(s) for this Teaching Unit (Unité d’enseignement – UE) for the programmes/courses that offer this Teaching Unit are specified at the end of this sheet.
- Theory of computability: problems and algorithms, computable and non-computable functions, reduction, undecidable problem classes (Rice's theorem), fixed point theorem, Church-Turing thesis
- Logic: logic of propositions and logic of predicates (syntax, semantics, proof, quantifiers, model checking, resolution)
- Computability Models: Turing Machine
- Theory of complexity: complexity classes, NP-completeness, Cook's theorem, NP-complete problem solving.
At the end of this learning unit, the student is able to :
Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
Given the learning outcomes of the "Bachelor in Computer science" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
- Concepts : enumerable sets
- Computability: fondamenbtal results
- Models of computability
- Analysis of Church-Turing thesis
- Introduction to algorithmic complexity
- Complexity classes
Due to the COVID-19 crisis, the information in this section is particularly likely to change.This course can be given in a variety of face-to-face and distance modalities. These may include lectures, readings, preparations, exercises, as well as individual or group work.
Due to the COVID-19 crisis, the information in this section is particularly likely to change.Different modes of evaluation can be organized: continuous assessment, graded work, participation, exam. The exam will be written, but in case of doubt on the part of the teacher as to the grade to be given to a student, the student may be questioned orally.