Computability and complexity [ LINGI1123 ]

• Advanced algorithmics and data strucutres (e.g. SINF1121)
• Thinking using discrete mathematics (e.g. INGI1101)

• 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

Students completing successfully this course will be able to

• recognize, explain and identify the limits of computing science ;
• explain the main computability models especially  their foundations, their similarities and their differences
• identify, recognize and describe non computable and untractable problems

Students will have developed skills and operational methodology. In particular, they have developed their ability to

• have a critical look at the performance and capabilities of computer systems

• written exam (September, oral exam)
• 2 formative evaluations (not for the final grade) during the semester

• lectures
• exercises supervised by a teaching assistant

• Introduction
  
• 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

Slides online

References

• 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