モンテカルロ法とは - IT用語辞典
モンテカルロ法 【Monte Carlo method】 モンテカルロシミュレーション / Monte Carlo simulation 概要 モンテカルロ法（Monte Carlo method）とは、数値計算手法の一つで、乱数を用いた試行を繰り返すことにより近似解を求める手法。関数などにランダムな入力値を次々に投入し、対応する出力値を統計的に処理することで結果を推定する。 ある事象をモデル化した数式や関数があるとき、その定義域に含まれる値をランダムにたくさん生成して実際に計算を行い、得られた結果を統計的に処理することで推定値を得ることができる。 数式を解析的に解くのが困難あるいは不可能な場合でも数値的に近似解を求めることができる。確率論的な事象についての推定値を得る場合を特に「モンテカルロシミュレーション」と呼ぶ。名称の由来はカジノで有名なモナコ公国のモンテカルロ地区である。 例えば、
疑似乱数に状態なんていらない - あどけない話
State モナドと疑似乱数で書いたように、遅延評価が利用できる言語では、無限数列が扱えるので、疑似乱数を使う際に状態を持たなくてもよい。その一例として、モンテカルロ法による円周率の近似を挙げてみる。 XY 平面に単位円を考える。 radius :: Double radius = 1.0この円がぴったり収まる大きさ1の正方形を描く。ここで、第一象限のみを考える。正方形のうち、第一象限にある部分の面積は、1/4。第一象限にある円の面積は、全体の 1/4 だから π/4。 モンテカルロ法では、第一象限の正方形の中に、ランダムに点(x,y)を打つ。たくさんのランダムな点を、疑似乱数から生成しよう。そのとき、状態を持つのではなく、乱数の無限数列を生成する。 import Random randomSeq :: Int -> [Double] randomSeq seed = randomRs (
JavaScriptによる様々な方法での円周率計算(モンテカルロ法など) - konisimple
考察 1,000回で誤差3%程度に、10,000回で誤差1%程度に、100,000回で誤差0.1%程度に、1,000,000回で誤差0.05%程度に、10,000,000回で誤差0.01%程度になります。 コンピュータのスペックによっては、10,000,000回以降はきつい場合があります。ブラウザが応答しなくなるかもしれません(><) あんまり回数を増やすとJavaScriptの疑似乱数の限界にぶちあたる気がします。
モンテカルロ法を試す―円周率の評価―
確率法則を用いて問題を解くモンテカルロ法（Monte Carlo meyhod）では、質のよい乱数が必要である。 C言語で用意されている関数randと、高品質で高速に乱数を生成できるとして知られるメルセンヌ・ツイスタを利用して、円周率を評価してみる。 また、その際のアルゴリズムとして「あたりはずれ法」と「粗いモンテカルロ法」を用いて計算する。 図１のような単位円の第１象限領域の面積をモンテカルロ法にて求め、 解析的に求められる面積$\pi/4$と比較することによって、円周率の評価を行うことにする。 図１．単位円の第１象限領域 あたりはずれ法 あたりはずれ法とは、面積を評価したい領域$S_A$を面積が既知の領域$S$で囲み、 領域$S$上に分布が一様になるように$N$個の点を降らせる。 領域$S_A$上に落ちた点の数が$N_A$であれば、$S_A$の面積は、 で評価することができる。 図１の
奈良女子大学附属中等教育学校 公式サイト
2025年4月11日 新着情報 2025年春 進路状況 2025年4月10日 新着情報 柳汀会奨学基金受給申請の募集開始 2025年3月24日 新着情報学校からのお知らせSSHの活動教育研究 SSH先導的改革Ⅰ期（文理融合基礎枠）に内定 2025年3月23日 新着情報SSHの活動SSH 生徒の活動報告 【成果報告】サイエンスキャッスル ジャパン 2025に参加 2025年2月21日 新着情報SSHの活動SSH 生徒の活動報告 【成果報告】第10回高校生国際シンポジウムで文部科学大臣賞を受賞 2025年2月13日 新着情報生徒の活動 【活動報告】第２回西日本公立高校テニス大会 第3位 2025年2月7日 新着情報入学情報 令和7年度入学適性検査の結果をupしました 2025年2月4日 新着情報SSHの活動SSH 生徒の活動報告 【成果報告】第２回Show and Tell プレゼンテーション
アルゴリズムイントロダクション輪講 #3 が終わりました - ミラクル☆モテメンの脱オタ日記
今回は第1回インターンの id:tarao (ダイアリー書いてない (´；ω；｀)) さんの担当、5章の確率論的解析と乱択アルゴリズムでした。前章までは各アルゴリズムの最悪の時間計算量を考えていましたが、現実には最悪の場合の入力ばかりがやってくるのではなく、典型的・平均的な場合の時間計算量を求めたいこともあります。確率論的解析がこういう時に必要になるようです。また、その時指標確率変数というのを用いると計算が楽になる (ことが多い) ということです。 今回は輪講中に、いくつか練習問題にも触れました。 5.1-3 偏ったコインを用いて 0,1 をそれぞれ 1/2 の確率で出力するアルゴリズムを作るには？ → 2回振って (表、裏) か (裏、表) と出たらそれぞれ 0, 1 を返し、そうでなければやり直し、を繰り返す。 5.3-2 恒等置換以外の任意の置換をランダムに生成するアルゴリズム？ →
乱拓アルゴリズムの世界へ
1 �� Randomized Algorithm �� 2 1 (randomized algorithm) . . . (probabilistic algorithm, stocastic algorithm) [8, 11] (randomized algorithm) 2 2 (1) (2) 1 2E-mail: watanabe@is.titech.ac.jp procedure QuickSort(A, B); % Given A[1..n], compute its sorted permutation to B[1..n]. i ← random number from {1,...,n}; k ← A[i]; A1 ← elements of A[1..n] smaller than k; A2 ← the other elements of A[1..n]; Quic
乱択アルゴリズム紹介(Color-Coding) - Preferred Networks Research & Development
吉田です。今まで数解に渡って乱択アルゴリズムを紹介してきました。そろそろ解析やアイデアがシンプルかつ結果が綺麗な乱択アルゴリズムは尽きてきたかと思っていましたが、もう一つとても素敵な手法が有るのを思い出しましたので解説します。Color Codingと呼ばれる手法です。 \(G = (V, E)\)をグラフ、\(s,t\in V\)を\(G\)中の二頂点、\(k\geq 0\)を整数とします。\((s,v,k)\)パスとは、\(s\)と\(t\)を結ぶパスで内点の個数が丁度\(k\)個のものを指します。但しパスは同じ頂点や枝を二度使ってはいけません。例えば以下の図で赤い線で示されているパスは\((s,t,5)\)パスです。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
円周率の計算-n次元球体積の計算(モンテカルロ法)
Monte Carlo法による円周率の計算
シミュレーション
ソフトの砂場(円周率)
アルゴリズムイントロダクション 第5章 確率論的解析と乱択アルゴリズム
http://www.technotype.net/hugo.elias/models/m_perlin.html
実践的アルゴリズム特論 10,11回目: 乱択アルゴリズム
確率と計算
クイックソートの動作と計算量解析
暗号基盤特論 #03 モーメントと偏差
Quasi-random sequences
Group: トレーニング講座（3/06 (日)) | アルゴリズム プログラミング