Duration
30h Th, 20h Pr
Number of credits
| Master in mathematics (120 ECTS) | 8 crédits | |||
| Master in mathematics (60 ECTS) | 8 crédits |
Lecturer
Language(s) of instruction
French 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
This lecture deals with this fundamental question : what kind of problem (being admitted that it can be coded into a computer) can be solved by a computer program ?
To be able to answer this question, we first have to give a formal definition of the notions of algorithm and of computable function. This is done through the use of Turing machine. The main topics are : primitive recursive functions, recursive functions, computable functions, Turing machines, universal Turing machine, Church-Turing's thesis, decidable problem, the halting problem, decidable and acceptable languages, Cook's theorem, complexity theory, NP-completeness, ...
The lecture ends with the presentation of some well-known NP-complete problems (in optimization or graph theory for instance) like the travel salesman problem.
Learning outcomes of the learning unit
At the end of this course, the student will master fundamental notions arising in computability and complexity theory as well as the corresponding proofs. In particular, the student will integrate the concepts of computable functions and decision problem. He/she will be able to explain, using convenient reductions, that some problems do not have any algorithmic solution. Also he/she will be able to build some Turing machines and prove NP-completeness of classical problems.
Prerequisite knowledge and skills
No specific programming skill is needed.
Planned learning activities and teaching methods
Theoretical lectures using "blackboard and chalk" interacting with students. During exercises sessions, students are facing exercises that must be solved.
Mode of delivery (face-to-face ; distance-learning)
Lectures ("chalk and blackboard" interacting with students) are dedicated to theoretical aspects of Turing machines and complexity theory. Practical sessions are devoted to solve exercises and to enlighten the concepts presented during the lecture. Detailed schedule will be given at the beginning of the academic year.
Recommended or required readings
Lecture notes are available (in French). These are by M. Rigo, academic year 2009-2010. Some textbooks:
- R. Cori, D. Lascar, Logique Mathématique, Dunod (1993).
- M. R. Garey, D. S. Johnson, Computers and Intractability, A guide to the Theory of NP-Completeness, W. H. Freeman and Company, (1979).
- H. R. Lewis, C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, (1981).
- A. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Society. Second Series 42, 230-265, (1936).
- P. Wolper, Introduction à la calculabilité, Dunod (2006).
Assessment methods and criteria
The final examination is divided into an oral part and a written exam. The oral exam is devoted to the theory but also direct applications of the theory (student may be asked to solve a small exercise on the blackboard or on a sheet of paper). The written exam evaluate the comprehension of the material of the exercice sessions.
Work placement(s)
Organizational remarks
This course is organized once every two years : 2017-2018, 2019-2020, ...
Some useful informations are given on
http://www.discmath.ulg.ac.be/charlier/enseignement.html.
Contacts
Émilie Charlier - titulaire
Manon Stipulanti - assistante
Département de Mathématique (B37)
Quartier Polytech 1
Allée de la Découverte,12
B-4000 Liège
Tél. : +32 4 366.93.84
E-mail :
echarlier@uliege.ac.be
m.stipulanti@uliege.ac.be