Code
IGFE CSC 7341
Domain
Informatique
Program
Master
Language
Anglais/English
ECTS Credits
2,5
Class hours
21
Workload
51
Program Manager(s)
Department
- Réseaux et Services Multimédia Mobiles
Organisation
Cours/TD/TP/projet/examen :Learning objectives
Turing Machines. Decision problems. Decidable and undecidable problems. The Halting Problem (Lecture and exercises).
Algorithm and Problem Complexity. Complexity classes. Time and Space Complexity. Hardness and completeness of (decision) problems (Lecture and exercises).
SAT-problem. Cook's theorem. 2-SAT and 3-SAT problems (Lecture and exercises).
Hamiltonian path problem and Hamiltonian cycle problem. The Clique problem (Lecture and exercises).
Complexity issues and corresponding problems in related fields of Communication Networks:
- Complexity issues in information security (Lecture, discussion and students presentations’).
- Complexity issues in software testing (Lecture, discussion and students presentations’).
Discussion on P =? NP.
Discussion on alternative complexity definitions.
Individual laboratories on the listed subjects will be performed. The tasks include the estimation of the correlation between the theoretically proven complexity and the software quality parameters, such as performance, disc load, energy consumption, etc.
Prerequisites
Students are required to have good mathematical foundations, including logics, combinatorial analysis, graph theory, Boolean algebra, algorithms and data structures, software engineering and general network architectures.
Content
The main objective of the course is the study of the analysis of algorithms as well as widely met complexity classes. The students need to know the ‘classical’ problems met in the computer communications and their complexity. After the class, they should also be able to estimate the computational complexity of a given algorithm, in time and space.
Evaluation
The evaluation includes 3 hours written exam.
The class also contains the continuous evaluation represented as homework, laboratories and students’ presentations.