Prepas.org

Le site de l'UPS pour les Classes Préparatoires aux Grandes Écoles

Télécom ParisTech P=NP? (Machines de Turing et complexité des problèmes) le Vendredi 13 mai 2016

Thème : P=NP? (Machines de Turing et complexité des problèmes)

Dates de la session : Vendredi 13 mai 2016

Type de stage : Cours (il n'y a pas de travaux pratiques prévus pour ce stage).

Auditoire attendu : les professeurs de mathématiques supérieures et spéciales, en mathématiques, physique, chimie, informatique et sciences de l'ingénieur. Pré-requis : rudiments de programmation (variables, boucles).

Lieu : Télécom ParisTech, 46, rue Barrault, 75013 Paris

Responsable pédagogique : Olivier Hudry

Contact : liesse@telecom-paristech.fr

Intervenants : Olivier Hudry, enseignant-chercheur au département InfRes de Télécom ParisTech.

Page Web de présentation : (maintenue par Télécom ParisTech ) ici

Seuil d'ouverture / Numerus clausus : 5 / 50

Inscription (libre mais obligatoire) avant le 6 mai 2016

de préférence en ligne ICI
ou par mél à liesse@telecom-paristech.fr

Synopsis
Les machines de Turing constituent un modèle abstrait d'un ordinateur et permettent de définir rigoureusement ce qu'est un algorithme. Elles sont utilisées en particulier dans le domaine de la calculabilité (est calculable ce qui l'est par une machine de Turing) et permettent de définir la complexité des algorithmes. La complexité algorithmique permet à son tour d'aborder la complexité des problèmes, dont la fameuse question ouverte (question qui constitue un des sept problèmes recensés par l'institut de mathématiques Clay sous le nom de "problèmes du prix du millénaire" et associés chacun à un prix de un million de dollars) : P = NP ?

Plus précisément, ce stage, qui s'inscrit dans le domaine de l'informatique théorique et des mathématiques discrètes, se propose d'aborder les points suivants :

- description des machines de Turing, déterministes ou non déterministes ;

- classification des problèmes en optimisation combinatoire : problèmes de décision (appelés aussi problèmes de reconnaissance), problèmes d'optimisation, problèmes de recherche ; liens algorithmiques entre problèmes d'optimisation et problèmes de décision

- définition des classes de complexité P et NP pour les problèmes de décision

- question de l'égalité entre P et NP ou de l'inclusion stricte de P dans NP

- transformations polynomiales et problèmes NP-complets

- problèmes (de décision, d'optimisation, de recherche...) NP-difficiles.

NB :
1. il n'y a pas de travaux pratiques prévus pour ce stage ;
2. des connaissances élémentaires en théorie des graphes sont les bienvenues, mais ne sont pas indispensables.

Programme :

J1 Matin
9h30 - 9h45 : Accueil (Hall Barrault)
9h45 - 10h00 : Présentation du stage
10h00 - 12h30 (incluant une pause) : machines de Turing déterministes et non déterministes, classification des problèmes en optimisation combinatoire (problèmes de décision, problèmes d'optimisation, problèmes de recherche), liens algorithmiques entre problèmes d'optimisation et problèmes de décision

12h30 Déjeuner

J1 Après-midi
13h30 - 17h00 (incluant une pause) : classes P et NP, transformations polynomiales et problèmes NP-complets, théorème de Cook, classe co-NP, problèmes NP-difficiles.
17h00 : Clôture