Mipmap - Wikipedia
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Mipmap" – news · newspapers · books · scholar · JSTOR (June 2009) (Learn how and when to remove this message) In computer graphics, a mipmap (mip being an acronym of the Latin phrase multum in parvo, mea
B-tree and UB-tree - Scholarpedia
The B-tree is a dynamic high performance data structure to organize and manage large datasets which are stored on pseudorandom access devices like disks, (Bayer and McCreight 1972). The UB-tree is a multidimensional generalization of the B-tree. Invented in 1969, B-trees are still the prevailing data structure for indexes in relational databases and many file systems (Comer 1979), (Weikum and Voss
その13 OBBとOBBの衝突
ホーム＜ゲームつくろー！＜衝突判定編＜ OBBとOBBの衝突 3D衝突編 その13 OBBとOBBの衝突 衝突の本丸の1つ「OBBとOBB」の衝突です。大きさの違うお互いに3次元的に回転した直方体が衝突しているかどうかを調べるというのはやはり簡単ではありませんが、これができると多種多様な方面で役に立ちます。OBB同士の衝突として主流なのは「分離軸判定」と呼ばれる方法でして、ここでもそれについて見ていきます。ちょっと深呼吸してご覧下さい(^-^; ① 「分離軸」判定とは？ OBBの衝突には「分離軸」という物が登場します。これがいったい何なのか？まずは下の図をご覧下さい。 上のOBBは明らかに衝突していません。この時、両方のOBBを分ける直線が「絶対に」存在します。この直線は、ちょっと小難しい言葉で言うと分離超平面（Separating hyperplane）と呼ばれています。直線なのに平面と
scale out の技術 (in UNIX magazine, April 2009)
scale outの技術 首藤 一幸 Last-updated: January 5, 2010 注: このページの文章は以下の記事の元原稿です。 首藤一幸, "スケールアウトの技術", クラウドの技術, pp.88-101, (株)アスキー・メディアワークス, ISBN978-4-04-868064-6, 2009年 11月 6日 アスキー・メディアワークス社の 書籍紹介ページ Amazon.co.jp の ページ 首藤一幸, "スケールアウトの技術", UNIX magazine 2009年 4月号, pp.78-91, (株)アスキー・メディアワークス, 2009年 3月 18日 データベースに求められる性能を試算したところ、 十台、百台…数万台のサーバが必要になった。 クラウドを構築する側はこういう問題に直面し、解決しようとしてきた。 台数に比例した性能を引き出すこと、つまりsca
key-valueストアの基礎知識
首藤 一幸 Last-updated: January 5, 2010 注: このページの文章は Software Design 誌 2010年 2月号に掲載された以下の記事の元原稿です。 Software Design 誌編集部の了承の元に、本ウェブページに掲載しております。 首藤一幸: "key-valueストアの基礎知識", Software Design 2010年 2月号, p.14-21, (株)技術評論社, 2010年 1月 18日 クラウド、特にPaaS向けのソフトウェア開発が現実のものとなり、 そこではリレーショナルデータベースとは違ったデータベースが 勢いを増しています。 その代表であるkey-valueストアを解説します。 もくじ key-valueストアとは なぜkey-valueストアか key-valueストアの使いどころ key-valueストアとNoSQLの
PageRank In PHP
Google was a better search engine than it’s predecessors for a number of reasons, but probably the most well known one is PageRank, the algorithm for measuring the importance of a page based on what links to it. Though not necessarily that useful on its own, this kind of link analysis can be very helpful as part of a general information retrieval system, or when looking at any kind of network, suc
問題公開のあとの反応 - 人生を書き換える者すらいた。
問題を公開のあと、トラックバックやはてブでいろいろ回答や感想を見ました。 ちゃんとしたコードが書ける人が何人もいることがわかり（まあそういう人がレスポンスを出しているので当たり前か）、一安心です。本当に世間のレベルがあの求人サイトの応募者のレベルだったら、マジで日本のソフトウェア産業は滅びると思っていたからな... コメントの中で特に気になったものいくつかについて書いてみます。 ●「これは知識問題だ」という指摘 過去に似たことをやっていれば有利、というのは確かにそうです。 ただ、そういう予備知識がなくても普通に考えて実装するのに充分な時間として３時間という設定でした。というか、僕も今回の反応を見るまでA*というアルゴリズムは知らなかったよ！ また、解答は単に正解が出力できるかではなく、「コードの質」も見てます。僕もこの世界は長いので、ある程度ボリュームのあるコードを見ればその人の実力はだい
d.y.d. - 最短性をチェックする
17:31 10/01/26 言語雑談会 言語雑談会 なるものに行ってきました。 自分は主に最近のD言語の話題 [PDF] [PPTX] についてと、 最近読んだ Pattern Calculus がイマイチ心に響かなかったという話と、 これも最近読んだ Prolog で SAT ソルバ という論文が格好良すぎて卒倒しそうです、などの話題を雑談していました。 SAT の話をしていてふと突然気づいたんですが、私が今までSATソルバに落としてみたことのある問題は、 すべて割と簡単に CNF（SATソルバがそのまま食べてくれる綺麗な形式の論理式） ができあがる問題だったようです、数独とか。 任意の命題論理式をCNFに変換できる指数爆発しない方法をそういえば知らないぞ俺！としゃべってたら soutaro さんが素晴らしい解説 をして下さいました。ありがたや。 あと shinhさんの 「コンピュータ
インデックスの基礎知識
■ インデックスとは データベースの世界で、インデックス(索引)とはテーブルに格納されているデータを 高速に取り出す為の仕組みを意味します。 インデックスを適切に使用することによってSQL文の応答時間が劇的に改善 される可能性があります。 インデックスにはB-Treeインデックスをはじめ、ビットマップインデックス、 関数インデックスなどの種類がありますが、ここでは最も一般的に使われ、かつ ほとんどのDBMSでサポートされているB-Treeインデックスについて解説します。 ※ CREATE INDEX文でオプションを指定しない場合は通常B-Treeインデックスが 作成されます。 ■ B-Treeインデックスのしくみ B-Tree(Balanced Tree)インデックスは次のようなツリー状の構造になっています。 ツリーの先頭はヘッダブロックと呼ばれています。ヘッダブロックでは、キー値の 範囲
B+-Tree Indexes
Storage structure of records All records of a table in a RDBMS are stored on disk to guarantee their permanence in case of software and/or hardware failures. The records in a table are organized in files that are managed by the DBMS -- not by the OS. Whenever a query is submitted to the RDBMS, the query is processed and the records in the relational database table(s) that satisfy the query are ret
A*アルゴリズムまとめ - octech
数年ぶりにA*アルゴリズムを実装したので、まとめなおしておきます。何回かじっくり読むとようやく理解が出来てきました。基本的にそんなに難しくないアルゴリズムです。 概要 「A*アルゴリズム」は、A-Star（エースター）と読み、パス探索アルゴリズムの一つです。 ノードネットワーク上にスタート地点とゴール地点を結ぶパスが存在すれば、最悪でもそのパスの存在を確認できるアルゴリズムです（見落とすことがない）。 内容はシンプルな再帰計算で、コスト計算の部分にヒューリスティックと呼ばれるパラメータがあり、その算出アルゴリズムを変更することにより、各種アプリの状況に応じた高速化と最適化が望めます。 2007-07-16 修正 「A* - Wikipedia」の擬似コードを見ていたら、自分の書いたコードでは最適なルートを計算しない可能性があることが分かりましたので修正しました。下記のC++的擬似コード内で
経路探索アルゴリズムA* - gan2 の Ruby 勉強日記
RTSや防衛ゲームでよく見るキャラが障害物を避けて通る移動方法って どういうアルゴリズムなんだろう？と気になったのでちょっと調べてみた。 そしたら、たぶんこれだっていうのが見つかったのでメモしておきます。 その名もA*(エースターって読むらしい)。 自分でFlash使って実装してみたい。 以下は参考ページ。 A*（A-star：エースター）探索アルゴリズム 概要の説明はここがすごく分かりやすい。WikipediaのA*の項を見たときは( ゜д゜)ポカーンって感じだったけど、ここの説明を読んだらすっきりした。 A*アルゴリズム、ActionScriptで。 Flashでの実装。ソース(コメントつき)あり。これを読んで勉強かなぁ。 http://torus.jp/memo/x200606/shibuya-js.rd.htmlと合わせて読むのがいいかも。 2007-07-12 C++での実装。ソ
A* - Wikipedia
A*探索アルゴリズム A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの[1]。h はヒューリスティック関数と呼ばれる。 A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 を使うことができ、この値は道に沿った実際の距離のおおまかな予
11．動的計画法と擬多項式時間アルゴリズム
内容 スライド 1 11．動的計画法と擬多項式時間アルゴリズム スライド 2 これまでは、主に、「問題がいかに難しいか」を理論的に証明する方法について学んで... スライド 3 １１−１．部分和問題（SUBSET SUM Problem) スライド 4 インスタンス例 スライド 5 入力サイズ スライド 6 部分和問題の指数時間アルゴリズム スライド 7 したがって、次のようなアルゴリズムが得られる。 スライド 8 このアルゴリズムの計算量は、1-3を 回繰り返しており、 ２．において... スライド 9 部分和問題の擬多項式時間アルゴリズム スライド 10 方針 スライド 11 表の概形 （アルゴリズムの基礎にあたる。） スライド 12 要素 に注目した表の更新。 スライド 13 要素 に注目した表の更新。 スライド 14 要素
足し算引き算で10を作るゲームと部分和問題、DP - 素人がプログラミングを勉強していたブログ
切符の問題 切符の裏に印刷してある4桁の数字を4つの数字と考えて、足し算と引き算だけで10を作るゲームの解き方。 例えば、1,2,3,4の場合は1+2+3+4=10。 プログラム的には、 prob([1,2,3,4]); // [{plus: [1,2,3,4], minus: []}] こんな感じに返ってくるようにしたい。 まず、2,4,5,7から10を作る場合。2+4+5+7=18であるので、上記の式のいくつかの符号を-にすればいいことが分かる。一つの数字を引くと、18を出す時に最初に足した分と、今引こうとしている分の2つ引かなければならないから、逆算して、(18-10)/2=4を引けばいいと分かる。 この場合、合計が4になる組合せは、4そのものしかないから、2-4+5+7=10、が答えと分かる。 (合計-10)/2が引く数の合計で、それ以外が足す数である。2で割っているので、全部の数
第1回 直線の幾何 | gihyo.jp
計算幾何学とは 小学生や中学生の頃、算数や数学の授業で、台形の面積を求めたり、直線の方程式を解いたりした記憶が誰にでもあることでしょう。計算幾何学とは、コンピュータサイエンスの立場から、こうした「図形」に関するアルゴリズムを研究する学問です。計算幾何学は、今日のコンピュータグラフィックスやCADの発展においてきわめて重要な役割を担っているほか、地理情報システム（GIS）やロボット工学といった数多くの分野に応用されています。 本連載では、ブログ可視化サイトの「Blogopolis」で採用されている計算幾何的アプローチを引き合いに出しつつ、Javaプログラムでアルゴリズムを実装しながら、計算幾何学の初歩を学びます。 Blogopolisとボロノイ図 Blogopolisは筆者の開発したWebサイトで、主に日本国内で開設された25万件以上のブログを解析し、「仮想都市景観」として視覚化したサービ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Summed-Area Tables And Their Application to Dynamic Glossy Environment Reflections
ページランクとは(PageRank)
http://www.o440.info/developing/findpath/
http://next1.msi.sk.shibaura-it.ac.jp/MULTIMEDIA/numeanal2/numeanal2.html