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
En bref
Crédits ECTS : Cf UE
Contact(s)
Lieu(x)
- Toulouse