Problème de décision | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

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. 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, semi-décidable ou prouvable si l'ensemble A est récursivement énumérable. Et dans le cas contraire, où le problème P n'est ni décidable, ni partiellement décidable, il est dit indécidable. Il y a des problèmes fondamentaux qui sont indécidables, c'est le cas du problème de l'arrêt. L'ensemble des nombres premiers est un exemple classique de problème de décision décidable. Il est en effet possible de savoir si un entier naturel est un nombre premier en vérifiant qu’aucun entier naturel le précédant, hormis , ne fait partie de ses diviseurs. Bien que l'on connaisse des méthodes beaucoup plus efficaces de test de primalité, l'existence d'une méthode correcte suffit pour établir la décidabilité. Un exemple plus général, sortant du contexte mathématique ou informatique, serait de considérer un cas concret, afin de mieux visualiser les notions de « décidable » ou « calculable », et au contraire d'« indécidable » ou « incalculable ». Ainsi, considérons un jeu dans lequel un voyageur se déplace sur Terre avec, à chaque étape de son voyage, l'indication seule de sa prochaine destination.

À 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 (16)

Personnes associées (9)

Unités associées (1)

Concepts associés (65)

Cours associés (68)

Séances de cours associées (563)

MOOCs associés (11)

Théorie de la calculabilité

La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique. La calculabilité (parfois appelée « computationnalité », de l'anglais computability) cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.

NP (complexité)

La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.

Problème de décision

CS-308: Quantum computation

The course introduces teh paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

ME-372: Finite element method

L'étudiant acquiert une initiation théorique à la méthode des éléments finis qui constitue la technique la plus courante pour la résolution de problèmes elliptiques en mécanique. Il apprend à applique

Wasserstein Distributionally Robust Learning

Soroosh Shafieezadeh Abadeh

Many decision problems in science, engineering, and economics are affected by uncertainty, which is typically modeled by a random variable governed by an unknown probability distribution. For many pra

EPFL2020

"Dice"-sion Making under Uncertainty: When Can a Random Decision Reduce Risk?

Daniel Kuhn, Wolfram Wiesemann

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 inv

2019

Double Refinement Network for Efficient Monocular Depth Estimation

Nikita Durasov

Monocular depth estimation is the task of obtaining a measure of distance for each pixel using a single image. It is an important problem in computer vision and is usually solved using neural networks

IEEE2019

With every smartphone and computer now boasting multiple processors, the use of functional ideas to facilitate parallel programming is becoming increasingly widespread. In this course, you'll learn th

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d

Algorithme caché du sous-groupe

Continue la discussion sur le problème caché du sous-groupe de Simon, en se concentrant sur la recherche d'une base.

Comprendre le chaos dans les théories quantiques de champ

Explore le chaos dans les théories quantiques des champs, en se concentrant sur la symétrie conforme, les coefficients OPE et l'universalité de la matrice aléatoire.

Calcul distribué I

Explore le calcul distribué entre deux parties dans un contexte éloigné.