[空を飛ぶ鳥の群れの動きを再現するアルゴリズムの論文] Craig Reynolds: Flocks, Herds, and Schools: A Distributed Behavioral Model
Published in Computer Graphics, 21(4), July 1987, pp. 25-34. (ACM SIGGRAPH '87 Conference Proceedings, Anaheim, California, July 1987.) Flocks, Herds, and Schools: A Distributed Behavioral Model 1 Craig W. Reynolds Symbolics Graphics Division [obsolete addresses removed 2] Abstract The aggregate motion of a flock of birds, a herd of land animals, or a school of fish is a beautiful and familiar par
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」：最強最速アルゴリズマー養成講座（1/3 ページ） 典型的なアルゴリズムをたくさん知っている人間が最強か――？ いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。 アルゴリズマー養成講座と銘打ってスタートした本連載。もしかすると読者の方の興味は、はやりのアルゴリズムや汎用的なアルゴリズムを知ることにあるのかもしれません。しかし、今回は、いわゆる「典型的なアルゴリズム」を用いずに進めていきたいと思います。 なぜ典型的なアルゴリズムを用いないのか。それは、典型的なアルゴリズムばかりを先に覚え、それだけでTopCoderなどを戦っていこうとした場合、それに少しでもそぐわない問題が出た場合に、まったく太刀打ちできなくなってしまう
統計的に正しいランキングを行う方法 - Hello, world! - s21g
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ポジティブ／ネガティブ投票による正しいランキング方法が以下の記事で紹介されています。 How Not To Sort By Average Rating この計算方法では、投票数が少ない場合には分散が大きく不正確な評価で、 投票数が多くなるにつれて分散が小さく正確な評価が得られているという事を考慮しています。以下数式 これはScoreの信頼区間を表しています。 この信頼区間の下界をランキングのスコアにすれば良い事になります。 ここで、は、 です。全体に占めるポジティブ投票数の割合ですね。 は標準正規分布上の 信頼区間の有意確率です。 さて、五段階評価によるRatingに同様のテクニックを適用する場合はどうしたらいいでしょうか
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ : 404 Blog Not Found
2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GCアルゴリズム詳細解説 日本語の資料がすくないGCアルゴリズムについて詳細に解説します トップページページ一覧メンバー編集 × GC 最終更新： author_nari 2010年03月14日(日) 20:47:11履歴 Tweet このWikiが目指す所 GCとは？ GCを学ぶ前に知っておく事 実行時メモリ構造 基本アルゴリズム編 Reference Counter Mark&Sweep Copying 応用アルゴリズム編 IncrementalGC 世代別GC スナップショット型GC LazySweep TwoFinger Lisp2 Partial Mark and Sweep -Cycle Collection- Mostly Parallel GC train gc MostlyCopyingGC(Bartlett 1989) TreadmillGC(Barker 1992)
アルゴリズムコンテストの挑み方 (3) - d.y.d.
17:19 08/11/27 TopCoder Code Jam の練習に……と思ってしばらく前から TopCoder のSRMに参加してたのですが、 せっかくなので cafelier@SRM に記録をつけることにしました。 どういう試行錯誤をしながら提出した時のコードにいたったのかを、 できるだけ詳細にメモろうと思っています。 426以前のは記憶から掘り起こして書いたのでちょい大ざっぱですが。 これまで何回かここで書いたような整然とした考え方を本当に自分がしているかいうと、 してないよなー、と薄々思ってしまっているので、じゃあどういう風にやっているんだろうかと。 自分のふり見て我がふり直す。 20:26 08/11/24 論文 PLAN-X 2009 通ったみたいです。ばんざい。 ただでさえD論まったく間に合う気がしないのに、camera ready版なんて作ってる時間が… オートマトン
正規表現エンジンを作ろう （1）
はじめに こんにちは。hirataraです。 私が初めて正規表現を使ったのは、PerlによるCGIでの文字列処理でした。それから私はPerlを使い続け、今では正規表現なしのコーディングは考えられないほど、正規表現を当たり前の機能として日常的に使っています。昔は標準では正規表現をサポートしていなかったJavaも、今では正規表現をサポートするようになりました。Javaだけではなく、今日ではほとんどの高級言語にとって、正規表現はなくてはならない機能であると言っても過言ではないほどメジャーな機能となっています。 本記事では、この正規表現の舞台裏に光を当てます。一見すると作ることが難しそうな正規表現エンジンですが、その根底には数学的な概念があり、その概念さえ知っていれば基礎となる機能の実装はそんなに難しくありません。この連載ではその数学的な概念をPythonを使って表現しながら、実際に動作する正規表
ガベージコレクションの実装法と評価
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
1日で作る全文検索エンジン - Building a full-text search engine in "ONE" day - - とあるはてな社員の日記
最近、「Introduction to Information Retrieval」というStanfordの大学院向け教科書のドラフトを読んでいます。id:naoyaあたりが勉強会で読んでいる教科書です。この教科書には、効率のいい全文検索システムを作るにはどうすればいいか、という(まさに)教科書的手法が網羅的に書いてあり、そのあたりに興味がある人には、非常に興味深く読めるお勧めの本です。 ただ、面白い面白いと言っているだけでは、エンジニアとしては価値半減ですので、GW中にrubyで一日かけて実装してみました。 さすがに実装は、一日で作ったものですから、非常に素朴です。マルチバイト文字はbi-gramで、シングルバイトはスペースなどの区切り記号で認識しています。インデックスは、rubyの処理系のHashやArrayで保持しており、外部にMarshallで書き出す、というものです。検索エンジン
Üdvözlöm az Óriáscsúszda honlapunkon
CÉGEK, RENDEZVÉNYSZERVEZŐK, ÖNKORMÁNYZATOK! Szórakozási lehetőség gyermekeknek! Rendezvényekre, partikra rendelhetők, vagy bérbe vehető szórakoztató eszközök. Bővebb felvilágosításért kattintson a képekre vagy válasszon a lenti elérhetőségeink közül. További képek Bővebb szöveges cég és szolgáltatás tájékoztató ITT! Elérhetőségeink Telefonszám: +36-30/9659-614
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
「圧縮新聞」を作った - phaの日記
僕は昔からロボットがロボットなりに変な文章を生成して喋ったりする人工無脳とかそういう仕組みが好きで、最近はそのへんの仕組みを勉強していました。それで大体仕組みの基本はわかったので簡単なスクリプトを書いてみたよ。 圧縮新聞 このスクリプトはウェブ上にある新聞社とかのニュースの文章を元にして、バラバラにして圧縮してまとめた文章を作るので、ざっと眺めるだけでその日起こった事件の全体が何となくわかるかもしれません。リロードするたび文章は変わります。 生成例 しょうゆ・みそ業界大手のＮＯＶＡ（大阪市）が入った郵便小包は、北朝鮮の鉄道網を連結する計画だったらしいことが２１日、わかった。タンクに灯油を補給した。検案の結果、財政難などをほとんど与えずに６者協議の外相会議の早期再開に期待を表明した国と製薬会社に賠償を求めた。その後、死亡した。 しくみ こういった人工無脳みたいな文章生成をするには形態素解析と
JavaScriptでジュリア集合を描画:Geekなぺーじ
幅 : , 高さ : ジュリア集合解説 このスクリプトは、以下の数式を実行して色をつけていったものです。 この数式のzとAは実数部と虚数部を持つ複素数です。 Aは定数です。 平面上の各z_0に対して、この計算を繰り返し行っていきます。 この計算を行った結果が特定の値を超えた場合、その計算が発散したとします。 そして、発散するまでにかかった回数で平面上に色をつけていきます。 規定の回数まで行っても発散しない場合は、発散しなかったとして色を塗りません。 (ただし、今回のプログラムでは黒を塗っています。) 実数部の開始位置と終了位置を調整すると、画像全体のズーム率を調整できます。 定数Aの値を変更していくと、模様が変わります。 色々試して見てください。 何を入れていいのか解らない場合などには、以下の値などがお勧めです。 実数 -0.5 ～ 0.5、虚数 -0.5 ～ 0.5、A実数 -0.2、A
『C言語による最新アルゴリズム事典』
奥村晴彦『C言語による最新アルゴリズム事典』技術評論社，1991年，ISBN4-87408-414-1，2400円 大きな画像（1.1M） 1987年10月にPascalを使った『コンピュータ・アルゴリズム事典』を，1991年2月にその改訂版としてANSI C言語を使った『C言語による最新アルゴリズム事典』を出版しました（いずれも技術評論社）。そのサポートページをつくろうと思いながら多忙のためなかなかできませんでした。とにかく始めなければ……というわけで，サポートページまがいのものを作ってみました。 石田晴久ほか『コンピュータの名著・古典100冊』（インプレス，2003年）に選んでいただきました。100冊といっても日本人の書いたものは20％しかなく，たいへん恐縮しています。 Frequently Asked Questions どの銘柄のC言語ですか？ ほぼ当時のANSI Cドラフトに基づ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
システム・エンジニアの基礎知識