N.B.: Ces
descriptif et programme sont
donnés à
titre indicatif et peuvent évoluer.
Table des
matières
Nouveautés
- 03/05/17 : clôture des inscriptions : 11 inscrits.
- 31/01/17 : création de cette fiche.
Informations
générales
- Thème
: P=NP? (Machines de
Turing et complexité des problèmes)
- Date de la session : Mercredi 10 mai 2017
- 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).
Inscription libre
mais obligatoire, voir ci-dessous.
- Lieu
: Télécom ParisTech, 46, rue Barrault, 75013 Paris (comment
venir?).
- Volume
horaire et programmation
: voir ci-dessous
- 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
- Seuil
d'ouverture / Numerus clausus : 5 / 50
- Inscription
(libre mais obligatoire) : Inscription 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 :
- 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
- 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
Documents
dernière
modification 3-mai-2017