Decision problem
Problème de la décision
En
logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un
algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction (voir
système à la Hilbert,
calcul des séquents,
déduction naturelle), sans autres axiomes que ceux de l'égalité. De façon équivalente par le
théorème de complétude, il s'agit de savoir si un énoncé est universellement valide, c’est-à-dire vrai dans tous les modèles (de l'égalité). Il s'agit de
décidabilité algorithmique. Dit autrement, la question est celle de la
décidabilité du calcul des prédicats égalitaire du premier ordre : l'ensemble des énoncés universellement valides du calcul des prédicats du premier ordre est-il décidable ?
Pour la suite, voir Wikipédia.org…
Entscheidungsproblem
Entscheidbar ist eine Eigenschaft dann, wenn es ein Entscheidungsverfahren gibt, für jedes Objekt festzustellen, ob es diese Eigenschaft hat oder nicht. Als Entscheidungsproblem bezeichnet man die Frage, ob und wie für eine gegebene Eigenschaft ein Entscheidungsverfahren formuliert werden kann.
Mehr unter Wikipedia.org...
Problem decyzyjny (teoria obliczen)
W
teorii obliczeń problem decyzyjny to pytanie sformułowane w
systemie formalnym na które możliwe są 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ę problemy funkcyjne – na które wymagane są bardziej złożone odpowiedzi, oraz
problemy optymalizacyjne – polegające na znalezieniu najlepszej odpowiedzi.
Teoria złożoności obliczeniowej kategoryzuje problemy decyzyjne w zależności od tego jak trudno je rozwiązać, w terminach zasobów wymaganych przez najefektywniejsze algorytmy.
Teoria rekursji definiuje również hierarchię dla problemów których nie da się algorytmicznie rozwiązać, określając stopień ich "nierozwiązywalności" jako stopień Turinga.
W celu uzyskania więcej informacji, zobacz w Wikipedia.οrg...
© W niniejszym artykule wykorzystano materialy pochodzace z
Wikipedia® i posiada on Powszechna
Licencje Publiczna GNU
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合からへの写像、あるいはの部分集合である。たとえば、ある
命題論理式を充足する真理値割り当てがあるかないか（
充足可能性問題）、与えられた
自然数が
素数か否か（
素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや
素因数分解の結果といったものの出力を要求する問題は
函数問題（function problem）と呼ばれる。決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、
計算理論でよく使われる。
Wikipedia.orgをもっと見ると…
Free Download Now!
