 | |
| INFO0212-2 | Computability and complexity theory
 |
|
| Duration : | 20h Th, 20h Pr |
|
| Credits/ECTS : |
|
|
| Holder(s) : | Michel Rigo |
|
| Language : | French language |
|
| Course 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. |
|
| Course objective : | To present fundamential notions in computability and complexity theory. It is interesting to notice that some problems have no algorithmic solution. |
|
| Prerequisites : | Basic knowledge in graph theory. No specific programming skill is needed. |
|
| Organization : | Lectures are dedicated to theoretical aspects of Turing machines and complexity theory. Pratical 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. |
|
| Written notes : | Lecture notes are available (in french). |
|
| Assessment : | The final examination is an oral one devoted to the theory (mainly proofs of theorems) but also direct applications of the theory (student may be asked to solve a small exercise on the blackboard). The expected knowledge needed for this examination will be officially announced during the year. |
|
| Contacts : | M. Rigo
Institute of Mathematics (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
| Remarks : | Some useful informations (in particular lecture notes) are given on
http://www.discmath.ulg.ac.be/ |
|
