About: Decision problem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatComputationalProblems, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FDecision_problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision proble

AttributesValues
rdf:type
rdfs:label
  • Problema de decisió
  • Rozhodovací problém
  • Πρόβλημα απόφασης
  • Decidoproblemo
  • Entscheidungsproblem
  • Problema de decisión
  • Problème de décision
  • Decision problem
  • Problema decisionale
  • 決定問題
  • 결정 문제
  • Beslissingsprobleem
  • Problem decyzyjny (teoria obliczeń)
  • Problema de decisão
  • Задача разрешимости
  • Beslutsproblem
  • Проблема вибору
  • 決定性問題
rdfs:comment
  • 계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다. 일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합의 유한한 부분집합이기 때문에, 모든 문제는 결정 문제로 환원될 수 있다. 판정 문제를 푸는 데 쓰인 방법을 알고리즘이라고 한다. 어떤 판정 문제를 푸는 알고리즘이 있으면 그 문제는 결정 가능하다고 한다. 없으면 결정 불가능하다고 한다.
  • 決定問題(けっていもんだい、decision problem)とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合、あるいはの部分集合からへの写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか(充足可能性問題)、与えられた自然数が素数か否か(素数判定問題)、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題(function problem)と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。
  • 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.
  • Inom datavetenskapen, och särskilt komplexitetsteori är ett beslutsproblem ett som ska besvaras med ja eller nej. Ett exempel på ett beslutsproblem är: kan man rita den här figuren utan att lyfta pennan? Detta problem kallas i matematiken för att hitta en Eulerstig. Märk att själva lösningen i ett beslutsproblem, i exemplet hur man ritar figuren, inte är intressant. Avsikten är att förenkla och formalisera beräkningsproblem så att man kan resonera om dem på ett matematiskt sätt. Har man väl en algoritm som löser ett beslutsproblem brukar det inte vara svårt att anpassa den till att plocka fram lösningen.
  • En teoria de la computabilitat i en complexitat computacional, un problema de decisió és una qüestió en algun sistema formal amb una resposta sí o no. Problemes amb respostes més complexes es coneixen com a . Per exemple, es pot tenir un problema de decisió «donats dos nombres x i y, x és divisor enter de y?». Aquesta és una pregunta de resposta sí o no, i la seva resposta depèn dels valors de x i de y. Un algorisme per aquest problema de decisió hauria de contestar com, donats x i y, es pot determinar si x és divisor enter de y.
  • Rozhodovací problém je v informatice, speciálně v teorii složitosti a teorii vyčíslitelnosti, otázka v nějakém systému s odpovědí ANO-NE v závislosti na hodnotě vstupu.Například, problém „pro dvě čísla x a y, dělí x hodnotu y beze zbytku?“ je rozhodovací problém, kde odpověď „ANO“ nebo „NE“ závisí na vstupech. Rozhodovací problémy se typicky a přirozeně objevují v otázkách rozhodnutelnosti, kdy se ptáme, zda existuje pro určení existence nějakých matematických objektů nebo pro jejich příslušnost do nějaké množiny. Některé problémy v matematice jsou .
  • Στη θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, ένα πρόβλημα απόφασης είναι ένα ερώτημα σε κάποιο τυπικό σύστημα που επιδέχεται μιας ναι ή όχι απάντησης, ανάλογα με τις τιμές κάποιων παραμέτρων εισόδου. Τα προβλήματα απόφασης εμφανίζονται συνήθως σε μαθηματικά ερωτήματα (αποφασισιμότητας), δηλαδή ερωτήματα σχετικά με την ύπαρξη ή μη κάποιας συστηματικής μεθόδου για να προσδιοριστεί αν κάποιο αντικείμενο υπάρχει ή αν ανήκει σε κάποιο σύνολο· κάποια από τα πιο σημαντικά προβλήματα των μαθηματικών είναι (μη αποφασίσιμα).
  • En kaj de , decidoproblemo estas demando en iu kun jes-aŭ-ne respondo, depende de la valoroj de kelkaj enigaj parametroj. Decidoproblemoj tipe prezentiĝas en matematikaj demandoj de , t.e., la demando pri la ekzisto de determini la ekziston de iu objekto aŭ ĝian membrecon en aro; kelkaj el la plej gravaj problemoj en matematiko estas .
  • In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision proble
  • Un problema decisionale nell'ambito della matematica riguarda un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili alternative, sulla base di uno o più criteri. Si parla di problemi decisionali soprattutto all'interno del campo della matematica applicata e, più nello specifico, della ricerca operativa.
  • Problem decyzyjny – pytanie sformułowane w systemie formalnym, na które możliwe są tylko odpowiedzi tak i nie. Przykładowo problem „Dla danych liczb x i y, czy x jest dzielnikiem y?” jest problemem decyzyjnym. Odpowiedzią może być tak lub nie w zależności od wartości x i y. Analogicznie do problemów decyzyjnych definiuje się – na które wymagane są bardziej złożone odpowiedzi oraz problemy optymalizacyjne – polegające na znalezieniu najlepszej odpowiedzi.
  • Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não. Por exemplo, o problema: "dados dois números x e y, y é divisível por x?" é um problema de decisão. Ou ainda: "Dado um número inteiro x, x é um número primo?". A resposta para esses problemas pode ser 'sim' ou 'não', e depende dos valores que as variáveis assumem em cada instância do problema. Para a seguinte instância do segundo problema "7 é um número primo?" a resposta é sim, já para a instância "8 é um número primo?" a resposta é não.
  • In de complexiteitstheorie is een beslissingsprobleem een computationeel probleem dat met 'ja' of 'nee' beantwoord dient te worden, afhankelijk van de gegeven invoer. Het probleem "is het getal n een priemgetal?" is een beslissingsprobleem want het antwoord is 'ja' of 'nee' en het antwoord hangt af van de invoer, namelijk het getal n.
  • Задача разрешимости (задача разрешения) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров. Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление произведения двух чисел, поиск наиболее быстрого алгоритма умножения чисел и оптимизационные задачи, в частности задача коммивояжёра в классической постановке, не являются проблемами разрешимости, поскольку их невозможно сформулировать так, чтобы ответом к задаче было бы «да» или «нет».
  • У теорії обчислюваності і теорії складності обчислень, проблема вибору або задача про приймання рішень — це запитання в деякій формальній системі з відповіддю так або ні, залежно від значення деяких вхідних параметрів. Рішення проблеми зазвичай з'являються в математичних питаннях алгоритмічного розв'язання, тобто в питаннях про існування ефективного методу для визначення наявності будь-якого об'єкта або його належність множині. Деякі з важливих математичних проблем нерозв'язні.
  • 在可計算性理論與計算複雜性理論中,所謂的決定性問題(亦稱判定問題,Decision problem)是一個在某些形式系統回答是或否的問題。舉例來說,「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是:「給兩個數字 x 與 y,x 是否可以整除 y?」,此問題依據其 x 與 y 的值可回答是或否。以演算法形式給出的解決決定性問題的方法稱為決策程式(decision procedure)。決策程式將對決定性問題「給兩個數字 x 與 y,x 是否可以整除 y?」給出確定 x 是否整除 y 的步驟。一種這樣的演算法是長除法,如果餘數為 0,則原決定性問題的答案為是,否則則為否。若是某決定性問題可以被一些演算法所解決,則稱此問題可決定(decidable)。 決定性問題與功能性問題(Function problem,或)密切相關,功能性問題的答案內容,較簡單的是與非複雜許多。範例問題:「給予一個正整數x,則哪些數可整除 x?」 另一個與上述兩類問題相關的是最佳化問題(Optimization problem),此問題關心的是尋找特定問題的最佳答案。 計算複雜度的領域中,分類可決定問題的依據在於此問題有多難被解決。在此標準下,所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中,非決定性問題由圖靈度決定,指的是一種在任何解答中隱含的不可計算性量詞。
sameAs
foaf:depiction
  • External Image
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Faceted Search & Find service v1.17_git93 as of Oct 15 2021


Alternative Linked Data Documents: iSPARQL | ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3322 as of Oct 25 2021, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory, 39 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software