FR
EN
Calculabilité, complexité, Résolution de problèmesEA Sécurité Fondamentale (STI)
Computability, Complexity, and Problem Solving
Teaching unit EA Fundamental Security · S08T_SFO1 | EC Code S08A_SF1-1
6ECTS (EU)
1Coefficient
21:20Hours
Séquencement
Learning objectives
Give some advanced aspects of the theory of computability and complexity. Understand the concepts of indecisability and intractability. Understand the concept of reduction. Understand different problem approximation techniques.
Prerequisites
| Module | Teaching unit | Semester |
|---|---|---|
| Algorithms and Complexity | Programming Principles | S5 |
| Logic | Programming Principles | S5 |
| Language Theory | Programming Principles | S5 |
| Modeling and Graph Theory | Development and Mathematics for Engineers | S6 |
Program
The programme is divided into several aspects
- Turing machines
- Thesis of Church-Turing,
- Simulations
- Decidability, Indecidability and Reduction,
- Theorem of the Halt
- Measurement of complexity,
- Class P (Polynomial),
- The NP class (Non-Deterministic),
- NP-Complusion (polynomial reduction, Cook Levin's Theorem),
- NP-complete problems
References
- M.R. Garey, D.S. Johnson,
- Apt, Krzysztof R., "Principles of constraint programming", Cambridge University Press
Skills
3| Ref. | Verb | Description | Level |
|---|---|---|---|
| C2_1 | recognize | Know the limits of programming and related concepts (calculation, NP-Completion) | 1 |
| C2_1 | demonstrate | Determine the difficulty of an algorithmic problem | 2 |
| C2_1 | analyze | Model a problem and use appropriate methods to solve it | 3 |