Note from June 29, 2020
Although we do not yet know how long the social distancing related to the Covid19 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.
Although we do not yet know how long the social distancing related to the Covid19 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.
5 credits
30.0 h + 30.0 h
Q2
Teacher(s)
Deville Yves;
Language
French
Prerequisites
Within SINF1BA : LSINF1101
Within FSA1BA : LFSAB1101, LFSAB1102, LFSAB1202, LFSAB1202, LFSAB1301, LFSAB1401
Within FSA1BA : LFSAB1101, LFSAB1102, LFSAB1202, LFSAB1202, LFSAB1301, LFSAB1401
Main themes
 Computability : problems and algorithms, computable and non computable functions, reductions, undecidable classes of problems (Rice), fix point theorem, ChurchTuring thesis
 Main computability models : Turing machines, recursive functions, lambda calculus, automates
 Complexity theory : complexity classes, NPcompleteness, Cook's theorem, how to solve NPcomplete problems
Aims
At the end of this learning unit, the student is able to :  
1 
Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:

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”.
Content
 Introduction
 Concepts: demonstration and reasoning, sets, Cantor's diagonalization
 Computability: basic results
 Models of computability
 Analysis of the ChurchTuring thesis
 Introduction to computational complexity
 Complexity classes and NP completeness
Teaching methods
 lectures
 exercises supervised by a teaching assistant
Evaluation methods
 written exam (September, oral exam)
Other information
Background:
 SINF1121 Advanced algorithmics and data structures
Online resources
Bibliography
Livres de référence
 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
Teaching materials
 Transparents en ligne
 Syllabus collaboratif
Faculty or entity
INFO
Programmes / formations proposant cette unité d'enseignement (UE)
Title of the programme
Sigle
Credits
Prerequisites
Aims
Master [120] in Mathematical Engineering
Master [60] in Computer Science
Master [120] in Computer Science
Additionnal module in Mathematics
Minor in Engineering Sciences: Computer Sciences (only available for reenrolment)