 | |
| INFO0016-1 | Introduction to the Theory of Computation
 |
|
| Duration : | 30h Th, 30h Pr |
|
| Credits/ECTS : |
| civil engineer in computer sciences, 3rd year | | | | 5 |
|
| Master in Computer Engineering, in-depth approach, 1st year | | Premier quadrimestre | | 5 |
|
| Master in Computer science, Research Focus, 1st year | | Premier quadrimestre | | 6 |
|
| Master in Computer Engineering, specialized approach, 1st year | | Premier quadrimestre | | 5 |
|
| Master in Computer Science, Professional Focus (Management), 1st year | | Premier quadrimestre | | 6 |
|
| Master in Computer science | | Premier quadrimestre | | 6 |
|
| Master in Bio-informatics and Modelling, Research focus, 1st year | | Premier quadrimestre | | 6 |
|
|
|
| Holder(s) : | Pierre Wolper |
|
| Language : | Langue anglaise |
|
| 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. |
|
| Course objective : | To introduce the theoretical basis of the limits of computer systems and to give an understanding of their meaning. |
|
| Prerequisites : | Knowledge of programming |
|
| Workshops : | Problem sessions aimed at gaining familiarity with the concepts introduced in the lectures. |
|
| Organization : | 1st semester - Lectures, problem sessions.
The lectures are given in English, the problem sessions in French. The reference book is written in French. |
|
| Written notes : | P. Wolper, Introduction à la calculabilité (3ième édition), Dunod, 2006. |
|
| Assessment : | mid-semester test (non compulsory); written exam including both theory and exercise questions (no oral exam). |
|
| Contacts : | Teacher: P. Wolper - Tél. 04/366 20 99 - e-mail pw@montefiore.ulg.ac.be
Assistant: |
|
| Remarks : | Additional information can be found on the course web page: http://www.montefiore.ulg.ac.be/~pw/cours/calc.html |
|
