Computability and complexity

lingi1123  2017-2018  Louvain-la-Neuve

Computability and complexity
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

The prerequisite(s) for this Teaching Unit (Unité d’enseignement – UE) for the programmes/courses that offer this Teaching Unit are specified at the end of this sheet.
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

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:

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

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:

  • 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
 

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 Church-Turing thesis
  • Introduction to computational complexity
  • Complexity classes
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
http://icampus.uclouvain.be/claroline/course/index.php?cid=INGI1123
Bibliography
Transparents en ligne
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
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
MAP2M
5
Bachelor in Computer Science
SINF1BA
5
LSINF1101 AND LSINF1102 AND LSINF1103 AND LSINF1250
Minor in Engineering Sciences: Computer Sciences
LSINF100I
5
Minor in Computer Sciences
LINFO100I
5
LSINF1101
Additionnal module in Mathematics
LMATH100P
5
Additionnal module in Mathematics
TMATH100P
5