ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
無料
ブラウザよりも高速アクセス!
 

モンテカルロ法

索引 モンテカルロ法

モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区(カルティ)の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。.

50 関係: 台形公式大数の法則層化抽出法乱択アルゴリズム乱数列二重指数関数型数値積分公式強化学習保険数理ミラー–ラビン素数判定法マルコフ連鎖マルコフ連鎖モンテカルロ法メトロポリス法モナコモンテカルロランダムラスベガス法レプリカ交換法ブートストラップ法ビュフォンの針ダイオードカジノコンピュータ囲碁シミュレーションシンプソンの公式ジョン・フォン・ノイマンスタニスワフ・ウラムBPP (計算複雑性理論)確率的チューリング機械確率論積分法粒子フィルタ素数判定複雑性クラス計算理論計算物理学計算複雑性理論金融工学GNU OctaveNPP (計算複雑性理論)PP (計算複雑性理論)R言語RP (計算複雑性理論)技術評論社機械学習次元の呪い決定的アルゴリズム擬似乱数数値積分数値解析

台形公式

数学において、台形公式(だいけいこうしき、Trapezoidal rule)もしくは台形則(だいけいそく)は定積分を近似計算するための方法、すなわち数値積分のひとつである。これはニュートン・コーツの公式の1次の場合である。被積分関数を区分線形関数で近似し、台形の面積の公式に帰着させて積分の近似値を求める。 具体的に言えば、求めたいx -y グラフのy.

新しい!!: モンテカルロ法と台形公式 · 続きを見る »

大数の法則

大数の法則(たいすうのほうそく、law of large numbers)は、確率論・統計学における極限定理のひとつで、「経験的確率と理論的確率が一致する」 という、素朴な意味での確率を意味付け、定義付ける法則である。 厳密には、ヤコブ・ベルヌーイによる大数の弱法則 と、エミール・ボレルやアンドレイ・コルモゴロフによる大数の強法則 とがある。単に「大数の法則」と言った場合、どちらを指しているのかは文脈により判断する必要がある。.

新しい!!: モンテカルロ法と大数の法則 · 続きを見る »

層化抽出法

層化抽出法(そうかちゅうしゅつほう、stratified sampling)とは、統計学における母集団からの標本調査の手法のひとつ。.

新しい!!: モンテカルロ法と層化抽出法 · 続きを見る »

乱択アルゴリズム

乱択アルゴリズム(らんたくアルゴリズム、Randomized algorithm、ランダム・アルゴリズム)または確率的アルゴリズム(かくりつてき-、Probabilistic algorithm)は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。.

新しい!!: モンテカルロ法と乱択アルゴリズム · 続きを見る »

乱数列

乱数列(らんすうれつ)とはランダムな数列のこと。 数学的に述べれば、今得られている数列 x1, x2,..., xn から次の数列の値 xn+1 が予測できない数列。乱数列の各要素を乱数という。.

新しい!!: モンテカルロ法と乱数列 · 続きを見る »

二重指数関数型数値積分公式

二重指数関数型数値積分公式(にじゅうしすうかんすうがたすうちせきぶんこうしき、double exponential formula, 略してDE公式)とは変数変換に基づく数値積分の公式の一つである。この公式は森正武、高橋秀俊によって提案された。変換後の被積分関数が端点で二重指数関数的に減衰することが特徴である。数値積分の効率性の観点で、この公式がいろいろな点で使いやすく、非常に応用が利くと言われている。また、この公式は変換前の被積分関数が端点で特異性を持つときにも有効である。ただし、被積分関数によって適用できない場合があるので注意が必要である。.

新しい!!: モンテカルロ法と二重指数関数型数値積分公式 · 続きを見る »

強化学習

強化学習(きょうかがくしゅう、Reinforcement learning)とは、ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習の一種。エージェントは行動を選択することで環境から報酬を得る。強化学習は一連の行動を通じて報酬が最も多く得られるような方策()を学習する。代表的な手法としてTD学習やQ学習が知られている。 最も基本的なモデルでは、ここでの環境は、有限状態数のマルコフ決定過程として定式化される。また、強化学習のアルゴリズムは動的計画法に類似したアルゴリズムである。.

新しい!!: モンテカルロ法と強化学習 · 続きを見る »

保険数理

