Duration
26h Th, 26h Pr
Number of credits
Lecturer
Language(s) of instruction
English language
Organisation and examination
Teaching in the first semester, review in January
Schedule
Units courses prerequisite and corequisite
Prerequisite or corequisite units are presented within each program
Learning unit 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 learning unit
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.
Prerequisite knowledge and skills
Knowledge of programming
Planned learning activities and teaching methods
1st quadrimester - Lectures, problem sessions.
The lectures and problem sessions are given in English. 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, hybrid learning)
Face-to-face.
The room contains 70 seats. If every second seat has to be used, a reservation procedure is used in order to accomodate the 35 first registrations. This is possibly renewed every week. All lectures are podcasted.
Organisational adjustments related to the current health context
If face-to-face is allowed:
Written exam mixing theory (true/false + proofs) and exercises similar to the problem sessions.
If remote evaluation as imposed by the health conditions:
Written exam to be done at home in exam conditions, mixing theory (true/false only) and exercises similar to the problem sessions.
The pdf with the exam questions is available on the dox repository at the time of the exam. The scan of the student's answers is to be uploaded on the submission platform https://submit.montefiore.ulg.ac.be
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
Below you will find information on the evaluation methods planned for in-person and remote exams as well as those planned for hybrid sessions. Depending on how the health crisis evolves, the chosen method will be communicated to you no later than one month before the start of the exam session.
Written exam including both theory and exercise questions (no oral exam).
Work placement(s)
Organizational remarks
All documents are available through the repository:
https://dox.uliege.be/index.php/s/v2rwRkkAGXzPjDA
This repository contains all slides, all annotated slides, the exercises, the previous exams and the weekly links to book a seat in the room.
Contacts
Quentin Louveaux
q.louveaux@uliege.be
04/366 27 89