Ê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 Graph Search.
Concept
Problème de recherche
Résumé
En informatique théorique, et plus particulièrement en théorie de la complexité et en théorie de la calculabilité, un problème de recherche est un problème algorithmique associé à une relation binaire. Si R est une relation binaire telle que pour tout (R) ⊆ Γ+ et T une machine de Turing, alors T implante R si:
Si x est tel qu'il existe un y vérifiant R(x, y) alors T accepte l'entrée x en produisant un résultat z tel que R(x, z) (s'il y a plusieurs y, T n'est astreint à n'en trouver qu'un seul)
Si x est tel qu'il n'existe aucune y tel que R(x, y) alors T rejette l'entrée x
De manière intuitive, un problème de recherche consiste à trouver, s'il existe, un objet "y" associé à un objet "x". On considère qu'un algorithme résout le problème si pour tout x, pour lequel un résultat existe, une occurrence est produite en résultat.
De tels problèmes se rencontrent fréquemment en théorie des graphes, en cherchant par exemple certains couplage, cliques, ensemble indépendant, etc.
À noter que le graphe d'une fonction est une relation binaire.
Toute relation R peut être vue comme un problème de recherche et on dit qu'une machine de Turing qui implante R résout le problème de recherche. Tout problème de décision est la restriction d'un problème de recherche qui consiste à assimiler "oui" à "un résultat existe" et "non" à "aucun résultat n'existe":
La définition d'un problème de recherche peut être généralisée à des relations n-aires en utilisant un encodage adéquat.
Un problème de recherche est défini par :
un ensemble d'états,
un état de départ,
un état-cible ou état-test,
une fonction booléenne qui permet de savoir un état donné est l'état-cible,
une fonction successeur,
une application d'un état vers l'ensemble des états possibles
Trouver une solution lorsqu’un algorithme n'est pas fourni, mais lorsqu'on a que la spécification de la solution.
algorithme de recherche générique: soit un graphe, un ensemble de nœuds de départ, et de nœuds d'arrivée, on explore de manière incrémentale les chemins du graphe depuis les nœuds de départ.
Source officielle
À 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.
Proximité ontologique
Publications associées (3)
On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem
We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2020Combinatorial Approach for Data Binarization
This paper addresses the problem of transforming arbitrary data into binary data. This is intended as preprocessing for a supervised classification task. As a binary mapping compresses the total information of the dataset, the goal here is to design such a ...
IDIAP1999Combinatorial Approach for Data Binarization
This paper addresses the problem of transforming arbitrary data into binary data. This is intended as preprocessing for a supervised classification task. As a binary mapping compresses the total information of the dataset, the goal here is to design such a ...
Springer1999Concepts associés (9)
Problème algorithmique
Un problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier.
Computability
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power.
Function problem
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'. A functional problem is defined by a relation over strings of an arbitrary alphabet : An algorithm solves if for every input such that there exists a satisfying , the algorithm produces one such , and if there are no such , it rejects.