保険数理(ほけんすうり)は保険、金融、その他業種や職種にて数学や統計学を用いたリスクアセスメントを行う分野である。 アクチュアリーは学位や実務経験を通じて認定されたこの分野の専門家である。 多くの国の保険数理人は、厳格な試験の通過が義務付けられている。 確率、数学、統計、金融、経済学、金融経済学、プログラミング (コンピュータ)などの分野が関連している。 多くの大学や大学院に保険数理学部がある。2010年の求人情報検索サイトCareerCastが環境、収入、雇用、業務内容、ストレスの5つを基準とした研究によると、米国ではアクチュアリーが最も優れた職業と評価された。 2006年の米国のNews&World Report誌による同様の研究では、将来の需要が見込まれる専門職25種の一つに含まれている。.

新しい!!: モンテカルロ法と保険数理 · 続きを見る »

ミラー–ラビン素数判定法

ミラー–ラビン素数判定法(Miller–Rabin primality test)またはラビン–ミラー素数判定法(Rabin–Miller primality test)は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンはこれを無条件の確率的アルゴリズムに修正した。.

新しい!!: モンテカルロ法とミラー–ラビン素数判定法 · 続きを見る »

マルコフ連鎖

マルコフ連鎖(マルコフれんさ、Markov chain)とは、確率過程の一種であるマルコフ過程のうち、とりうる状態が離散的(有限または可算)なもの(離散状態マルコフ過程)をいう。また特に、時間が離散的なもの(時刻は添え字で表される)を指すことが多い(他に連続時間マルコフ過程というものもあり、これは時刻が連続である)。マルコフ連鎖は、未来の挙動が現在の値だけで決定され、過去の挙動と無関係である(マルコフ性)。各時刻において起こる状態変化(遷移または推移)に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である。特に重要な確率過程として、様々な分野に応用される。.

新しい!!: モンテカルロ法とマルコフ連鎖 · 続きを見る »

マルコフ連鎖モンテカルロ法

マルコフ連鎖モンテカルロ法(マルコフれんさモンテカルロほう、Markov chain Monte Carlo methods、MCMC)とは、求める確率分布を均衡分布として持つマルコフ連鎖を作成することをもとに、確率分布のサンプリングを行うアルゴリズムの総称である。M-H アルゴリズムやギブスサンプリングなどのランダムウォーク法もこれに含まれる。充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標本として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。 求められる特性を持つマルコフ連鎖を作成することは通常難しくない。問題は許容できる誤差内で定常分布に収束する試行の回数を決めることである。適切な連鎖なら任意の位置から始めても定常分布に速く達し、これを高速混合(rapid mixing)とよぶ。 典型的なMCMCは常にある程度の初期値の影響が残るため目標分布しか近似することができない。CFTP法()など、より洗練されたMCMCベースのアルゴリズムは完全標本を作成することができるが、より多くの計算と(期待値では有限だが)限界のない実行時間を要する。 このアルゴリズムの最も一般的な応用は多重積分を数値的に計算することである。ランダムに歩き回る粒子の集団を想定し、粒子が点を通過するたびに、その点の被積分関数の値を積分に加算する。粒子は次に積分への貢献が高い所を探して複数の仮の動作をする。このような方法はランダムウォーク法とよばれ、これは乱数的なシミュレーションつまりモンテカルロ法の一種である。従来のモンテカルロ法で用いられる被積分関数のランダムな標本が独立であるのに対して、MCMCで用いられる標本は相関がある。被積分関数を均衡分布に持つようなマルコフ連鎖を作成する必要があるが、多くの場合において容易に行うことができる。 多重積分はベイズ統計学、計算物理学、計算生物学などにしばしば現れるため、そのような分野でMCMC法も広く使われている。例としては や を参照のこと。.

新しい!!: モンテカルロ法とマルコフ連鎖モンテカルロ法 · 続きを見る »

メトロポリス法

メトロポリス法(Metropolis method )は、モンテカルロ法によるシミュレーションにおいて、乱数発生により作った新しい状態を棄却するか採択するかの基準の与え方、あるいは重点サンプリング による分配関数の近似計算の方法。具体的には、系のエネルギー の変化 よって、 ならば確率 1 で、 ならば確率 で採択する。ここで は逆温度であり を満たす。 はボルツマン定数、は系の熱力学温度である。 一般に、詳細釣り合いの原理、非周期性 がある棄却採択法ならば、熱平衡状態のアンサンブルが得られる。.

新しい!!: モンテカルロ法とメトロポリス法 · 続きを見る »

