MA5011 - Complexité

Objectifs

Objectif général :

Comprendre et savoir calculer la complexité des algorithmes séquentiels.
Savoir reconnaître les problèmes combinatoires et être capable de prouver
leur difficulté.
Appréhender les systèmes cryptographiques.

Objectifs détaillés :

Comprendre les différentes notions de complexité d'un algorithme et être capable d'analyser les algorithmes séquentiels non-récursifs et récursifs.
Comprendre la complexité des problèmes de décision et le modèle de calcul sous-jacent de la machine de Turing non-déterministe.
Maîtriser la réduction de Turing entre problème et les classes P, NP et NPC.
Reconnaître et prouver la NP-complétude ou la NP-difficulté des problèmes d'optimisation combinatoire.
Comprendre comment l'utilisation de problèmes difficiles permet de créer des cryptosystèmes
asymétriques.

Place dans le cursus

1ère moitié du semestre 9