Although we do not yet know how long the social distancing related to the Covid-19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been - or will be - communicated to the students by the teachers, as soon as possible.
Within FSA1BA : LFSAB1101, LFSAB1102, LFSAB1202, LFSAB1202, LFSAB1301, LFSAB1401
- 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
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:
Students completing successfully this course will be able to
Students will have developed skills and operational methodology. In particular, they have developed their ability to
The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
- Concepts: demonstration and reasoning, sets, Cantor's diagonalization
- Computability: basic results
- Models of computability
- Analysis of the Church-Turing thesis
- Introduction to computational complexity
- Complexity classes and NP completeness
- exercises supervised by a teaching assistant
- written exam (September, oral exam)
- SINF1121 Advanced algorithmics and data structures
- O. Ridoux, G. Lesventes. Calculateurs, calculs, calculabilité. Dunod Collection Sciences Sup, 224 pages, 2008.
- P. Wolper Introduction à la calculabilité 2nd Edition, Dunod, 2001.
- Sipser M. Introduction to the Theory of Computation PWS Publishing Company, 1997
- Transparents en ligne
- Syllabus collaboratif