Effective solving of problems requires having an idea of their algorithmic difficulties, i.e. the possibility of solving them in an efficient manner in time and space with algorithms. The aim with this unit is to present the classification of problems currently used in relation to these questions. Classes N and NP will thus be defined, along with the famous question "P = NP?" which is at the core of the Theory of Complexity and where NP-Complete problems play an essential role. Other classes such as NP-Hard problems will also be covered. Finally, if a problem cannot be efficiently solved exactly an approximation solution might be tried. The last section of the unit will deal with this notion with an overview of the numerous questions it sets. A more specific study of possible strategies of approximation will be covered in the other course unit.
| On completion of the unit, the student will be capable of: | Classification level | Priority |
|---|---|---|
| Understanding the theoretical necessity and practical interest of studying the “difficulty” of a problem solution and some of its particular versions. | 2. Understand | Essential |
| Identifying the main problems in this field and their variations, along with certain of their applications | 1. Knowledge | Essential |
| Having a rigorous knowledge of the principle problem classes and their mutual relations. | 1. Knowledge | Essential |
| Knowing the question of approximation and what can be expected from the solution | 1. Knowledge | Important |
| Using the acquired notions to attempt a classification of a problem and some of its sub-problems | 3. Apply | Important |
| Using technical tools to compare problems and their different versions | 3. Apply | Important |
| Applying a general methodology of algorithmic problem solving | 4. Analyse | Useful |
| Broadening his knowledge of other questions of problem classes. | 2. Understand | Useful |
| Percentage ratio of individual assessment | Percentage ratio of group assessment | ||||
|---|---|---|---|---|---|
| Written exam: | 75 | % | Project submission: | 0 | % |
| Individual oral exam: | 0 | % | Group presentation: | 0 | % |
| Individual presentation: | 0 | % | Group practical exercise: | 0 | % |
| Individual practical exercise: | 25 | % | Group report: | 0 | % |
| Individual report: | 0 | % | |||
| Other(s): 0 % | |||||
| Type of teaching activity | Content, sequencing and organisation |
|---|---|
| Course + Supervised studies | Nature, Type and Formulation of Classes P and NP problems |
| Course + Supervised Studies | Structure of NP: NP – Complete problems, Boundary P - NP |
| Course + Supervised studies | NP problems – Hard and other problem classes. Complexity in space. |
| Course + Supervised Studies | Question of approximation |