 | | |
| INFO0016-1 | Introduction to the theory of computation
|
|
| Duration : | 30h Th, 30h Pr |
|
| Number of credits : |
| Master of science in computer science and engineering, research focus, 1st year | | 5 |
|
| Master in Computer science, Research Focus, 1st year | | 6 |
|
| Master of science in computer science and engineering, professional focus in management, 1st year | | 5 |
|
| Master in Computer Science, Professional Focus (Management), 1st year | | 6 |
|
| Master in Computer science | | 6 |
|
| Master in Bio-informatics and Modelling, Research focus, 1st year | | 6 |
|
|
|
| Lecturer : | Pierre Wolper |
|
Language(s) of instruction :
|
| English language |
|
Organisation and examination :
|
| Teaching in the first semester, review in January |
|
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 English and/or French. 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. |
|
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 :
|
| mid-semester test (non compulsory); written exam including both theory and exercise questions (no oral exam). |
|
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 20 99 - e-mail Pierre.Wolper@ulg.ac.be |
|
