MA5011 - Complexité

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.

Volume horaire (h)

  • Cours magistraux : 20

Examens

Nombre total d'heures d’évaluation : 3

Ce cours fait partie de la formation

En bref

Crédits ECTS : Cf UE

Nombre d'heures 23

Contact(s)

Nicolas BARNIER

Tél : +33 5 62 25 95 06

Email : nicolas.barnier @ enac.fr

Jean-Baptiste GOTTELAND

Tél : +33 5 62 25 95 84

Email : jean-baptiste.gotteland @ enac.fr