アルゴリズム百選 - フィボナッチ数列に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))である”という． この定義だと、フィボナッ
nobilog2: 好きなアルゴリズム：モンテカルロ法
今週前半、小飼弾さんの「404 Blog not found」が「プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10」という記事を載せていたが、仕事も一段落間近かなので、その記事を見て以来、書きたいと思っていたことを書いてみようと思う。 nobilog2復活へのリハビリエントリーだ。 小飼さんの記事は、Hatena Questionの「あなたが一番好きなアルゴリズムを教えてください。また、その理由やどんな点が好きなのかも教えてください」がきっかけになった記事のようだ。 私はプログラマーではないが、まだパソコンが8ビットで「マイコン」と呼ばれていた時代に出会って衝撃を覚えたアルゴリズムがある。 もしかしたら一般に言うアルゴリズムとは別なのかもしれないが、Wikipediaでも"algorhythm"と書かれていたので許して欲しい（広義のアルゴリズムにはぎりぎり入るのではないだろ
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) のどちらか一方に排
【インフォシーク】Infoseek ： 楽天が運営するポータルサイト
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.algo.ics.tut.ac.jp/~yusuke_abe/html/2007-07-04.html
阿部めも / 2007-12-05 - 最近話題のブログ
カジュアルなO記法 | 配電盤
O(1)というのはご機嫌に速いということ？ | 配電盤
4.2.4 Runge-Kutta Method for 2nd order ODE
Making Noise - Ken Perlin