Institut Polytechnique de Paris Introduction aux classes de complexité le Mercredi 28 avril 2021

Références aux programmes : MPI 9

Résumé du contenu

Le stage propose une introduction à la théorie de la complexité algorithmique des problèmes. On propose d’abord une typologie des problèmes considérés : problème de décision (problèmes posant une question dont la réponse est « oui » ou « non» ; exemple : un entier est-il premier ?), problème de valeur optimale en optimisation combinatoire (déterminer la valeur optimale d’une fonction définie sur un ensemble fini ; exemple : déterminer la distance minimum que parcourt un voyageur de commerce pour visiter ses clients), problème de structure optimale en optimisation combinatoire (déterminer un élément optimisant une fonction définie sur un ensemble fini ; exemple : déterminer le parcours qu'effectue un voyageur de commerce pour visiter ses clients en minimisant la distance parcourue). On étudie les liens entre ces problèmes. On définit les classes : P, NP, co-NP. A l’aide des transformations polynomiales, on définit la notion de compl ́etude. Tout ceci permet de distinguer entre eux les problèmes polynomiaux, pseudo-polynomiaux, NP- complets, co-NP-complets, NP-difficiles, notions que l’on illustre à l’aide d’exemples classiques.

INSCRIPTION

Lien d’inscription : ICI

Intervenant : Olivier Hudry (Télécom Paris) olivier.hudry@telecom-paris.fr.

Horaire : Deux blocs de 3h : 9h-12h et 14h-17h.

Format : cours magistral.

Public visé : Tout public, notamment professeurs de MPI. Il est attendu que le public connaisse les définitions de base en algorithmique (dont la complexité d’un algorithme) et en théorie des graphes.

Numerus clausus : Aucun

Mots-clés : complexité, classe P, classe NP, classe co-NP, transformations polynomiales, problèmes polynomiaux, problèmes pseudo-polynomiaux, problèmes NP-complets, problèmes co-NP-complets, problèmes NP-difficiles

Langage : pas de programmation