Computational complexity

Catalogue des cours de Télécom SudParis

Code

IGFE CSC 7341

Domaine

Informatique

Programme

Master

Langue

Anglais/English

Crédits ECTS

2,5

Heures programmées

21

Charge de travail

51

Coordonnateur(s)

Département

  • Réseaux et Services Multimédia Mobiles

Acquis d'apprentissage

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.

Contenu

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.

Prérequis

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.

Evaluation

The evaluation includes 3 hours written exam.
The class also contains the continuous evaluation represented as homework, laboratories and students’ presentations.

Fiche mise à jour le 13/07/2018