 | |
| INFO0016-1 | Introduction to the Theory of Computation
 |
|
| Duration : | 30h Th, 30h Pr |
|
| Credits/ECTS : |
| civil engineering in electricity, 2nd year | | | | 6,5 |
|
| civil engineer in computer sciences, 2nd year | | | | 5,5 |
|
| civil engineer in computer sciences, 3rd year | | | | 5 |
|
| "licencié" in computer, 2nd year | | | | 6 |
|
| Master in Electrical Engineering, in-depth approach, 1st year | | Toute l'année | | 5 |
|
| Master in Computer Engineering, in-depth approach, 1st year | | Toute l'année | | 5 |
|
| Master in Informatical Sciences, in-depth approach, 1st year | | Toute l'année | | 6 |
|
| Master in Electrical Engineering, specialized approach, 1st year | | Toute l'année | | 5 |
|
| Master in Computer Engineering, specialized approach, 1st year | | Toute l'année | | 5 |
|
| Master in Informatical Sciences, specialized approach, 1st year | | Toute l'année | | 6 |
|
| Master in Informatical Sciences | | Toute l'année | | 6 |
|
| Master in Bio-informatics and Modelling, Research focus, 1st year | | Toute l'année | | 6 |
|
|
|
| Holder(s) : | Pierre Wolper |
|
| Language : | Langue française |
|
| 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. |
|
| 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 |
|
|
|
| Items online : |
|
| Additional information |
| Room and schedule information., slides and problem sets. |
|
|
|
| |
