 | | |
| INFO0016-1 | Introduction to the theory of computation
|
|
| Duration : | 30h Th, 30h Pr |
|
| Number of credits : |
| Master of science in computer science and engineering, in-depth approach, 1st year | | First semester | | 5 |
|
| Master in Computer science, Research Focus, 1st year | | First semester | | 6 |
|
| Master of science in computer science and engineering, professional focus in management, 1st year | | First semester | | 5 |
|
| Master in Computer Science, Professional Focus (Management), 1st year | | First semester | | 6 |
|
| Master in Computer science | | First semester | | 6 |
|
| Master in Bio-informatics and Modelling, Research focus, 1st year | | First semester | | 6 |
|
|
|
| Lecturer : | Pierre Wolper |
|
Language(s) of instruction :
|
| English language |
|
Course 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 course :
|
| 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. |
|
Prerequisites and co-requisites/ Recommended optional programme components :
|
| Knowledge of programming |
|
Planned learning activities and teaching methods :
|
| 1st semester - Lectures, problem sessions.
The lectures are given in English, the problem sessions in French. The reference book is written in French.
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. |
|
Recommended or required readings :
|
| P. Wolper, Introduction à la calculabilité (3ième édition), Dunod, 2006.
Required reference covering precisely the material taught in the course. |
|
Assessment methods and criteria :
|
| mid-semester test (non compulsory); written exam including both theory and exercise questions (no oral exam). |
|
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 20 99 - e-mail Pierre.Wolper@ulg.ac.be |
|
