乱択アルゴリズム - Wikipedia
乱択アルゴリズム（らんたくアルゴリズム）、ランダム・アルゴリズム（英: randomized algorithm）または確率的アルゴリズム（かくりつてきアルゴリズム、（英: probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的とすることがある。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を期待実行時間[1]と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。 n 個の要素からなる配列から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純
モンテカルロ法 - Wikipedia
モンテカルロ法（モンテカルロほう、（英: Monte Carlo method、MC）とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。 計算理論[編集] 計算理論の分野において、モンテカルロ法とは誤答する確率の上界が与えられる乱択アルゴリズム（ランダム・アルゴリズム）と定義される[1]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。一般にモンテカルロ法は独立
メルセンヌ・ツイスタ - Wikipedia
メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数列生成器 (PRNG) の1つである。1996年に国際会議で発表されたもので（1998年1月に論文掲載）松本眞と西村拓士による。既存の疑似乱数列生成手法にある多くの欠点がなく、高品質の疑似乱数列を高速に生成できる。考案者らによる実装が修正BSDライセンスで公開されている。 「メルセンヌ・ツイスタ」は厳密にはある手法に基づいた乱数列生成式（あるいは生成法）の族を指し、内部状態の大きさや周期は設定可能である。以下の長所と短所では、メルセンヌ・ツイスタ自体、よく使われている生成法のMT19937、さらにその実装について、区別することなく述べている。 219937-1 (≒4.315×106001) という長い周期が証明されている。 この周期は、名前の由来にもなっているように（24番目の）メルセンヌ素数であり、保証され
アルゴリズムパズル
大学で計算機科学を教える著者が、「パズルを解くことで、アルゴリズム的思考を鍛える」というコンセプトに基づいて、古今東西150の「アルゴリズム的」な数学パズルを収録。優れたアルゴリズム設計戦略と分析テクニックを通して、アルゴリズム的思考と柔軟な発想を育てます。また、近年では、入社試験にパズル的な難問を出す企業も増えており、その対策としても役立つ一冊です。 質問形式の序文 謝辞 パズル一覧 チュートリアルのパズル 本編のパズル 墓碑銘パズル 第1章 チュートリアル 一般的なアルゴリズム設計戦略 魔方陣（Magic Square） nクイーン問題（The n-Queens Problem） 有名人の問題（Celebrity Problem） 数当てゲーム（Number Guessing）（別名20の扉（Twenty Questions）） トロミノ・パズル（Tromino Puzzle） アナグ
6さいカンファレンス 第3回「アルゴリズムを自力で生み出すプログラムを作ろう！」まとめ
2012/09/06にくいなちゃんさん主催で開催された6さいカンファレンスのまとめ。 第3回は「アルゴリズムを自力で生み出すプログラムを作ろう！」です。 勝手にまとめてしまったので、何か問題があれば@shogo82148まで。 WELCOME TO HEAVEN!! くいなちゃん: ところでみなさん、次の( ) に入る数を当ててください 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ( ) くいなちゃん: はい、正解です！ これは、フィボナッチ数列と呼ばれ、 前の2つの値の和が、次の値になっているという数列です くいなちゃん: これを、f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 3, f(5) = 5, … と書いていくことにしましょう。 f(10) = 55 ですね！ くいなちゃん: もっと汎用的に考えて、f(x) の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
いつからFIFOがスケールしないと錯覚していた