モナコ

モナコ公国(モナコこうこく、プランシポテ・ドゥ・モナコ、仏:)、通称モナコ()は、西ヨーロッパの立憲君主制国家。.

新しい!!: モンテカルロ法とモナコ · 続きを見る »

モンテカルロ

モンテカルロ(フランス語:Monte Carlo、オック語:Montcarles、モナコ語:Monte-Carlu)は、モナコの4つの地区(カルティエ)の1つであり、同国の北東部、モナコ湾の北岸に位置する。モンテカルロ地区は行政上、同名の「モンテカルロ区」を含む4つの区にさらに分けられている。 モンテカルロとはイタリア語で「シャルル3世の山」という意味であり、彼の治世下で名づけられた。.

新しい!!: モンテカルロ法とモンテカルロ · 続きを見る »

ランダム

ランダム(random)とは、事象の発生に法則性(規則性)がなく、な状態である。ランダムネス(randomness)、無作為性(むさくいせい)ともいう。 事象・記号などのランダムな列には秩序がなく、理解可能なパターンや組み合わせに従わない。個々のランダムな事象は定義上予測不可能であるが、多くの場合、何度も試行した場合の結果の頻度は予測可能である。例えば、2つのサイコロを投げるとき、1回ごとの出目は予測できないが、合計が7になる頻度は4になる頻度の2倍になる。この見方では、ランダム性とは結果の不確実性の尺度であり、確率・情報エントロピーの概念に適用される。 数学、確率、統計の分野では、ランダム性の正式な定義が使用される。統計では、事象空間の起こり得る結果に数値を割り当てたものを確率変数(random variable)という。この関連付けは、事象の確率の識別および計算を容易にする。確率変数の列を(random sequence)という。ランダム過程(不規則過程、確率過程)は、結果が決定論的パターンに従わず、確率分布によって記述される進化に従う確率変数の列である。これらの構造と他の構造は、確率論や様々なランダム性の応用に非常に有用である。 ランダム性は、よく定義された統計的特性を示すために統計で最も頻繁に使用される。ランダムな入力(や擬似乱数発生器など)に依存するモンテカルロ法は、計算科学などの科学において重要な技術である。これに対し、では乱数列ではなく一様分布列を使用している。 無作為抽出(random selection)は、ある項目を選択する確率が母集団内におけるその項目の割合と一致している集団から項目を選択する方法である。例えば、赤い石10個と青い石90個を入れた袋に入れた場合、この袋から何らかのランダム選択メカニズムによって石を1個選択した時にそれが赤い石である確率は1/10である。しかし、ランダム選択メカニズムによって実際に10個の石を選択したときに、それが赤1個・青9個であるとは限らない。母集団が識別可能な項目で構成されている状況では、ランダム選択メカニズムは、選択される項目に等しい確率を必要とする。つまり、選択プロセスが、母集団の各メンバー(例えば、研究対象)が選択される確率が同じである場合、選択プロセスはランダムであると言うことができる。.

新しい!!: モンテカルロ法とランダム · 続きを見る »

ラスベガス法

ラスベガス法(Las Vegas algorithm)は、間違った解を返さない乱択アルゴリズムを指す。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、ラスベガス法は答え(解)については賭けをせず、計算に使用するリソース量についてのみ賭けをする。さらに平均実行時間が入力長の多項式関数で押さられるようなラスベガス法は(efficient)であるという。ラスベガス法の単純な例にランダム化されたクイックソートがある。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。.

新しい!!: モンテカルロ法とラスベガス法 · 続きを見る »

レプリカ交換法

レプリカ交換法(レプリカこうかんほう、replica exchange method、レプリカ交換MCMCサンプリング)はパラレルテンパリング(、並列焼きもどし)法としても知られ、モンテカルロシミュレーションやマルコフ連鎖モンテカルロ法(MCMC)のサンプリング効率を改善するための方法である。SwendsenとWangによって開発され、Geyerによって拡張され、その後、特に、福島・根本およびによって発展した。杉田と岡本はパラレルテンパリングの分子動力学法版を考案した。これはレプリカ交換分子動力学(、REMD)として知られている。 手法としては、始めに異なる温度でランダムに初期化された 個の系のコピーを走らせ、メトロポリス法の基準でそれぞれ温度間で系の状態を交換するものである。 この方法の重要な点は、低温のシミュレーションで高温の設定が(またはその逆も)できることである。低エネルギー配置と高エネルギー配置の両方をサンプリングできるため、とても安定にかつ正確なシミュレーションを行うことができる。このようにして、正準集団では一般にうまく計算されない比熱といった熱力学特性がかなり正確に計算できる。.

