Problème de décision

On parle de problème de décision dans des contextes variés. Cet article est conçu pour décrire ce terme en informatique, ou en mathématiques.



Catégories :

Décision - Statistiques - Algorithmique

Recherche sur Google Images :


Source image : fr.wikipedia.org
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • le problème de décision est bien NP.... aUneSolution () avec l'option exh du programme de test Quelle est la complexité d'aUneSolution () ? Si... (source : fil.univ-lille1)

On parle de problème de décision dans des contextes variés. Cet article est conçu pour décrire ce terme en informatique, ou en mathématiques.

En algorithmique, un problème de décision est une question mathématiquement définie portant sur des paramètres donnés sous forme manipulable informatiquement, et demandant une réponse par oui ou non.

Ainsi, l'ensemble des villes et de longueur inférieure à d, est un problème de décision.

Un problème de décision peut être indécidable s'il n'existe aucun programme informatique qui permette de le résoudre (sans restriction de mémoire ou temps), ce qu'on formalise par l'impossibilité de répondre au problème avec une machine de Turing.

Certains problèmes de décision décidables sont cependant reconnus comme non traitables en pratique pour des raisons de trop grande complexité des calculs. La théorie de la complexité des algorithmes donne une hiérarchie des complexités formelles. Surtout, un problème NP-complet n'aura pas de solution exacte en pratique, sauf sur des cas spécifiques ou sur des instances de taille suffisamment petite.

Voir aussi

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Probl%C3%A8me_de_d%C3%A9cision.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu