2021-2022 / INFO0016-1

Introduction to the theory of computation


26h Th, 26h Pr

Number of credits

 Master of Science (MSc) in Data Science5 crédits 
 Master of Science (MSc) in Computer Science and Engineering5 crédits 
 Master of Science (MSc) in Computer Science and Engineering (double diplômation avec HEC)5 crédits 
 Master of Science (MSc) in Data Science and Engineering5 crédits 
 Master of Science (MSc) in Computer Science5 crédits 
 Master of Science (MSc) in Computer Science (double diplômation avec HEC)5 crédits 
 Master of Science (MSc) in Computer Science5 crédits 


Quentin Louveaux

Language(s) of instruction

English language

Organisation and examination

Teaching in the first semester, review in January


Schedule online

Units courses prerequisite and corequisite

Prerequisite or corequisite units are presented within each program

Learning unit contents

Introduction to the concept of effective procedure. Countable and uncountable sets. Finite automata and pushdown automata. Formal grammars and their relation to automata. Turing machines and the Church-Turing thesis. Theory of recursive functions. Problems unsolvable by an effective procedure. Introduction to NP-completeness and complexity theory.

Learning outcomes of the learning unit

At the end of this course, the student will have a good knowledge of the theory pertaining to the limits of computer systems and will understand their meaning.

Prerequisite knowledge and skills

Knowledge of programming

Planned learning activities and teaching methods

1st quadrimester - Lectures, problem sessions.
The lectures and problem sessions are given in English. The reference book is written in French, but similar textbooks written in English are available. The problem sessions are aimed at gaining familiarity with the concepts introduced in the lectures.

Mode of delivery (face to face, distance learning, hybrid learning)

Face-to-face course

Additional information:


Recommended or required readings

Recommended reference covering precisely the material taught in the course:
P. Wolper, Introduction à la calculabilité (3ième édition), Dunod, 2006.
Reference in English:
Michael Sipser, Introduction to the Theory of Computation, CENGAGE Learning Custom Publishing, 2012

Assessment methods and criteria

Exam(s) in session

Any session

- In-person

written exam ( open-ended questions )

Additional information:

Written exam including both theory and exercise questions (no oral exam).

Work placement(s)

Organizational remarks

All documents are available through the repository:
This repository contains all slides, all annotated slides, the exercises, the previous exams.  


Quentin Louveaux
04/366 27 89