INFO0016-1

Duration

30h Th, 30h Pr

Number of credits

	Master in data science (120 ECTS)	5 crédits
	Master of science in computer science and engineering (120 ECTS)	5 crédits
	Master in data science and engineering (120 ECTS)	5 crédits
	Master in computer science (120 ECTS)	5 crédits
	Master in computer science (60 ECTS)	5 crédits
	Master in bio-informatics and modelling (120 ECTS)	6 crédits

Lecturer

Pierre Wolper

Language(s) of instruction

English language

Organisation and examination

Teaching in the first semester, review in January

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)

Face-to-face.

Assessment methods and criteria

Written exam including both theory and exercise questions (no oral exam). A bonus is given for active participation in the problem sessions.

Work placement(s)

Organizational remarks

Additional information can be found on the course web page: http://www.montefiore.ulg.ac.be/~pw/cours/calc.html

Contacts

Teacher: P. Wolper Tél.: 04 366 93 13 e-mail Pierre.Wolper@ulg.ac.be Assistant: Isabelle Mainz

Introduction to the theory of computation