アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org
http://blog.livedoor.jp/dankogai/archives/50958771.html 弾さんの記事。 フィボナッチ数列の一般項を求める式を使ったときってO(1)って言えるのだろうか？ 「O()が小さいからといって速いとは限らない」が抜けている。 読んでいるうちにアルゴリズムの本が書きたくなってきたりして。 追記(1)： http://blog.livedoor.jp/dankogai/archives/50962361.html 弾さんの追加記事。 弾さんのO記法の定義がわかりません。奥村先生の『C言語による最新アルゴリズム事典』の「O記法」には以下のように書かれています。 もっと正確にいえば，定数c(> 0)，Nが存在して，n≧Nならば必ず|f(n)|≦c|g(n)|が成り立つとき，“n→∞のときf(n)＝O(g(n))である”という． この定義だと、フィボナッ
ActionScript 3.0 : 高品質乱数 メルセンヌツイスター（Mersenne Twister）
高品質な疑似乱数アルゴリズムとして有名なMersenne Twisterです。 ゲームに高い品質の乱数が求められることがあるかはわかりませんが、 このサイトではモンテカルロ法等を使用したプログラムも作っていく予定なので、 ActionScript 3.0に移植しました。 乱数に高い品質を求める理由が特にない場合は付属のMath.random()メソッドを使う方が手軽かもしれません。 参考URL : Mersenne Twister : A random number generator 以下使い方、実行例、メルセンヌツイスタークラスのソースプログラムです。 使い方 var mt:MersenneTwister; var rand:Number; mt = new MersenneTwister(0); rand = mt.nextNumber(); 実行例 ※ このFlash
SIMD-oriented Fast Mersenne Twister (SFMT)
SIMD-oriented Fast Mersenne Twister (SFMT): twice faster than Mersenne Twister*1. English Version 最新情報 SFMT ver1.5.1 をリリースしました。(2017/2/22) SFMT ver1.5 をリリースしました。 53bit精度double出力にバグがありました。(2017/2/7) SFMT 論文の正誤表 を追加しました。(2015/9/1) dSFMT ver2.2.3 をリリースしました。(2013/12/19) SFMT ver1.4.1 をリリースしました。(2013/12/19) dSFMT ver2.2.2 をリリースしました。 ver2.2.2 はVisual C++ 2012 でコンパイルエラーになる部分を修正しました。 (2013/9/17) dSFMT ver
Concurrent Clean : 乱数生成器 - lethevert is a programmer
Cleanに付属している乱数生成器はMersenne Twisterだけなのだけれど、暗号学的に安全な乱数生成器もあるほうがいいのではないかなと思って調査中。 Wikipediaに名前の挙がっている Blum-Blum-Shub法と Fortuna法の２つを調査。 線形合同法のようなより軽い乱数生成器もあると便利なのかなぁ。 - Fortuna法は、/dev/randomなどで使われる乱数生成器のアルゴリズムらしい。Linuxで使うことができるらしい。以前のアルゴリズムはYarrowというアルゴリズムがあって、Mac OS XやFreeBSDで使われているそうな。 http://en.wikipedia.org/wiki/Fortuna_%28PRNG%29 http://www.linux.or.jp/JM/html/LDP_man-pages/man4/random.4.html -
乱数生成器 - lethevert is a programmer
昨日の調査で分かってきたこと。 システムが提供する（可能性のある）乱数生成器には次の４種類がある。 情報理論的な'真'の乱数生成器 各ビットが１ビットのエントロピーを持つ乱数を生成する。OSなどがハードウエアを通して外部のエントロピー源から情報を得て生成する。 暗号理論的な擬似乱数生成器 (CSPRNG) 暗号理論的に予測不可能な乱数を生成する。乱数生成のアルゴリズムは既知であっても、乱数種が暗号理論的に推測不可能なため、生成される乱数が予測不可能。たとえば、Blum-Blum-Shab法は、RSAなどと同じく素因数分解をベースにしている。 統計学的な擬似乱数生成器 統計学的に健全な乱数を生成する。しかし、セキュリティ用途には不適。たとえば、Mersenne Twisterの標準的な実装であるMT19937の場合は、624個の出力を観察すれば、それ以降の出力を予測可能になる。 不完全な擬似
メルセンヌ・ツイスタ - Wikipedia
メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数列生成器 (PRNG) の1つである。従来の疑似乱数列生成手法にある多くの欠点を克服し、高品質の疑似乱数列を高速に生成できるものとして、1996年に松本眞と西村拓士によって国際会議で発表された（1998年1月に論文掲載）。考案者らによる実装が修正BSDライセンスで公開されている。 「メルセンヌ・ツイスタ」は厳密にはある手法に基づいた乱数列生成式（あるいは生成法）の族を指し、内部状態の大きさや周期は設定可能である。以下の長所と短所では、メルセンヌ・ツイスタ自体、よく使われている生成法のMT19937、さらにその実装について、区別することなく述べている。 219937-1 (≒4.315×106001) という長い周期が証明されている。 この周期は、名前の由来にもなっているように（24番目の）メルセンヌ素数であり、
数学って面白い！？ : ベンフォードの法則 - livedoor Blog（ブログ）
新聞や雑誌などを見てみると、さまざまな数字が書いてあります。 日付、ページ数、金額、サッカーの得点、などなど。 さて、そんなさまざまな数字の中で、「１」からはじまるもの（つまり、１や１２や１４６や１５８７など）は、どのくらいあるのでしょうか？ 単純に考えると、最高位に来る数字は１から９までの９通りありますから、「１」からはじまる確率は １/９ でおよそ１１％くらいかという予想が立ちます。 しかしながら、「１」から始まる数字は、実は全体の３０％を占めているのです。 これはベンフォードの法則と呼ばれています。 もっと正確に言うと、一般にｎ（１≦ｎ≦９）からはじまる数字の存在確率は になります。 これは数字に条件などを加えない限りは、常に成り立ちます。 ｎ＝１を代入すると、約３０％という値が出てきて、更にｎ＝２を代入すると、約１８％になります。 ということは、世の中の数字の約半分は、１か２で始ま
サービス提供終了のお知らせ
日頃より、Momoたろうインターネットクラブをご愛顧いただきまして誠にありがとうございます。 「ホームページサービス」のサービス提供は2015年11月30日をもちまして終了させていただきました。 これまで長らくご利用いただき、誠にありがとうございました。 今後も、皆様によりよいサービスをご提供させていただけるよう、サービス品質向上に努めて参りますので、何卒、ご理解いただけますようお願 い申し上げます。 ＜Momoたろうインターネットクラブをご契約のお客様へ＞ 後継サービスとして「userwebサービス」を提供させていただいております。 詳しくは、以下のリンクをご参照ください。 ▼「userwebサービス」のご案内 http://www.ejworks.info/userhp/mmtr/index.html 今後ともMomoたろうインターネットクラブをご愛顧いただけますようお願い申し上げます
岩井慶一郎のIT的数学入門
ド・モルガンの法則と論理回路 [2008年03月21日] 以前，この欄でド・モルガンの法則を取り上げました。今回は，ド・モルガンの続きです。1回ずつ読みきりにしているので，ド・モルガンの続きといっても別の話題です。 自動掃除機を数学的に考えてみる [2007年10月22日] 先日，知り合いから，このページを見たよという電話をもらい，「1回目の記事の回答がないじゃないか」と指摘されてしまいました。ということで，今回は1回目の記事の一部をフォローします。掃除機の話です。
プログラミングに役立つ 「ド・モルガンの法則」
集合論の最も大事な定理の1つに，「ド・モルガンの法則」というのがあります（ド・モルガンの定理とも言います）。これは情報処理技術者試験などでも頻出なのでご存知の方も多いと思いますが，復習を兼ねて改めて書くと， A, B を集合としたときに， 1. Not (A∩B) = Not(A) ∪ Not(B) 2. Not (A∪B) = Not(A) ∩ Not(B)というものです（図1参照。右辺が具体的にどうなるか塗ってみてください）。 さて， ∩は「かつ」とよみ，英語では「AND」， ∪は「または」とよみ，英語では「OR」， と書くので，上の式は， 1. Not (A AND B) = Not(A) OR Not(B) 2. Not (A OR B) = Not(A) AND Not(B) ということになります。ここで，世の中のすべての事象は X または Not(X) のどちらか一方に排
Good Math, Bad Math : Graph Coloring Algorithms
Search this blog Profile Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer. My professional interests center on programming languages and tools, and how to improve the languages and tools that are used for building complex software systems. Other Information Graph coloring is deceptively simple. The idea of coloring a graph is very straightforwa
Naive Bayes classifier - Wikipedia
Example of a naive Bayes classifier depicted as a Bayesian Network In statistics, naive (sometimes simple or idiot's) Bayes classifiers are a family of "probabilistic classifiers" which assumes that the features are conditionally independent, given the target class.[1] In other words, a naive Bayes model assumes the information about the class provided by each variable is unrelated to the informat
ユビキタスの街角 データ圧縮手法の応用
PPM (Prediction by Partial Matching)というデータ圧縮アルゴリズムがある。 一般に、あるデータ列が与えられているとき、次に来るデータを予測することができればデータ圧縮を行なうことができる。 データ列から判断して次に来るデータが「a」だと確実に判断できるときは「a」を記述する必要が無いからである。 PPM法では、既存のデータ列中の文字列出現頻度を計算することによってこのような予測を行なう。 たとえば「abracadab」というデータの次にどの文字が来るか予測する場合、 「a」は4回、「b」は2回出現している 「b」の後に「r」が続いたことがある 「ab」の後に「r」が続いたことがある ... といった情報を累積して確率を推定する。 この場合、 (3)から考えて次の文字は「r」である確率が高いが、 (1)も考慮すると「a」の確率もある、という風に計算を行なう。
パワー法による固有値と固有ベクトルの求め方
パワー法による固有値と固有ベクトルの求め方 Last modified: May 16, 2002 固有値・固有ベクトルを求める簡単な方法としてはパワー法がある（パワー法は，あくまでも簡便法である。より一般的で精度も十分で計算速度も速いアルゴリズムは数多くある）。 例題： 「行列 $\mathbf{A}$ の，固有値と固有ベクトルを求めなさい。」 \[ \mathbf{A} = \left ( \begin{array}{rrr} 1.0 & 0.5 & 0.3 \\ 0.5 & 1.0 & 0.6 \\ 0.3 & 0.6 & 1.0 \end{array} \right ) \] 固有値・固有ベクトルを求めたい行列を $\mathbf{A}$ とする。 > ( A <- matrix(c(1, 0.5, 0.3, 0.5, 1.0, 0.6, 0.3, 0.6, 1.0), b
ベイジアンフィルタについて
最近話題のベイズ理論を用いたフィルタについて整理してみました．まず，ベ イズ理論が注目され始めたというニュースを最初にみたのが，ＭＳも注目する “ベイズ”って何だ(oricom.co.jp)でした． このときは対して気にもとめていませんでしたが，再度興味をそそられ出した のが，グーグル、インテル、MSが注目するベイズ理論(CNET)のニュース． MSだけならまだしも，Googleが，というのが自分的には大きかったです．しか し，このニュースだけでは，この技術が具体的にどのように採用されるのか， 特に検索エンジンのような大規模なものに適用可能かどうかは大きな疑問でし た． そもそも，このベイズ理論がどこに聞いてくるのかということを考えるとその 疑問は自然だと思います．ベイズ理論（ベイズ推定）は，過去に起きた事象の 確率を利用して未来を予測する手法です．そのため，直感的にはユーザごとの 最適化
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
カジュアルなO記法 | 配電盤
4.2.4 Runge-Kutta Method for 2nd order ODE
Making Noise - Ken Perlin
Amazon.co.jp: 空間的データ構造とアルゴリズム: Elmar Langetepe (著), Gabriel Zachmann (著), 中本浩 (翻訳): 本
ニュートン法