Problème de décision
Un article de Wikipédia, l'encyclopédie libre.
|
|
On parle de problème de décision dans des contextes variés. Cet article est destiné à 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, savoir si, étant donné les distances entre les villes d'une carte et une distance d, il existe un chemin passant par toutes les 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 que l'on formalise par l'impossibilité de répondre au problème à l'aide d'une machine de Turing.
Certains problèmes de décision décidables sont cependant considérés comme non décidables en pratique pour des raisons de trop grande complexité des calculs la théorie de la complexité donne une hiérarchie des complexités formelles. En particulier, un problème NP-complet n'aura pas de solution exacte en pratique, sauf sur des cas particuliers ou sur des instances de taille suffisamment petite.
