Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
229 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Le problème et le problème next up previous
suivant: La conjecture de Hodge monter: Les sept problèmes du précédent: Les sept problèmes du

Le $ P$ problème et le $ NP$ problème

Imaginez que vous deviez organiser le logement d'un ensemble de 400 étudiants. Vous ne disposez que d'une seule résidence comprenenant exactement 100 chambres, aussi vous êtes amené à ne retenir qu'une partie de ces étudiants. Pour compliquer l'affaire, le doyen de votre université vous impose une liste de paires d'étudiants à ne pas faire habiter ensemble. Le nombre de possibilités pour un tel arrangement dépasse le nombre d'atomes dans l'univers et on ne pourra jamais construire un ordinateur capable de produire au moyen de sa seule force de calcul une liste convenable. Le problème, qui est un des plus importants actuellement en mathématiques appliquées à l'informatique, est bien entendu de savoir si il existe un procédé permettant de calculer la liste voulue en un temps limité. A l'opposé, si on vous donne une liste de 100 étudiants, il est facile de vérifier si cette liste satisfait ou non aux critères qu'on vient de fixer. On appelle $ P$ problème tout problème qui consiste comme ici à trouver une liste d'éléments dans un ensemble donné et ce relativement à un critère fixé à l'avance. Le $ NP$ problème est opposé au $ P$ problème .Il consiste à vérifier si une liste donnée est en adéquation avec les conditions données au préalable. Stephen Cook et Leonid Levin ont les premiers, et de manière indépendante, formulés le $ P$ problème et le $ NP$ problème en 1971.


next up previous
suivant: La conjecture de Hodge monter: Les sept problèmes du précédent: Les sept problèmes du
Emmanuel_Vieillard-Baron
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page