This HTML5 document contains 43 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n11http://g.co/kg/m/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-elhttp://el.dbpedia.org/resource/
n7http://fr.dbpedia.org/resource/Modèle:
wikipedia-frhttp://fr.wikipedia.org/wiki/
n19http://fr.dbpedia.org/resource/Modèle:Traduction/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n5http://ma-graph.org/entity/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Problème_de_recherche
rdfs:label
Problème de recherche Suchproblem
rdfs:comment
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
owl:sameAs
n5:201789804 n11:0545mf dbpedia-el:Πρόβλημα_αναζήτησης dbr:Search_problem dbpedia-pt:Problema_de_busca wikidata:Q2362762 dbpedia-de:Suchproblem
dbo:wikiPageID
9238925
dbo:wikiPageRevisionID
125337826
dbo:wikiPageWikiLink
dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Stable_(théorie_des_graphes) dbpedia-fr:Algorithme category-fr:Théorie_de_la_complexité_des_algorithmes dbpedia-fr:Théorie_des_graphes dbpedia-fr:Counting_problem_(complexity) dbpedia-fr:Relation_binaire dbpedia-fr:Couplage_(théorie_des_graphes) dbpedia-fr:Optimization_problem dbpedia-fr:Fonction_successeur dbpedia-fr:Machine_de_Turing dbpedia-fr:État_(informatique) dbpedia-fr:Automate_fini dbpedia-fr:Function_problem dbpedia-fr:Informatique_théorique dbpedia-fr:Problème_de_décision dbpedia-fr:Clique_(théorie_des_graphes) category-fr:Calculabilité dbpedia-fr:Problème_algorithmique dbpedia-fr:Théorie_de_la_calculabilité dbpedia-fr:Goal_state
dbo:wikiPageLength
4308
dct:subject
category-fr:Théorie_de_la_complexité_des_algorithmes category-fr:Calculabilité
prop-fr:wikiPageUsesTemplate
n7:, n7:Portail n7:Références n19:Référence
prov:wasDerivedFrom
wikipedia-fr:Problème_de_recherche?oldid=125337826&ns=0
foaf:isPrimaryTopicOf
wikipedia-fr:Problème_de_recherche
dbo:abstract
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.