About: Search problem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatComputationalProblems, within Data Space : dbpedia.org associated with source document(s)

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

AttributesValues
rdf:type
rdfs:label
  • Suchproblem
  • Πρόβλημα αναζήτησης
  • Search problem
  • Problème de recherche
  • Problema de busca
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
  • 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
  • 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
  • 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
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
id
title
  • search problem
has abstract
  • Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα αναζήτησης είναι ένα είδος υπολογιστικού προβλήματος που αναπαριστάται από μια . Αν το 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-μερείς σχέσεις με τη χρήση οποιασδήποτε κατάλληλης κωδικοποίησης η οποία να επιτρέπει πολλαπλές συμβολοσειρές να συμπιεστούν σε μία (για παράδειγμα απαριθμώντας τες διαδοχικά με κάποιο διαχωριστικό).
  • 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.
  • 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).
  • 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).
prov:wasDerivedFrom
page length (characters) of wiki page
is foaf:primaryTopic of
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git81 as of Jul 16 2021


Alternative Linked Data Documents: PivotViewer | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3322 as of Sep 15 2021, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software