| rdfs:comment
| - 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. (fr)
- 決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合、あるいはの部分集合からへの写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。 (ja)
- 계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다. 일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합의 유한한 부분집합이기 때문에, 모든 문제는 결정 문제로 환원될 수 있다. 판정 문제를 푸는 데 쓰인 방법을 알고리즘이라고 한다. 어떤 판정 문제를 푸는 알고리즘이 있으면 그 문제는 결정 가능하다고 한다. 없으면 결정 불가능하다고 한다. (ko)
- In de berekenbaarheids- en complexiteitstheorie is een beslissingsprobleem een computationeel probleem dat, afhankelijk van de gegeven invoer, met 'ja' of 'nee' beantwoord dient te worden. Het probleem "is het getal een priemgetal?" is bijvoorbeeld een beslissingsprobleem. Een beslissingsprobleem wordt beslisbaar genoemd als er een algoritme bestaat dat het voor elke invoer oplost. (nl)
- 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. (sv)
- 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. (ca)
- 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 nerozhodnutelné. (cs)
- Στη θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, ένα πρόβλημα απόφασης είναι ένα ερώτημα σε κάποιο τυπικό σύστημα που επιδέχεται μιας ναι ή όχι απάντησης, ανάλογα με τις τιμές κάποιων παραμέτρων εισόδου. Τα προβλήματα απόφασης εμφανίζονται συνήθως σε μαθηματικά ερωτήματα (αποφασισιμότητας), δηλαδή ερωτήματα σχετικά με την ύπαρξη ή μη κάποιας συστηματικής μεθόδου για να προσδιοριστεί αν κάποιο αντικείμενο υπάρχει ή αν ανήκει σε κάποιο σύνολο· κάποια από τα πιο σημαντικά προβλήματα των μαθηματικών είναι (μη αποφασίσιμα). (el)
- 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 . (eo)
- In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm 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', (en)
- En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas posibles son «sí» o «no». (es)
- 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. (it)
- 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. (pl)
- 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. (pt)
- Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров. Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление произведения двух чисел, поиск наиболее быстрого алгоритма умножения чисел и оптимизационные задачи, в частности задача коммивояжёра в классической постановке, не являются проблемами разрешимости, поскольку их невозможно сформулировать так, чтобы ответом к задаче было бы «да» или «нет». (ru)
- У теорії обчислюваності і теорії складності обчислень, проблема вибору або задача про ухвалення рішень — це запитання в деякій формальній системі з відповіддю так або ні, залежно від значення деяких вхідних параметрів. Рішення проблеми зазвичай з'являються в математичних питаннях алгоритмічного розв'язання, тобто в питаннях про існування ефективного методу для визначення наявності будь-якого об'єкта або його належність множині. Деякі з важливих математичних проблем нерозв'язні. (uk)
- 在可計算性理論與計算複雜性理論中，決定性問題，亦稱判定問題，（英語：Decision problem）是一個在某些形式系統回答「是」或「否」的問題。 舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與 y 的值可回答是或否。以演算法形式給出的解決決定性問題的方法稱為決策程式（decision procedure）。對決定性問題「給兩個數字 x 與 y，x 是否可以整除 y？」決策程式將確定 x 是否整除 y。一種這樣的演算法是長除法，如果餘數為 0，則原決定性問題的答案為「是」，否則為「否」。若某決定性問題可以被一些演算法所解決，則稱此問題可決定（decidable）。 決定性問題與功能性問題（Function problem，或）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除 x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 計算複雜度的領域中，分類可決定問題的依據在於「此問題有多難被解決」。在此標準下，所謂的「難」是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 (zh)
|
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)