Search problem (original) (raw)
Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα αναζήτησης είναι ένα είδος υπολογιστικού προβλήματος που αναπαριστάται από μια . Αν το R είναι μια δυαδική σχέση τέτοια ώστε field(R) ⊆ Γ+ και το T είναι μια μηχανή Turing, τότε το T υπολογίζει το R εάν: * Έστω ότι το x είναι τέτοιο ώστε να υπάρχει κάποιο y όπου R(x,y). Τότε το Τ αποδέχεται x με έξοδο z τέτοια ώστε R(x,z) (μπορεί να υπάρχουν πολλαπλά y, αλλά το Τ χρειάζεται να βρει μόνο ένα από αυτά) * Έστω ότι το x είναι τέτοιο ώστε δεν υπάρχει κανένα y όπου R(x,y). Τότε το Τ απορρίπτει το x
| Property | Value |
|---|---|
| dbo:abstract | Als Suchproblem bezeichnet man in der theoretischen Informatik ein Problem, bei dem zu einer gegebenen Eingabe eine bestmögliche Lösung gesucht ist. Das Suchproblem unterscheidet sich vom zugehörigen Optimierungsproblem darin, dass beim Optimierungsproblem nicht die Lösung selbst, sondern der ihr zugeordnete Zahlenwert gesucht ist. Formal ist ein Suchproblem definiert durch eine in einer symbolischen Repräsentation dargelegte Start- und Zielzustandsbeschreibung, einer Menge von Operatoren und einer Funktion, welche bestimmt, ob der aktuelle Zustand ein Zielzustand ist. Die Anwendung aller vorhandenen Operatoren auf den Startzustand und auf die so resultierenden Zustände spannen den Suchraum auf, welcher häufig auch als Suchbaum notiert werden kann. Zum Beispiel handelt es sich beim 8-Damen-Problem um ein Suchproblem, bei dem der Suchraum die Menge aller Schachbretter mit maximal 8 darauf platzierten Damen ist. Der Startzustand ist hier ein leeres Schachbrett, die Zielfunktion akzeptiert Schachbretter mit 8 Damen, die sich nicht gegenseitig bedrohen. Die Operatoren bilden ein Schachbrett S mit Damen ab auf ein Schachbrett mit k+1 Damen, bei dem k Damen auf den gleichen Feldern wie auf S stehen und die zusätzliche Dame auf einem Feld steht, das auf S frei war. (de) Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα αναζήτησης είναι ένα είδος υπολογιστικού προβλήματος που αναπαριστάται από μια . Αν το R είναι μια δυαδική σχέση τέτοια ώστε field(R) ⊆ Γ+ και το T είναι μια μηχανή Turing, τότε το T υπολογίζει το R εάν: * Έστω ότι το x είναι τέτοιο ώστε να υπάρχει κάποιο y όπου R(x,y). Τότε το Τ αποδέχεται x με έξοδο z τέτοια ώστε R(x,z) (μπορεί να υπάρχουν πολλαπλά y, αλλά το Τ χρειάζεται να βρει μόνο ένα από αυτά) * Έστω ότι το x είναι τέτοιο ώστε δεν υπάρχει κανένα y όπου R(x,y). Τότε το Τ απορρίπτει το x Διαισθητικά, το πρόβλημα έγκειται στην εξεύρεση κάποιας δομής "y" στο αντικείμενο "x". Λέμε ότι ένας αλγόριθμος επιλύει το πρόβλημα αν υπάρχει τουλάχιστον μια τέτοια δομή και ο αλγόριθμος μπορεί τελικά να μας δώσει στην έξοδό του μια από αυτές. Διαφορετικά ο αλγόριθμος σταματά με κατάλληλο μήνυμα ("Το αντικείμενο δε βρέθηκε" ή κάτι παρόμοιο). Τέτοια προβλήματα προκύπτουν αρκετά συχνά στη θεωρία γράφων, για παράδειγμα, όπου ενδιαφέρουν ιδιαίτερα οι γράφοι αναζήτησης για δομές όπως κάποιο συγκεκριμένο , κλίκες, ανεξάρτητο σύνολο, κλπ. Σημειώστε ότι ο γράφος μιας συνάρτησης είναι μια δυαδική σχέση και ότι αν το Τ υπολογίζει μια μερική συνάρτηση τότε υπάρχει το πολύ μία μόνο πιθανή έξοδος. Μια σχέση R μπορεί να θεωρηθεί ως ένα πρόβλημα αναζήτησης και μια μηχανή Turing που υπολογίζει την R λέμε επίσης ότι μπορεί και να την επιλύσει. Κάθε πρόβλημα αναζήτησης αντιστοιχεί σε ένα πρόβλημα απόφασης, και συγκεκριμένα: Αυτός ο ορισμός μπορεί να γενικευθεί σε n-μερείς σχέσεις με τη χρήση οποιασδήποτε κατάλληλης κωδικοποίησης η οποία να επιτρέπει πολλαπλές συμβολοσειρές να συμπιεστούν σε μία (για παράδειγμα απαριθμώντας τες διαδοχικά με κάποιο διαχωριστικό). (el) In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If R is a binary relation such that field(R) ⊆ Γ+ and T is a Turing machine, then T calculates R if: * If x is such that there is some y such that R(x, y) then T accepts x with output z such that R(x, z) (there may be multiple y, and T need only find one of them) * If x is such that there is no y such that R(x, y) then T rejects x Intuitively, the problem consists in finding structure "y" in object "x". An algorithm is said to solve the problem if at least one corresponding structure exists, and then one occurrence of this structure is made output; otherwise, the algorithm stops with an appropriate output ("Item not found" or any message of the like). Such problems occur very frequently in graph theory, for example, where searching graphs for structures such as particular matching, cliques, independent set, etc. are subjects of interest. Note that the graph of a partial function is a binary relation, and if T calculates a partial function then there is at most one possible output. A relation R can be viewed as a search problem, and a Turing machine which calculates R is also said to solve it. Every search problem has a corresponding decision problem, namely This definition may be generalized to n-ary relations using any suitable encoding which allows multiple strings to be compressed into one string (for instance by listing them consecutively with a delimiter). (en) 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. (fr) Em teoria da complexidade computacional e teoria da computabilidade, o problema de busca é um tipo de problema computacional representado por uma relação binária. Se R é uma relação binária tal que o dominio (R) ⊆ Γ+ e T é um máquina de Turing, então T calcula R se: * Se x é tal que existe algum y tal que R(x, y) então T aceita x com saída z tal que R(x, z) (pode haver vários y, e T só precisa encontrar um deles ) * Se x é tal que não existe y tal que R(x, y) então T rejeita x Intuitivamente, o problema consiste em encontrar uma estrutura y em um objeto x. Um algoritmo é dito para resolver o problema se ele se comporta da seguinte forma: se pelo menos uma estrutura correspondente existe, então uma ocorrência desta estrutura é emitida, caso contrário, o algoritmo pára com uma saída apropriada ("Item não encontrado" ou qualquer outra mensagem do gênero). Por exemplo, esses problemas ocorrem muito frequentemente em teoria dos grafos, onde busca grafos para estruturas como em particular acoplamento, clique, conjunto independente, etc. são assuntos de interesse. Observe que o grafo de uma função parcial é uma relação binária, e se T calcula uma função parcial, então há, no máximo, uma saída possível. Uma relação R pode ser vista como um problema de busca, e uma máquina de Turing que calcula R também pode resolvê-lo. Todo problema de busca tem um correspondente problema de decisão Esta definição pode ser generalizada para relações N-ária usando qualquer codificação adequada que permite que várias sequências sejam comprimidas em uma cadeia de caracteres (por exemplo, listando-os consecutivamente com um delimitador). (pt) |
| dbo:wikiPageID | 1471816 (xsd:integer) |
| dbo:wikiPageLength | 3719 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1072668837 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Binary_relation dbr:Algorithm dbr:Decision_problem dbr:Independent_set_(graph_theory) dbr:Computability_theory dbr:Matching_(graph_theory) dbr:Clique_(graph_theory) dbr:Computational_complexity_theory dbr:Computational_problem dbr:Function_problem dbr:State_(computer_science) dbr:Successor_function dbr:Graph_theory dbr:Counting_problem_(complexity) dbc:Computational_problems dbr:Optimization_problem dbr:Turing_machine dbr:Search_games dbr:Start_state dbr:Unbounded_search_operator dbr:Goal_state |
| dbp:id | 3425 (xsd:integer) |
| dbp:title | search problem (en) |
| dbp:wikiPageUsesTemplate | dbt:Confusing dbt:Multiple_issues dbt:One_source dbt:Refimprove dbt:Reflist dbt:PlanetMath_attribution |
| dcterms:subject | dbc:Computational_problems |
| rdf:type | yago:WikicatComputationalProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 |
| rdfs:comment | Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα αναζήτησης είναι ένα είδος υπολογιστικού προβλήματος που αναπαριστάται από μια . Αν το R είναι μια δυαδική σχέση τέτοια ώστε field(R) ⊆ Γ+ και το T είναι μια μηχανή Turing, τότε το T υπολογίζει το R εάν: * Έστω ότι το x είναι τέτοιο ώστε να υπάρχει κάποιο y όπου R(x,y). Τότε το Τ αποδέχεται x με έξοδο z τέτοια ώστε R(x,z) (μπορεί να υπάρχουν πολλαπλά y, αλλά το Τ χρειάζεται να βρει μόνο ένα από αυτά) * Έστω ότι το x είναι τέτοιο ώστε δεν υπάρχει κανένα y όπου R(x,y). Τότε το Τ απορρίπτει το x (el) Als Suchproblem bezeichnet man in der theoretischen Informatik ein Problem, bei dem zu einer gegebenen Eingabe eine bestmögliche Lösung gesucht ist. Das Suchproblem unterscheidet sich vom zugehörigen Optimierungsproblem darin, dass beim Optimierungsproblem nicht die Lösung selbst, sondern der ihr zugeordnete Zahlenwert gesucht ist. (de) 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 (fr) In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If R is a binary relation such that field(R) ⊆ Γ+ and T is a Turing machine, then T calculates R if: * If x is such that there is some y such that R(x, y) then T accepts x with output z such that R(x, z) (there may be multiple y, and T need only find one of them) * If x is such that there is no y such that R(x, y) then T rejects x (en) Em teoria da complexidade computacional e teoria da computabilidade, o problema de busca é um tipo de problema computacional representado por uma relação binária. Se R é uma relação binária tal que o dominio (R) ⊆ Γ+ e T é um máquina de Turing, então T calcula R se: * Se x é tal que existe algum y tal que R(x, y) então T aceita x com saída z tal que R(x, z) (pode haver vários y, e T só precisa encontrar um deles ) * Se x é tal que não existe y tal que R(x, y) então T rejeita x (pt) |
| rdfs:label | Suchproblem (de) Πρόβλημα αναζήτησης (el) Problème de recherche (fr) Search problem (en) Problema de busca (pt) |
| owl:sameAs | freebase:Search problem yago-res:Search problem wikidata:Search problem dbpedia-de:Search problem dbpedia-el:Search problem dbpedia-fr:Search problem dbpedia-pt:Search problem https://global.dbpedia.org/id/2E29p |
| prov:wasDerivedFrom | wikipedia-en:Search_problem?oldid=1072668837&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Search_problem |
| is dbo:wikiPageWikiLink of | dbr:NP_(complexity) dbr:Decision_problem dbr:Computability dbr:Generic-case_complexity dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Cook–Levin_theorem dbr:Crossword dbr:Computational_problem dbr:Computer-automated_design dbr:Function_problem dbr:Las_Vegas_algorithm dbr:Promise_problem dbr:Bridge_and_torch_problem dbr:Counting_problem_(complexity) dbr:Blocks_world dbr:Heuristic_(computer_science) dbr:Hidden_linear_function_problem dbr:Boolean_satisfiability_problem dbr:Search_algorithm dbr:Maximum_inner-product_search dbr:NP-hardness |
| is foaf:primaryTopic of | wikipedia-en:Search_problem |