Probleme a faire

[Retroe]

Imaginez que vous deviez organiser le logement d'un ensemb
le de 400 étudiants. Vous ne disposez que d'une seule
résidence comprenant exactement 100 chambres, aussi vous êt
es 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 arra
ngement 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 pr
océ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 es
t 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 de 1971


Je vous ais un peu expliquer le probleme svp aidez moi :mur: :mur: :mur: :mur: :mur: :mur: :mur: :mur: :mur: :mur: :mur: