Home - Search by Faculty - By teacher - By course


INFO0016-1

Introduction to the Theory of Computation

[ version française ]

Duration :30h Th, 30h Pr
Credits/ECTS :
4th year of the 5 year degree in civil engineering in electricity (electronics)6,5
4th year of the 5 year degree in civil engineering in computer sciences5,5
2nd "licence" in computer6
2nd year of Master's degree in computer sciences,6
Holder(s) :Pierre Wolper
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é (2ième édition), InterEditions, 2001.
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: Xavier Hainaut - Tél. 04/366 26 34 - e-mail hainaut@montefiore.ulg.ac.be(legay@montefiore.ulg.ac.be)
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.




ULg : Students and Studies Administration - Academic Affairs
Contact : Monique Marcourt, direction A.E.E.
Date of data : 27/02/2006
Developed by SEGI