Computability and complexity [ LINGI1123 ]

> https://icampus.uclouvain.be/claroline/course/index.php?cid=INGI1123

Within SINF1BA : LSINF1101

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

Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:

• AA1.1, AA1.2
• AA2.4

Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:

• S1.I3, S1.G1
• S2.2

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)

• 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

Background:

• SINF1121 Advanced algorithmics and data structures