新しい!!: モンテカルロ法とレプリカ交換法 · 続きを見る »

ブートストラップ法

統計学におけるブートストラップ法(ブートストラップほう、bootstrap method)とは、様々な目的に用いられる統計的推論の手法であり、再標本化法に分類されるもののひとつである。モンテカルロ法の一つ。.

新しい!!: モンテカルロ法とブートストラップ法 · 続きを見る »

ビュフォンの針

ビュフォンの針(ビュフォンのはり、Buffon's needle problem)は18世紀の博物学者ジョルジュ=ルイ・ルクレール、コント・ド・ビュフォンが提起した数学上の問題である。 もし床に多数の平行線を引き、そこに針を落すならば、どれかの線と針が交差する確率はどのようになるかという問題である。 積分と幾何学を使ってこの問題は解け、またこの方法を使って、モンテカルロ法で円周率の近似値を求められる。.

新しい!!: モンテカルロ法とビュフォンの針 · 続きを見る »

ダイオード

図1:ダイオードの拡大図正方形を形成しているのが半導体の結晶を示す 図2:様々な半導体ダイオード。下部:ブリッジダイオード 図3:真空管ダイオードの構造 図4 ダイオード(英: diode)は整流作用(電流を一定方向にしか流さない作用)を持つ電子素子である。最初のダイオードは2極真空管で、後に半導体素子である半導体ダイオードが開発された。今日では単にダイオードと言えば、通常、半導体ダイオードを指す。 1919年、イギリスの物理学者 William Henry Eccles がギリシア語の di.

新しい!!: モンテカルロ法とダイオード · 続きを見る »

カジノ

ノでスロットマシンに興じる人々 カジノ(casino)は、賭博を行う施設の一つ。ルーレットやブラックジャックなどのゲームで金銭を賭ける場所。日本で言う賭場「賭場」は厳密には丁半を行なう場なので完全に同一かは微妙でもある。。.

新しい!!: モンテカルロ法とカジノ · 続きを見る »

コンピュータ囲碁

ンピュータ囲碁(コンピュータいご)とは、人工知能研究の一分野で、ボードゲームの囲碁を打てるコンピュータプログラムを作ることを目的とした試みのことを指す。.

新しい!!: モンテカルロ法とコンピュータ囲碁 · 続きを見る »

シミュレーション

ミュレーション()は、何らかのシステムの挙動を、それとほぼ同じ法則に支配される他のシステムやコンピュータなどによって模擬すること広辞苑第6版。simulationには「模擬実験」や「模擬訓練」という意味もある。なお「シミュレイション」と表記することもまれにある。.

新しい!!: モンテカルロ法とシミュレーション · 続きを見る »

シンプソンの公式

ンプソンの公式(シンプソンのこうしき、Simpson's rule) とは、数値解析の分野において、次の積分の近似値を得る方法である。 「シンプソンの公式」という名前は、トーマス・シンプソンにちなんだものである。.

新しい!!: モンテカルロ法とシンプソンの公式 · 続きを見る »

ジョン・フォン・ノイマン

ョン・フォン・ノイマン(ハンガリー名:Neumann János(ナイマン・ヤーノシュ、)、ドイツ名:ヨハネス・ルートヴィヒ・フォン・ノイマン、John von Neumann, Margittai Neumann János Lajos, Johannes Ludwig von Neumann, 1903年12月28日 - 1957年2月8日)はハンガリー出身のアメリカ合衆国の数学者。20世紀科学史における最重要人物の一人。数学・物理学・工学・計算機科学・経済学・気象学・心理学・政治学に影響を与えた。第二次世界大戦中の原子爆弾開発や、その後の核政策への関与でも知られる。.

新しい!!: モンテカルロ法とジョン・フォン・ノイマン · 続きを見る »

スタニスワフ・ウラム

タニスワフ・マルチン・ウラム(Stanisław Marcin Ulam, 1909年4月3日 - 1984年5月13日)は、アメリカ合衆国の数学者。ポーランド出身。数学の多くの分野に貢献しており、また水爆の機構の発案者としてその名を残している。.

新しい!!: モンテカルロ法とスタニスワフ・ウラム · 続きを見る »

BPP (計算複雑性理論)

計算複雑性理論において、BPPとは、確率的チューリングマシンによって、誤り確率が高々1/3で多項式時間で解ける決定問題の複雑性クラスである。Bounded-error Probabilistic Polynomial timeの頭文字をとったものである。 ある問題がBPPに属するなら、コイントスなどによるランダムな決定を許す多項式時間で実行可能なアルゴリズムが存在する。そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。 定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。 これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。 この性質は複数回アルゴリズムを実行し、解の多数決をとることにより、高い精度のアルゴリズムを作る事を可能にする。.

新しい!!: モンテカルロ法とBPP (計算複雑性理論) · 続きを見る »

確率的チューリング機械

率的チューリング機械(かくりつてきチューリングきかい、Probabilistic Turing machine)は、計算可能性理論において、各時点で何らかの確率分布に従って状態遷移をランダムに選択する非決定性チューリング機械の一種である。 各遷移の確率がいずれも等しければ、決定性チューリング機械にその文字セット(一般に '1' と '0')についてそれぞれの文字を等確率で書く "write" 命令を持たせたものと定義できる。また、決定性チューリング機械に追加のテープとしてランダムなビット列が延々と書かれているものを追加したものと考えることもできる。 結果として、確率的チューリング機械は確率論的な結果を生み出す。同じ入力と命令状態であっても、実行するたびに結果が変わり、場合によっては停止しないこともある。つまり、確率的チューリング機械は、同じ入力であっても実行する毎にその入力を受理したりしなかったりする。 従って、確率的チューリング機械での文字列の受理/不受理は、通常とは異なった形で定義される。この定義の違いによって、様々な多項式時間の確率的な複雑性クラスが生じる。例えば、'''RP'''、Co-RP、'''BPP'''、ZPP などである。制約を多項式時間ではなく対数領域とした場合は、LP、Co-RL、BPL、ZPL がある。また、両方を制約を課した場合は、RLP、Co-RPL、BPLP、ZPLP がある。 確率的計算は対話型証明系の多くのクラスの定義においても重要である。この場合、検査機構(verifier)は全能の証明機構(prover)にだまされないためにランダム性を必要とする。例えば、IPクラスは PSPACE に等しいが、検査機構でのランダム性を排除すると NP と等しくなってしまう。PSPACE と NP の関係は正確には未だ確定していないが、おそらく NP の方が小さいと考えられている。 計算複雑性理論の課題の1つとして、「ランダム性は計算能力を向上させるか?」という問題がある。つまり、確率的チューリング機械で多項式時間で解ける問題があるとき、それが決定性チューリング機械では多項式時間で解けないと言えるだろうか? それとも、決定性チューリング機械で確率的チューリング機械をシミュレートして、高々多項式程度の低速化で問題を解けるだろうか? 現在、多くの研究者は後者(P.

新しい!!: モンテカルロ法と確率的チューリング機械 · 続きを見る »

確率論

率論(かくりつろん、,, )とは、偶然現象に対して数学的な模型(モデル)を与え、解析する数学の一分野である。 もともとサイコロ賭博といった賭博の研究として始まった。現在でも保険や投資などの分野で基礎論として使われる。 なお、確率の計算を問題とする分野を指して「確率論」と呼ぶ用例もあるが、本稿では取り扱わない。.

新しい!!: モンテカルロ法と確率論 · 続きを見る »

積分法

積分法(せきぶんほう、integral calculus)は、微分法と共に微分積分学で対を成す主要な分野である。 実数直線上の区間 [a, b] 上で定義される実変数 x の関数 f の定積分 (独: bestimmte Integral, 英: definite integral, 仏: intégrale définie) は、略式的に言えば f のグラフと x-軸、および x.

新しい!!: モンテカルロ法と積分法 · 続きを見る »

粒子フィルタ

粒子フィルタ(Particle filter)、または逐次モンテカルロ法 (Sequential Monte Carlo: SMC)とは、シミュレーションに基づく複雑なモデルの推定法である。 この手法はふつうベイズモデルを推定するのに用いられ、バッチ処理であるマルコフ連鎖モンテカルロ法 (MCMC) の逐次 (オンライン) 版である。またこの手法は重点サンプリング法にも似たところがある。 うまく設計すると、粒子フィルタはMCMCよりも高速である。拡張カルマンフィルタや無香カルマンフィルタ (Unscented カルマンフィルタ) に対して、十分なサンプル点があればベイズ最適推定に近付くためにより精度が高くなることから、これらの代わりに用いられることがある。手法を組み合わせ、カルマンフィルタを粒子フィルタの提案分布として使うこともできる。.

新しい!!: モンテカルロ法と粒子フィルタ · 続きを見る »

素数判定

素数判定(そすうはんてい)とは、ある自然数 n が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された(AKS素数判定法)。しかし多項式の次数が高く、実用上はなどのほうが高速であることが多い。 なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。.

新しい!!: モンテカルロ法と素数判定 · 続きを見る »

複雑性クラス

複雑性クラス(ふくざつせいクラス、Complexity class)は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である(例えば'''FP''')。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される(記述計算量)。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.

新しい!!: モンテカルロ法と複雑性クラス · 続きを見る »

計算理論

計算理論(けいさんりろん、theory of computation)は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.

新しい!!: モンテカルロ法と計算理論 · 続きを見る »

計算物理学

計算物理学(けいさんぶつりがく、computational physics)は、解析的に解けない物理現象の基礎方程式を計算機(コンピュータ)を用いて数値的に解くことを目的とする物理学の一分野である。.

新しい!!: モンテカルロ法と計算物理学 · 続きを見る »

計算複雑性理論

計算複雑性理論(けいさんふくざつせいりろん、computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.

新しい!!: モンテカルロ法と計算複雑性理論 · 続きを見る »

金融工学

金融工学(きんゆうこうがく、英語:financial engineering、computational finance)は、資産運用や取引、リスクヘッジ、リスクマネジメント、投資に関する意思決定などに関わる工学的研究全般を指す。.

新しい!!: モンテカルロ法と金融工学 · 続きを見る »

GNU Octave

GNU Octave は、主に数値解析を目的とした高レベルプログラミング言語である。Octaveは線形ならびに非線形問題を数値的に解くためのコマンドライン·インタフェースを提供する。また、 MATLABとほぼ互換性のある、数値実験を行うためのプログラミング言語として使用することができる。 Octaveは、GNUプロジェクトの一つでGNU General Public Licenseの条件の下のフリーソフトウェアである。 GNU OctaveとScilabは、MATLABのオープンソース代替品の一つである。 ただし、Octaveは、ScilabよりもMATLABとの互換性維持に重点を置いている 。.

新しい!!: モンテカルロ法とGNU Octave · 続きを見る »

NP

NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time(非決定性多項式時間)の略である(「Non-P」ないしは「Not-P」ではない)。.

新しい!!: モンテカルロ法とNP · 続きを見る »

P (計算複雑性理論)

計算量理論におけるPとは多項式時間(polynomial time)で解ける判定問題の集合である。.

新しい!!: モンテカルロ法とP (計算複雑性理論) · 続きを見る »

PP (計算複雑性理論)

計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は "probabilistic polynomial time" を意味する。1977年、Gill が定義した。.

新しい!!: モンテカルロ法とPP (計算複雑性理論) · 続きを見る »

R言語

R言語(あーるげんご)はオープンソース・フリーソフトウェアの統計解析向けのプログラミング言語及びその開発実行環境である。 R言語はニュージーランドのオークランド大学のRoss IhakaとRobert Clifford Gentlemanにより作られた。現在ではR Development Core Team によりメンテナンスと拡張がなされている。 R言語のソースコードは主にC言語、FORTRAN、そしてRによって開発された。 なお、R言語の仕様を実装した処理系の呼称名はプロジェクトを支援するフリーソフトウェア財団によれば『GNU R』である が、他の実装形態が存在しないために日本語での慣用的呼称に倣って、当記事では、仕様・実装を纏めて適宜にR言語や単にR等と呼ぶ。.

新しい!!: モンテカルロ法とR言語 · 続きを見る »

RP (計算複雑性理論)

計算複雑性理論におけるRP(randomized polynomial time)とは、以下の3つの属性を持つ確率的チューリング機械で解ける問題の複雑性クラスである。.

新しい!!: モンテカルロ法とRP (計算複雑性理論) · 続きを見る »

技術評論社

株式会社技術評論社(ぎじゅつひょうろんしゃ)は、日本の出版社。主にコンピュータ関連の書籍・雑誌を発行している。.

新しい!!: モンテカルロ法と技術評論社 · 続きを見る »

機械学習

機械学習(きかいがくしゅう、machine learning)とは、人工知能における研究課題の一つで、人間が自然に行っている学習能力と同様の機能をコンピュータで実現しようとする技術・手法のことである。.

新しい!!: モンテカルロ法と機械学習 · 続きを見る »

次元の呪い

次元の呪い(じげんののろい、The curse of dimensionality)という言葉は、リチャード・ベルマンが使ったもので、(数学的)空間の次元が増えるのに対応して問題の算法がなることを表している。 例えば、単位区間をサンプリングするには100個の点を等間隔で、かつ点間の距離を 0.01 以上にならないように配置すれば十分である。同じようなサンプリングを10次元の単位超立方体について行おうとすると、必要な点の数は 1020 にもなる。したがって、10次元の超立方体はある意味では単位区間の1018倍の大きさとも言える。 高次元ユークリッド空間の広大さを示す別の例として、単位球と単位立方体の大きさを次元を上げながら比較してみればよい。次元が高くなると、単位球は単位立方体に比較して小さくなっていく。したがってある意味では、ほとんど全ての高次元空間は中心から遠く、言い換えれば、高次元単位空間はほとんど超立方体の角で構成されており、「中間」がない。このことは、カイ二乗分布を理解する上で重要である。.

新しい!!: モンテカルロ法と次元の呪い · 続きを見る »

決定的アルゴリズム

決定的アルゴリズム(けっていてきアルゴリズム、deterministic algorithm)は、計算機科学におけるアルゴリズムの種類であり、その動作が予測可能なものをいう。入力を与えられたとき、決定的アルゴリズムは常に同じ経路で計算を行い、常に同じ結果を返す。決定的アルゴリズムは最も研究の進んでいるアルゴリズムであり、その多くは実際のコンピュータで効率的に実行できる実用性を備えている。決定性アルゴリズムと言うことも多い。 決定的アルゴリズムは、同じ入力に対しては常に(ひとつの)同じ結果を返すという点で、関数の一種とみなせる。アルゴリズムはその結果の計算の具体的な手順を与えるものである。.

新しい!!: モンテカルロ法と決定的アルゴリズム · 続きを見る »

擬似乱数

擬似乱数(ぎじらんすう、pseudorandom numbers)は、乱数列のように見えるが、実際には確定的な計算によって求めている擬似乱数列による乱数。擬似乱数列を生成する機器を擬似乱数列生成器、生成アルゴリズムを擬似乱数列生成法と呼ぶ。 真の乱数列は本来、規則性も再現性もないものであるため、本来は確定的な計算によって求めることはできない(例:サイコロを振る時、今までに出た目から次に出る目を予測するのは不可能)。一方、擬似乱数列は確定的な計算によって作るので、その数列は確定的であるうえ、生成法と内部状態が既知であれば、予測可能でもある。 ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。シミュレーション等の一般的な用途には、対象とする乱数列の統計的な性質が、使用対象とする目的に合致しているかどうかを判断する。これを検定と言い、各種の方法が提案されている。 しかし、特に暗号に使用する擬似乱数列については注意が必要であり、シミュレーション等には十分な擬似乱数列生成法であっても、暗号にそのまま使用できるとは限らない。暗号で使用する擬似乱数列については暗号論的擬似乱数の節および暗号論的擬似乱数生成器の記事を参照。.

新しい!!: モンテカルロ法と擬似乱数 · 続きを見る »

数値積分

数値積分(すうちせきぶん)とは、狭義には与えられる関数の定積分の値を、解析的にではなく数値的に求めることであり、広義には与えられる導関数から原関数を求めること、また微分方程式を数値的に解くことを含む。数値解析の一つである。 以下では、狭義の数値積分(一変数の関数の定積分の値を求める方法)について述べる。.

新しい!!: モンテカルロ法と数値積分 · 続きを見る »

数値解析

バビロニアの粘土板 YBC 7289 (紀元前1800-1600年頃) 2の平方根の近似値は60進法で4桁、10進法では約6桁に相当する。1 + 24/60 + 51/602 + 10/603.

新しい!!: モンテカルロ法と数値解析 · 続きを見る »

ここにリダイレクトされます:

モンテカルロ・シミュレーションモンテカルロシミュレーショングランドカノニカルモンテカルロ法変分モンテカルロ法拡散モンテカルロ法

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »