javascript - Mathを再発明してみた : 404 Blog Not Found
2010年09月14日06:30 カテゴリMathLightweight Languages javascript - Mathを再発明してみた 「基本というからには四則演算で三角関数実装しないとねー」と思いつつ書いていたら… C言語による最新アルゴリズム事典 奥村晴彦 [javascript]三角関数の基本 Math.random()を除いてMathを全部再発明しおえたので。 多倍長演算バージョンを作る時の下ごしらえにもなるかも。 下ごしらえ 仕様は Math - MDC アンチョコはもはや最新というにはあまりに古い、しかし代わりなき「C言語による最新アルゴリズム事典」。低レベルな車輪を再発明する人必携! 初期化と定数 定数の精度はおおげさに。 MyMath = {}; MyMath.E = 2.718281828459045235360287471352662497757; MyMat
ハチの脳、コンピュータより優れている--英大学調査
ミツバチは、コンピュータでさえ解答を得るのが難しい複雑な数学的問題を解決する能力を備えていることが研究で明らかになった。The Guardianが英国時間10月24日に報じている。 ロンドン大学ロイヤルホロウェイ校の研究結果によると、ハチは、花から花へと飛ぶ際にその最短経路を見つけ出し、一般に「巡回セールスマン問題」と呼ばれる問題を効果的に解決する能力を持っているという。 「巡回セールスマン問題」は、セールスマンがすべての目的地を訪問するという仮定において、その最短経路を見つけることが求められる。コンピュータでは、想定されるすべての経路の長さを比較し、最短経路を選ぶことで解答を得る。 同校が実施した実験では、コンピュータ制御の人工花を使うことで、ハチが単純に花を見つけた順に飛ぶのか、最短経路を見つけようとするのかを調べた。その結果、ハチは、花の位置を調べ、時間とエネルギーを最も節約できる経
ミツバチはコンピュータよりも速く巡回セールスマン問題を解ける | スラド サイエンス
ミツバチは複数の花を最短ルートで移動していることが、ロンドン大学クイーン・メアリー校および同大学ロイヤルホロウェイ校の共同研究で分かったそうだ（ロンドン大学クイーン・メアリー校発表、本家/.）。 複数地点を一度ずつ巡り出発点に戻る最短ルートを求める問題は通称「巡回セールスマン問題」と呼ばれており、ミツバチはこの問題を解くことができることが発見された初めての種であるという。 研究ではコンピュータで制御された人工の花を使い、ミツバチがこの花を「発見した順」に巡るのか、それとも「最短ルート」を見つけ出すのかを検証した。その結果、ミツバチはそれぞれの花の場所を探索したあと最短ルートを飛行するようになったという。 コンピュータでは解くのに何日もかかるこの問題をミツバチが短時間でどう処理しているかを調べることで、複雑な問題の解決に必要な最小限の神経回路を解明できるかもしれないとのことだ。
マルチキークイックソート - sileのブログ
「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも性能が低下しにくい クイックソート + 基数ソート、のような感じ？ ソート方法 基本的には通常のクイックソートと似ていて「ピボット要素*1を選んで、配列を分割する」といったことを繰り返す。 ただし、クイックソートは各段階で配列を二分割(ピボット要素よりも大きいか小さいか*2 )し、そのための比較には要素(文字列)全体を用いるのに対して、マルチキークイックソートでは、配列は三分割(ピボット要素よりも大きいか小さいか、それとも等しいか)され、そのための比較には文字列全体ではなく(各段階で)一文字のみ、が用いられ
Robert Sedgewick - Robert Sedgewick
Robert Sedgewick is the founding chair and the William O. Baker Professor in the Department of Computer Science at Princeton University. He was a member of the board of directors of Adobe Systems from 1990 to 2016, served on the faculty at Brown University from 1975 to 1985, and has held visiting research positions at Xerox PARC, IDA, and INRIA. His research expertise is in algorithm science, data
グラフ理論 - Wikipedia
グラフ理論（グラフりろん、英: Graph theory）は、ノード（節点・頂点、点）の集合とエッジ（枝・辺、線）の集合で構成されるグラフに関する数学の理論である。 グラフ（データ構造）などの応用がある。 グラフによって、様々なものの関連を表すことができる。 6つの節点と7つの辺から成るグラフの一例 例えば、鉄道や路線バス等の路線図を考える際には、駅（節点）がどのように路線（辺）で結ばれているかが問題となる一方、線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。 したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば実際の地理上とは異なって描かれている。つまり、路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。 このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり[1]、グラフがも
一筆書き - Wikipedia
六芒星の一筆書きの例。 一筆書き（ひとふでがき）とは、広い意味では「筆記具を平面から一度も離さず線図形を描く」ことである。狭い意味では、これに加えて「同じ線を二度なぞらない（点で交差するのはかまわない）」という条件が加わる。 以下は後者の狭い意味での一筆書きについて記す。 三角形「△」や四角形「□」は一筆書き可能だが、十字「+」は一筆書きできない。また、五芒星や白星「☆」、六芒星「✡」は一筆書き可能だが、アスタリスク「＊」は一筆書きができない。このように、一筆書きできる図形とできない図形がある。 「与えられた図形が一筆書き可能かどうか」という問題の例として、「ケーニヒスベルクの橋の問題」（独: Königsberger Brückenproblem）が知られている。なお、ケーニヒスベルクとは実際にあった場所の名前である。
de Bruijn Graph を使った de novo アセンブリの発想がすごい件 - ほくそ笑む
Velvet や ABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう？と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。 ケーニヒスベルクの橋 まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。 「ケーニヒスベルクの橋」は、次のような問題です。 18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大き
Risan Suugaku - 一筆書き
一筆書き えっと、小学校ではですね、漢字の書き順を習うわけですよね。 書き順っていうのは、まあ昔の習字の影響もあると思うんですけども、非常にリーズナブルな書き方なわけです。やっぱり書き順と違う書き方をすると、何かおかしいわけですね。あるいは単にそれは、昔トレーニングされてておかしいと思うのかもしれないですけど。 で、これ、「口」なわけです。ちなみに「口」という字をこういう風に書くと、やっぱりおかしいとぼくらは思うように教育されているわけですが、まあ、そう書いてもいいわけです。まあ、これは、「口」っていうのは例えばこういう風なグラフだと思ってもいいわけです。 ここに要するに点があって、その間を枝で結ばれているグラフだと思ってもいいですね。 で、もう既にさっき僕が「口」を縦長に書いたのから、もう分かっている人もいるかも知れないけど、まあこれ、ロ(ろ)でもいいんですが、今度はですね、 (カキカキ
nabokov7; rehash : 意外に奥が深いシャッフルアルゴリズム
October 25, 201014:30 カテゴリプログラミング 意外に奥が深いシャッフルアルゴリズム 前の記事に引き続き，ブログチームの「シャッフルのお時間」の話をします。 毎週の進捗ミーティングのあと，次の週の監視(レビュー)相手を決めるためにシャッフルを行うのですが，ここはプログラマ集団。くじ引きとかではなく，ワンライナーでさらっとシャッフルのプログラムなどを走らせて決めたいものですよね。 ということで，進捗ミーティングの最後はシャッフルのお時間と呼ばれ，誰かひとりがプロジェクタにつながったマシン上でライブコーディングをし，その出力結果によって次週の監視相手が決まる，という儀式の時間になりました。 シャッフルの基本のきまりは以下の通りです。メンバー名の配列を入力とし，「見る人→見られる人」の組み合わせを出力するプログラムを書く。「自分自身を担当する人」が発生してはダメ。その場でコー
kd tree（kd木）を使った近傍点検索 - higepon blog
kd tree を使った近傍点検索のメモ。 kd tree の日本語の説明はkd木 - 日本語版 Wikipedia。 近傍点検索の擬似コードがあり、日本語版の元となっているのはkd-tree - 英語版 Wikipedia。 実際に動くコードで分かりやすいものは弾さんのところ。404 Blog Not Found:algorithm - 最近点検索をkd-treeで。 他には An intoductory tutorial on kd-trees という PDF があるが難しい。 kd tree の構築は、平衡木にするためのロジックがいくつかある事をのぞけばとても簡単。弾さんのコードを読めば分かると思う。 近傍点の検索は k 次元で説明されているものが多く分かりづらいと思った。自分で単純な2次元の場合にして考えれば良い。 流れは以下の通り。 検索対象点 p を kd tree 上で bi
コーダーの聖地「TopCoder Open」で日本人が2部門制覇
日本最強のアルゴリズマーたち、世界をうならせる プログラミングコンテストを企画・運営する米TopCoderは10月15日、コンピュータ・プログラミングと創造的設計のトーナメントである「2010 TopCoder Open」で、日本人が2部門を制したことを発表した。 TopCoderでは、さまざまなジャンルのコンテストが開催されており、例えばAlgorithm部門では、ほぼ毎週のようにSRM（Single Round Match）が開催されている。TopCoder Open（TCO）は、年に一度開催されるトーナメント制の大会で、オンラインで行われる数回の予選を経て、米国ラスベガスで開催される決勝戦に参加できる。TopCoderで日々しのぎを削る世界中のコーダーたちの中でも、特に優れた者だけが参加を許されるコーダーの聖域ともいえる大会。 今回のTopCoder Openに日本人としてラスベガス
最大フロー最小カット定理 - Wikipedia
最大フロー最小カット定理（さいだいフローさいしょうカットていり、英: Max-flow min-cut theorem）は、フローネットワークにおける最大フロー問題についての定理である。これは、ネットワークに流れる「もの」の最大流量が、ボトルネックによって決まることを意味している。線形計画法についての定理メンガーの定理から導出することもできる。 左から:1. 与えられたネットワーク。各エッジの容量はすべて等しいとする。2. ひとつのフロー。3. 2の残余ネットワークと、その増加道。 4. 最大フローの残余ネットワーク。s から到達可能な緑の丸印のノードの集合をS, 不可能な青の四角のノードの集合をTとすると、(S, T) が最小カットになっている。 二端子フローネットワーク が与えられたとする。つまり、有限の有向グラフ の各エッジ（辺） に非負実数の容量 が割り当てられており、始点となるノ
フローネットワーク - Wikipedia
フローネットワーク（英: Flow network）は、グラフ理論における重み付き有向グラフの一種であり、各枝に容量（capacity）を設定し、各枝をフロー（flow）が流れる。各枝のフローはその容量を超えることはない。オペレーションズ・リサーチでは、重み付きグラフをネットワークと呼び、頂点をノード、枝をアークと呼ぶ。フローが満足すべき制約条件として、1つのノードに流入するフローとそのノードから流出するフローは常に等しい。ただし、始点（source）と終点（sink）では、その限りではない。このネットワークは、例えば道路網の交通量、パイプを流れる液体、電気回路を流れる電流、その他の何らかのネットワーク上を移動するものをモデル化するのに適している。フローネットワークに関する最適化問題はネットワークフロー問題と呼ばれる。
フォード・ファルカーソンのアルゴリズム - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "フォード・ファルカーソンのアルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2015年11月) フォード・ファルカーソンのアルゴリズム（英: Ford-Fulkerson algorithm）とは、フローネットワークにおける最大フローを求めるアルゴリズムである[1]。レスター・フォード Jr.（英語版、ドイツ語版、フランス語版、ロシア語版） と デルバート・ファルカーソン（英語版、ドイツ語版、スペイン語版、フランス語版） にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であ
ANN - Approximate Nearest Neighbor Library
ANN is a library written in C++, which supports data structures and algorithms for both exact and approximate nearest neighbor searching in arbitrarily high dimensions. In the nearest neighbor problem a set of data points in d-dimensional space is given. These points are preprocessed into a data structure, so that given any query point q, the nearest or generally k nearest points of P to q can be
階乗を求める - d.y.d.
22:56 10/09/04 階乗を求める 去年聞いた中で、私が一番感動した式の話。 k! = limn→∞ nk / nCk kの階乗は、「nのk乗 ÷ n個のものからk個選ぶ組み合わせの数」という式で n を無限に大きくしていったときの収束先、である。 特に難しい証明が要るとかではなくて、nCk = n(n-1)(n-2)...(n-k+1) / k! であることを使うと、 limn→∞ nk / nCk = limn→∞ nk k! / n(n-1)(n-2)...(n-k+1) で、n が k に比べて十分大きければ n も n-k+1 もほとんど同じ値なので、 分子も分母もだいたい n を k 個かけているわけでして、 その部分が相殺して、k! が残るという寸法。 （厳密な表現ではないので、気になる人は厳密に証明してください。） 実装 と、この式自体はそんなに不思議ではないのです
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
生物情報科学科 情報基礎実験 ３年生冬学期 10/26 – 11/5 （森下研究室担当）
サービス終了のお知らせ
Amazon.co.jp: 計算幾何: 理論の基礎から実装まで (アルゴリズム・サイエンスシリーズ 10 数理技法編): 浅野哲夫: 本
