2024-2025 / INFO0212-2

Algorithmics and computability

Duration

30h Th, 20h Pr

Number of credits

 Master in mathematics, research focus (Odd years, not organized in 2024-2025) 8 crédits 
 Master in mathematics, teaching focus (Odd years, not organized in 2024-2025) 8 crédits 

Lecturer

Emilie Charlier

Language(s) of instruction

French language

Organisation and examination

Teaching in the first semester, review in January

Schedule

Schedule online

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, hybrid learning)

Face-to-face course


Additional information:

The theoretical part of the course is 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.
If the number of students is greater than or equal to 5, lectures will be given with a board and chalk, in interaction with the students. Otherwise, the organizational arrangements will be discussed at the first course.
 

Course materials and recommended or required readings

Platform(s) used for course materials:
- eCampus


Further information:

The lecture notes are available on eCampus.

The oral course will define the exact material of the course.

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.
  • P. Lecomte, Algorithmique et calculabilité, syllabus 1994-1995.
  • H. R. Lewis, C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.
  • M. Rigo, Algorithmique et calculabilité, syllabus 2009-2010.
  • 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.

Exam(s) in session

Any session

- In-person

oral exam


Additional information:

Oral examination. The exam is devoted to the theory but also to direct applications of the theory illustrated during the exercises sessions. Students may be asked to solve small exercises on the blackboard or on a sheet of paper.

Work placement(s)

Organisational remarks and main changes to the course

This course is organized once every two years : 2021-2022, 2023-2024, ...

Some useful informations are given on eCampus.

Contacts

Émilie Charlier

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.be
 

Association of one or more MOOCs