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‚ÄĚ

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.