モンテカルロ法とは - 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$の面積は、 で評価することができる。 図１の
画像処理 - HexeRein
description 画像処理について。 ソースは24bitのビットマップ（及びその互換）、EclipseによるJava環境（org.eclipse.swt.graphicsとjava.utils.Arrays。具体的にはこんな感じ）を前提に記述していますが、ピクセル毎に入出力できる環境であれば任意に読み替えて問題ありません。 具体的には、画像から幅、高さ、指定場所の画素といったものが利用出来、なおかつそれから画像を生成できることが条件となります。 低機能でも良ければC++用の簡易クラス（.cppファイル、.hファイル）とかあります。 ただし、簡易クラスの方では色データはRGB纏まった形で取得するのではなくて、GetR等のように一つ一つの色を取り出す必要がありますので、以下のソースコードそのままでは使用できない場合（や、面倒な前処理が不要となる場合）があります。 なお、ソースそれ自体は適
暴走するアルゴリズム、ウィーナーの危惧 - Zerobase Journal
金融の世界ではマシン同士の取引が「暴走」した事例が知られています。今後、多くの分野でマシン間通信が導入されていきますが、同様のリスクをはらんでいると言えます。これは単にリスクの量的な問題であるだけでなく、統治の問題としても考えるべきではないかと思います。 Wired日本版に「暴走するアルゴリズム」というシリーズがありました。 アルゴリズムはあまりにわれわれの金融システムに浸透しているので、もはや市場はそれなしには機能しなくなってしまっている。（...） だが最悪の場合、それは不可解でコントロール不能のフィードバックのループとなる。これらのアルゴリズムは、ひとつひとつは容易にコントロールできるものなのだが、ひとたび互いに作用し合うようになると、予測不能な振る舞いを─売買を誘導するためのシステムを破壊しかねないようなコンピューターの対話を引き起こしかねないのだ。（...） 今日ではこれらの唐突
エンジニアの面接でアルゴリズムを組ませる理由 | quipped
@shibataismさんが、日経Bizアカデミーに「日本のエンジニアはシリコンバレーで通用するのか？」という記事を書いている。 「僕は文系だけど、エンジニアとして一流だ」と自己主張する人がいますが、採用側から見て実際にそうであることは稀です。シリコンバレーの企業では、採用面接の際に「 ○○アルゴリズムを書いてみてください」といったように、具体的かつ実践的な課題が出されます。こうした面接で、文系の人は（そもそも大学できちんと勉強したことがないので）適切な回答をするのが難しい場合が多いのです。 とあるのだが、アメリカの大学で数学を勉強し、プログラミングは独習したソフトウェアエンジニアとして1、少し補足してみたいと思う。 「文系」だからといって諦める必要はない これはまあその人の経験によるのだろうけど、文系出身のエンジニアだからといって諦める必要はない。[平林さん](https://falla
突然素因数分解プログラムfactorに対抗したくなった - KENJI’S BLOG
せっかく32ビット素数表を作ったので、factorコマンドに素因数分解勝負を挑んでみた。ちなみに、factorコマンドとは、Linuxに標準でついている素因数分解プログラムです。Linuxに標準でついてるくらいなので、多分アルゴリズム的にかなり速い素因数分解ができる（ハズだと思います）。 # time factor 18446744073709551615 18446744073709551615: 3 5 17 257 641 65537 6700417 real 0m0.001s user 0m0.000s sys 0m0.000s # こんな風に、64ビット最大値の18446744073709551615を、わずか0.001秒で素因数分解します。ただし、素数の値が大きくなると、低速になります。 # time factor 18446744073709551609 1844674407
参考：大きい要素の処理
内容 スライド 1 参考：大きい要素の処理 スライド 2 ちょっと寄り道 （一個一個が大きいデータを処理する工夫） スライド 3 大きいデータを処理する工夫２ スライド 4 大きいデータを処理する工夫3 スライド 5 実現 スライド 6 ４－４：比較によらないソート スライド 7 比較によらないソート スライド 8 バケットソート スライド 9 バケットソートの動き１ スライド 10 バケットソートの実現 スライド 11 バケットソートの動き２(添字を用いた場合） スライド 12 バケットソートの実現2 スライド 13 バケットソートの計算量 スライド 14 基数ソート スライド 15 基数ソートの動き（３桁） スライド 16 練習 スライド 17 基数ソートの実現 スライド 18 基数ソートの計算量 スライド 19 ４－５：ソート問題の下界 スライド 20 問題とアルゴリズム スライド
読むべきアルゴリズムの本
勉強しなければならないのである。 長くなるので、ここで折り畳んでしまう。 【有料・和訳有】Introduction to Algorithms おそらく一番有名なアルゴリズム本。MITの教科書。 日本語版もあるが、上記は第３版なのに対して、日本語版は第２版までが出ている。 しかも３分冊されていて、３冊目は第１版のものしかないため、私が買い漁った時でも絶版。 アルゴリズムイントロダクション（改定２版） 第１巻 数学的基礎とデータ構造 アルゴリズムイントロダクション（改定２版） 第２巻 アルゴリズムの設計と解析手法 アルゴリズムイントロダクション 第３巻 精選トピックス 【有料・和訳有】Algorithm Design ２番目に有名なアルゴリズム本か。こっちはコーネル大学の教科書。 なんとタイムリーなことに、今年の１０月に第２版が出るらしい。 リンクはその第２版へのもの。 買ってないのだが、1
Type Inference brings JS improvements to Firefox Beta – Future Releases
Blog by Brian Hackett, Firefox Engineer Firefox 9 features the release of Type Inference, or TI, a research project under way for over a year. TI is a feature in the SpiderMonkey Javascript engine which generates type information about Javascript programs through a combination of analyzing the program’s code and monitoring the types of values as the program executes. This type information is used
Fast and Precise Hybrid Type Inference for JavaScript
Fast and Precise Hybrid Type Inference for JavaScript Abstract1 JavaScript performance is often bound by its dynamically typed na-2 ture. Compilers do not have access to static type information, mak-3 ing generation of efficient, type-specialized machine code difficult.4 To avoid incurring extra overhead on the programmer and to im-5 prove the performance of deployed JavaScript programs, we seek6 t
アルゴリズムイントロダクション輪講 #3 が終わりました - ミラクル☆モテメンの脱オタ日記
今回は第1回インターンの id:tarao (ダイアリー書いてない (´；ω；｀)) さんの担当、5章の確率論的解析と乱択アルゴリズムでした。前章までは各アルゴリズムの最悪の時間計算量を考えていましたが、現実には最悪の場合の入力ばかりがやってくるのではなく、典型的・平均的な場合の時間計算量を求めたいこともあります。確率論的解析がこういう時に必要になるようです。また、その時指標確率変数というのを用いると計算が楽になる (ことが多い) ということです。 今回は輪講中に、いくつか練習問題にも触れました。 5.1-3 偏ったコインを用いて 0,1 をそれぞれ 1/2 の確率で出力するアルゴリズムを作るには？ → 2回振って (表、裏) か (裏、表) と出たらそれぞれ 0, 1 を返し、そうでなければやり直し、を繰り返す。 5.3-2 恒等置換以外の任意の置換をランダムに生成するアルゴリズム？ →
アルゴリズムイントロダクション輪講 #1 が終わりました - ミラクル☆モテメンの脱オタ日記
月曜日にアルゴリズムイントロダクション輪講の第1回を開催しました。http://tokyoenvious.xrea.jp/ria-kyoto/ria-01.pdf が輪講スライドです。輪講中でホワイトボードを使って説明したところもあり (Θ記法のところとか)、資料としては不親切なところもあるかもしれません。 第1巻の最初は基礎部分で、なるべく早めにアルゴリズムそのものに触れたいというのもあり初回だけ一度に 3章分やったのですが、なかなか大変でした。FOR ループの正しさを検証するためのループ不変条件や、アルゴリズムの漸近的効率を記すための漸近記号のところの理解 (特に o や ω) がなかなか難しいようです。 個人的には、漸近記号については p.48 の O 〜 ≦ Ω 〜 ≧ Θ 〜 = o 〜 ω 〜 > という対応がしっくりきましたが、なかなか上手く説明できませんでした。終わった後も
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
準乱数および議事乱数を用いて円周率を求めるFORTRANプログラム
円周率の計算-n次元球体積の計算(モンテカルロ法)
Monte Carlo法による円周率の計算
個人投資家必見、アルゴリズム取引の凄さが何となく分かる動画「アルゴリズムが形作る世界」 : 市況かぶ全力２階建
アルゴリズムイントロダクション 第5章 確率論的解析と乱択アルゴリズム
http://www.technotype.net/hugo.elias/models/m_perlin.html