モンテカルロ法と確率的チューリング機械間の類似点
モンテカルロ法と確率的チューリング機械は(ユニオンペディアに)共通で7ものを持っています: 乱択アルゴリズム、BPP (計算複雑性理論)、確率論、複雑性クラス、計算複雑性理論、NP、RP (計算複雑性理論)。
乱択アルゴリズム
乱択アルゴリズム(らんたくアルゴリズム、Randomized algorithm、ランダム・アルゴリズム)または確率的アルゴリズム(かくりつてき-、Probabilistic algorithm)は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。.
モンテカルロ法と乱択アルゴリズム · 乱択アルゴリズムと確率的チューリング機械 ·
BPP (計算複雑性理論)
計算複雑性理論において、BPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。 ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。 これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。 この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。.
BPP (計算複雑性理論)とモンテカルロ法 · BPP (計算複雑性理論)と確率的チューリング機械 ·
確率論
率論(かくりつろん、,, )とは、偶然現象に対して数学的な模型(モデル)を与え、解析する数学の一分野である。 もともとサイコロ賭博といった賭博の研究として始まった。現在でも保険や投資などの分野で基礎論として使われる。 なお、確率の計算を問題とする分野を指して「確率論」と呼ぶ用例もあるが、本稿では取り扱わない。.
モンテカルロ法と確率論 · 確率的チューリング機械と確率論 ·
複雑性クラス
複雑性クラス(ふくざつせいクラス、Complexity class)は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である(例えば'''FP''')。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される(記述計算量)。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.
モンテカルロ法と複雑性クラス · 確率的チューリング機械と複雑性クラス ·
計算複雑性理論
計算複雑性理論(けいさんふくざつせいりろん、computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
モンテカルロ法と計算複雑性理論 · 確率的チューリング機械と計算複雑性理論 ·
NP
NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time(非決定性多項式時間)の略である(「Non-P」ないしは「Not-P」ではない)。.
RP (計算複雑性理論)
計算複雑性理論におけるRP(randomized polynomial time)とは、以下の3つの属性を持つ確率的チューリング機械で解ける問題の複雑性クラスである。.
上記のリストは以下の質問に答えます
- 何モンテカルロ法と確率的チューリング機械ことは共通しています
- 何がモンテカルロ法と確率的チューリング機械間の類似点があります
モンテカルロ法と確率的チューリング機械の間の比較
確率的チューリング機械が15を有しているモンテカルロ法は、50の関係を有しています。 彼らは一般的な7で持っているように、ジャカード指数は10.77%です = 7 / (50 + 15)。
参考文献
この記事では、モンテカルロ法と確率的チューリング機械との関係を示しています。情報が抽出された各記事にアクセスするには、次のURLをご覧ください: