Probleme de decision

Probleme de decision

Problème de décision

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, 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 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. 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.

Voir aussi

Ce document provient de « Probl%C3%A8me de d%C3%A9cision ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Probleme de decision de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Problème de décision — 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… …   Wikipédia en Français

  • DÉCISION — La réflexion moderne sur la question de savoir quel parti prendre lorsqu’on se trouve confronté à un choix difficile a été esquissée pour la première fois par Blaise Pascal, au XVIIe siècle, dans le fameux texte du «pari» sur l’entrée dans la… …   Encyclopédie Universelle

  • Problème décisionnel — Décision La décision est le fait d effectuer un choix lors de la confrontation à un problème afin de le résoudre. Il existe au moins trois grandes approches du concept de décision : La première estime que la décision est un choix de type… …   Wikipédia en Français

  • Decision — Décision La décision est le fait d effectuer un choix lors de la confrontation à un problème afin de le résoudre. Il existe au moins trois grandes approches du concept de décision : La première estime que la décision est un choix de type… …   Wikipédia en Français

  • Probleme de la decision — Problème de la décision En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est à dire s il se dérive… …   Wikipédia en Français

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Probleme SAT — Problème SAT On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une valuation sur un ensemble de variables propositionnelles[1] telle qu… …   Wikipédia en Français

  • Probleme du voyageur de commerce — Problème du voyageur de commerce Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce …   Wikipédia en Français

  • Problème de couverture des sommets — Problème de couverture de sommets En Théorie des graphes, le problème de couverture de sommets est un problème NP complet et c est l un des 21 problèmes NP complets de Karp. Il est souvent utilisé en théorie de la complexité pour prouver que d… …   Wikipédia en Français

  • Problème NP-complet — En théorie de la complexité, un problème NP complet est un problème de décision vérifiant les propriétés suivantes : Il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”