« Au seuil de la complexité calculatoire »
in Pour la science, 295 (05/2002), p.52-60.
|
Titre :
|
Au seuil de la complexité calculatoire (2002)
|
|
Type de document :
|
Article : texte imprimé
|
|
Dans :
|
Pour la science (295, 05/2002)
|
|
Article en page(s) :
|
p.52-60
|
|
Langues de la publication :
|
Français
|
|
Descripteurs
|
[UNESCO] Algorithme
|
|
Mots-clés :
|
problème mathématique/informatique appliquée
|
|
Résumé :
|
Les changements brusques de comportement, courants en physique, existent également en informatique. La transposition de l'analyse et des concepts physiques aux problèmes d'optimisation aide les mathématiciens à en démêler la complexité. L'algorithme de Davis, Putnam et Loveland appliqué à la résolution d'un problème SAT. Les problèmes NP-complets et les phénomènes de seuil.
|
|
Nature du document :
|
Article de périodique
|
