<- Archives UCL - Programme d'études ->



computability and complexity [ LINGI1123 ]


4.0 crédits ECTS  30.0 h + 30.0 h   2q 

Teacher(s) Deville Yves ;
Language French
Place
of the course
Louvain-la-Neuve
Online resources

 > http://www.icampus.ucl.ac.be/claroline/course/index.php?cid=INGI1123

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

 

Main themes
  • 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
Aims

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
Evaluation methods
  • written exam (September, oral exam)
  • 2 formative evaluations (not for the final grade) during the semester
Teaching methods
  • lectures
  • exercises supervised by a teaching assistant
Content
  • 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
Bibliography

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

 

Cycle et année
d'étude
> Bachelor in Engineering
> Preparatory year for Master in Computer science
> Master [120] in Mathematical Engineering
> Bachelor in Computer Science
> Bachelor in Mathematics
Faculty or entity
in charge
> INFO


<<< Page précédente