« NP-complétude » : différence entre les versions


Aucun résumé des modifications
Balise : Éditeur de wikicode 2017
m (Remplacement de texte — « <small> loc. nom. fém. </small> » par « <small> féminin </small> »)
(9 versions intermédiaires par 2 utilisateurs non affichées)
Ligne 1 : Ligne 1 :
==Domaine==
[[Category:Vocabulary2]]
[[Category:Algorithme]]
Algorithme<br>
[[Catégorie:Théorie de la complexité]]
Théorie de la complexité<br>
[[Category:Coulombe2]]
[[Catégorie:Scotty2]]
[[Category:GRAND LEXIQUE FRANÇAIS]]
==Définition==
==Définition==
En théorie de la complexité, la NP-complétude concerne l'étude des problèmes de la classe de complexité NP-complet, des problèmes qui appartiennent à la fois à la classe de complexité NP et à la classe de complexité NP-difficile.  
En théorie de la complexité, la NP-complétude concerne l'étude des problèmes de la classe de complexité NP-complet, des problèmes qui appartiennent à la fois à la classe de complexité NP et à la classe de complexité NP-difficile.  
Ligne 15 : Ligne 5 :


==Français==
==Français==
'''NP-complétude''' n.f.
'''NP-complétude'''   <small> féminin </small>


'''NP-complet''' n.f.
'''NP-complet'''   <small> féminin </small>


==Anglais==
==Anglais==
'''NP-completeness'''
'''NP-completeness'''


<small>




Source: [http://www.uqac.ca/rebaine/8INF806/NPcompletudecours.pdf Djamal Rebaïne, UQAC]




Source: [http://www.uqac.ca/rebaine/8INF806/NPcompletudecours.pdf Djamal Rebaïne, UQAC]
 
 
[[Category:Algorithme]]
[[Catégorie:Théorie de la complexité]]
[[Category:GRAND LEXIQUE FRANÇAIS]]

Version du 22 mai 2020 à 12:11

Définition

En théorie de la complexité, la NP-complétude concerne l'étude des problèmes de la classe de complexité NP-complet, des problèmes qui appartiennent à la fois à la classe de complexité NP et à la classe de complexité NP-difficile.

Bien que toute solution d'un problème NP-complet puisse être vérifiée rapidement (en temps polynomial), il n'existe aucun moyen efficace connu pour trouver une première solution. Un exemple classique de problème NP-complet est le problème du voyageur de commerce, dont le but est de déterminer le trajet le plus court pour visiter un grand nombre de villes. La difficulté d'un problème NP-complet provient du fait qu’il n’existe pas d’algorithme connu pour trouver une solution rapidement.

Français

NP-complétude féminin

NP-complet féminin

Anglais

NP-completeness


Source: Djamal Rebaïne, UQAC