Problème de décision

Résumé

En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat. Dans le contexte de la calculabilité En théorie de la calculabilité, formuler un problème de décision c'est se poser une question de décidabilité. Il s'agit en fait de rechercher l'existence d'un algorithme résolvant le problème et, s'il existe, de l'expliciter. On dit qu'un problème (de décision) P est décidable si l'ensemble A des éléments qui répondent « oui » à la question posée est récursif. De même, P est dit partiellement décidable,

Source officielle

https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_d%C3%A9cision

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (72)

Chargement

Afficher plus

Publications associées

Chargement

Personnes associées (10)

Personnes associées

Chargement

Unités associées (6)

Unités associées

Chargement

Concepts associés (41)

Concepts associés

Chargement

Cours associés (10)

Cours associés

Chargement

Séances de cours associées (22)

Séances de cours associées

Chargement

Publications associées (72)

A Decision Procedure for (Co)datatypes in SMT Solvers

Andrew Joseph Reynolds

We present a decision procedure that combines reasoning about datatypes and codatatypes. The dual of the acyclicity rule for datatypes is a uniqueness rule that identifies observationally equal codatatype values, including cyclic values. The procedure decides universal problems and is composable via the Nelson-Oppen method. It has been implemented in CVC4, a state-of-the-art SMT solver. An evaluation based on problems generated from theories developed with Isabelle demonstrates the potential of the procedure.

Springer-Verlag Berlin2015

Chargement

Stochastic programming and distributionally robust optimization seek deterministic decisions that optimize a risk measure, possibly in view of the most adverse distribution in an ambiguity set. We investigate under which circumstances such deterministic decisions are strictly outperformed by random decisions which depend on a randomization device producing uniformly distributed samples that are independent of all uncertain factors affecting the decision problem. We find that in the absence of distributional ambiguity, deterministic decisions are optimal if both the risk measure and the feasible region are convex, or alternatively if the risk measure is mixture-quasiconcave. We show that several classes of risk measures, such as mean (semi-)deviation and mean (semi-)moment measures, fail to be mixture-quasiconcave and can therefore give rise to problems in which the decision maker benefits from randomization. Under distributional ambiguity, on the other hand, we show that for any ambiguity averse risk measure there always exists a decision problem (with a nonconvex—e.g., mixed-integer—feasible region) in which a randomized decision strictly dominates all deterministic decisions.

2019

Chargement

Interdiction Games on Markovian PERT Networks

Eli Gutin, Daniel Kuhn, Wolfram Wiesemann

In a stochastic interdiction game a proliferator aims to minimize the expected duration of a nuclear weapons development project, and an interdictor endeavors to maximize the project duration by delaying some of the project tasks. We formulate static and dynamic versions of the interdictor's decision problem where the interdiction plan is either precommitted or adapts to new information revealed over time, respectively. The static model gives rise to a stochastic program, whereas the dynamic model is formalized as a multiple optimal stopping problem in continuous time and with decision-dependent information. Under a memoryless probabilistic model for the task durations, we prove that the static model reduces to a mixed-integer linear program, whereas the dynamic model reduces to a finite Markov decision process in discrete time that can be solved via efficient value iteration. We then generalize the dynamic model to account for uncertainty in the outcomes of the interdiction actions. We also discuss a crashing game where the proliferator can use limited resources to expedite tasks so as to counterbalance the interdictor's efforts. The resulting problem can be formulated as a robust Markov decision process.

Informs2015

Chargement

Afficher plus