先日、質問した内容の続きです 「点の集合Ｐに対して、任意の点の問い合わせ 点q を与えたときの検索アルゴリズム」 http://q.hatena.ne.jp/1239891135 みなさ…
先日、質問した内容の続きです 「点の集合Ｐに対して、任意の点の問い合わせ 点q を与えたときの検索アルゴリズム」 http://q.hatena.ne.jp/1239891135 みなさまのアドバイスのおかげで、計算幾何学というものに出会うことができました ＫＤ木で実装を考えています 今度はその拡張で 「点・線・閉図形の集合Ｐに対して、任意の点の問い合わせ 点q を与えたときの検索アルゴリズム」 を探しています アイディアをお貸しください
kd-tree Visualization(2) - agwの日記
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。 繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。 同じく、木構造として可視化したものは以下のようなものでした。 さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。 この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。 同様に、木構造にて1番の右側にぶら下がってい
kd-tree Visualization(1) - agwの日記
前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです １．集合Pはあらかじめ、任意の順番でソートしておける ２．点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです 集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか？ 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索する… - 人力検索
Challenge for Geeks - ita’s diary
近頃流行のフィボナッチ数列、この1000項目を誤差なく表示せよ。 64 bit int でも100項目でオーバーフローするんで簡単じゃないよ。ちなみに２００桁程度。 64 bit で100項目で足りないから、 double でもそこからは誤差が出るよ。 まあ多倍長演算ライブラリを拾ってくれば終わりだけどね。 ありがとございます： http://d.hatena.ne.jp/kokarage/20071203/p1 ウホッ！十進数多倍長！ENIAC！ http://d.hatena.ne.jp/smoking186/20071203/1196670148 オーダーLog(n)最速 第二問 では多倍長とか使わず気楽にデカい計算できる問題： 10の10乗項目を10進数で表した時の下６桁を表示せよ。 ちなみに既に周期的になってるらしく、googol (10の100乗)項目も下６桁は同じ。googo
Numerical Computation as Software
Numerical Computation as Software ソフトウェアとしての数値計算 Last Update: 2007-10-21 お断り＆言い訳 [2007-10-21] 「今後の当面の方針」について [2007-10-13] Version 1.0.3.2公開。 内容 [Bug] 表紙 目次 初めに 数値計算のための予備知識 数学ソフトウェアの現状と数値計算の役割について 数の体系，コンピュータ，浮動小数点数 浮動小数点数と丸め誤差 多倍長計算 計算量について 初等関数の計算 連立一次方程式の解法1-- 直接法 ノルム，条件数，連立一次方程式の誤差解析 連立一次方程式の解法2 -- 反復法 連立一次方程式の解法3 -- Krylov部分空間法 行列の固有値・固有ベクトル計算 非線型方程式の解法 代数方程式の解法 補間と最小二乗法 数値微分と数値積分 常微分方程式の初期値問
ORWiki
OR学会50年の歴史の中で，OR事典の編纂・改訂は通算３度目となる．いろいろな理由からOR事典編集委員会は，「OR事典」をWebに公開するという手段をとることになった．前回はCDによる出版であった． 資料編だけは「OR事典」から切り離して，OR学会の通常のホームページの中に移すことになった．これは逆瀬川浩孝委員長のアイディアである。内容の性格上，資料追加も間違いの訂正も広報委員会の責任で簡単に出来るようになる． 前回までの学会の歴史資料はそのまま残してある．今回はデータ追加作業を基本に多少の資料追加を行った．前事務局長の藤木秀夫さんには，その後の学会活動全般にわたる記録をまとめて原稿を作成してもらった．学術会議関係も藤木さんが前回の形式に習って資料原稿を作成し，FMES会長の高橋幸雄さんに目を通していただいた． 各支部から増補追加の原稿が送られてきた．Webのサンプルを見てくださいと言って
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Cryptology ePrint Archive 2009/414 - M. Finiasz and N. Sendrier "Security Bounds for the Design of Code-based Cryptosystems"
ECCC - TR09-065 - P. Voulgaris, D. Micciancio "Faster exponential time algorithms for the shortest vector problem"
ECCC - TR09-062 - D. Venturi "Lecture Notes on Algorithmic Number Theory"
Shaving Logs with Unit Cost
Cryptology ePrint Archive 2009/058 - Takakazu Satoh "On Generalization of Cheon's Algorithm"
ECCC - TR08-102
サービス終了のお知らせ
http://ja.doukaku.org/106/
SpringerLink - ISAAC 2007
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/0407-2.pdf
SpringerLink - D. J. Bernstein "The Tangent FFT " (AAECC 2007)
SpringerLink - B. A. Sethuraman, F. Oggier "Constructions of Orthonormal Lattices and Quaternion Division Algebras for Totally Real Number Fields" (AAECC 2007)
2007-11-29
Popularizing computing