Lx=d: SundayResearch (Japanese version)

CACM (Vol.55, No.9)に 2 つほど面白い話があったので紹介する． 1. DieHard 多くの C++ で書かれたソフトウェアのバグは多少の buffer overflow である．そこで memory allocator が random に allocation のサイズを拡大する．また，allocator は heap の allocation を randomize する．すると，この種のバグはdeterministic ではなく，Heisenberg bug になる． これは devloper からすると悪夢である．バグが再現できたりできなかったりするので，それを修正するのが困難になるからだ． しかし，ユーザからすれば，バグは起きないこともある．クラッシュしたら再起動すれば，運が良ければクラッシュしないかもしれない． この論文は DieHard というタイトルで Microsoft research から入手できる．しかしバグを隠すことは Seatbelts や Airbags のアナロジではないと個人的には思う．面白いアイデアとは思うが，プログラマとしては deterministic なバグの方が好みであるし，できればバグは隠すよりも直したいと思う． http://queue.acm.org/detail.cfm?id=2333133 2. CriptDB 暗号化したデータをサーチしたり，圧縮したデータを圧縮したまま処理する方法というのがあると聞いていったいどうするのだろうと思ったことがある．詳細は私にはわからないが，一方向関数でも対応がある程度明らかなものでは可能のようだ．たとえば，英語の Databse があるとする，これをドイツ語に翻訳するのが暗号化と思えば，ドイツ語の単語でサーチができる．たとえば，山(Mountain)という単語を探そうとすると，このキーワードを暗号化した Bergによって探索する．話はそんなに単純ではないが，原理はこれに類したものであるようだ． http://dl.acm.org/citation.cfm?doid=2330667.2330691

この話は マルコフ行列の中の著者達の番外編である．鉄道ファンとグラフ理論の関係は何かという話である． ( English version ) 同僚の Dietger がグラフの全ての edge をたどる問題を知っているかと聞くので，Hamiltonian path のことかと答えると， Hamiltonian path は全ての nodeを一度通るもので，そうではなく全ての edge を通るものだということだった． 私はVertex と Edge の Dual を考えれば良いではないかと言ったのだが，Triangle mesh ではVertex と Face は Dual になるが，Edge はそうではない．(図1, 2, 3)考えてみると，点は辺を介して接続され，面も辺を介して接続されている．では辺は何を介して接続されているのだろうか．面か点である．面と点の接続関係は辺によるものなので，辺はある意味この面・点とは異なる．だから面と点を入れかえることはまだできるが，辺は何かと入れかえられないと考えた． Figure 1: Duality of face and vertex: faces to a dual grah. Figure 2: Duality of face and vertex: a dual graph to faces. Figure 3: Edge's duality? これはどんな問題を考えているのかと尋ねたところ，彼の友人は鉄道の線路の管理をしているということであった．つまり線路を定期的に全て検査しなくてはならない．効率良く線路を全てまわるのはどうすれば良いのかという問題をグラフの問題として考えたものである．結局，これは 中国人の郵便配達問題 と呼ばれていることがわかった．中国人の数学者(Mei Ko Kuan)がこの問題に関して研究していたことにちなむらしい．これは Euler path 問題，つまり一筆書き問題とかかわりが深い． 私は昔， PTT (Programming tools and techniques) という集まりでこれに類する話を聞いたことがある．この会はソフトウェア関係の会であるが，鉄道好きの人も多数いらした．葛西さんという方が，この会で発表したのは，最長の片道切...

数学では番号だけ考えていれば良いが，実際にはこの番号は何かに対応している．何かとは区別さえできればなんでもよいのであるが，具体的な例を示した方がイメージがわくと思うので，2つほど例を示そう． 例1:点が著者を示す場合 以下の4人の著者を考える． William Shakespeare Lewis Carroll Raymond Smullyan Martin Gardner これらの著者がそれぞれどのような影響を受けたかは様々な見解があるだろうが，とりあえず，Shakespeare は Carroll に影響を与え，Carroll は Smullyan とGardner に影響を与えたとしよう．そのグラフは図 6のようになるだろう． Figure 6. Graph example 1. Each node is an English author. 例2:点が駅名を示す場合 点が駅名を示す場合を考える． Weinmeisterstr Alexanderplatz Hackescher Markt Jannowitzbruecke これらの駅間が隣あっている場合，それらの駅には関係があるものとして辺で接続しよう．するとそのグラフは図 7 のようになる．ところでBerlin の市内電車はよく工事をしていて，ある区間が不通であったり，困ったことに一方通行しかない場合があったりする．一方通行の場合には，グラフは有向グラフとなるであろう． Figure 7. Graph example 2. Each node is a train station. ここで一つ注意して欲しい．点の例が何であっても，これらのグラフは同じ形をしている．同じ形をしているグラフは全て数学では同じであって区別しない．つまり，図 4, 5, 6, 7 ( 図4,5 は以前の blog を参照 )は全て同じグラフである．数学ではこの形のグラフから何が言えるかということに関して考える． 著者と駅名が同じ形で示されたということは奇妙なことかもしれない．しかし数学は世界からパターンをみつけだし，それらに共通のことを考える学問である．そして私はいつも驚くのであるが，この世界には同じようなパターンが出現することがいくつもある．新しく出会った...

モデルビュー行列からカメラのパラメータを計算する． modelview matrix は model に作用する matrix も含んでいるので，シーンがスケール，移動，回転されていたりするとその効果が含まれている．これをmatrixの情報のみを使って分離する方法はない．そこで，ここではシーンに対するtransformation matrix は Identity matrix, つまり全てはカメラの効果としてカメラのパラメータを抽出する．もし，シーンに対する効果が分離されているようなレンダラと OpenGL レンダラを併用する場合には，この transformationmatrix を undo する必要がある． modelview matrix は以下のような成分になっている．この成分の詳しいことに関しては私の以前の blog( http://shitohichiumaya.blogspot.de/2011/01/what-matrix-glulookat-generates-1.html )を参照のこと． \begin{eqnarray*}  \left[   \begin{array}{cccc}    x_x & y_x & z_x & 0 \\    x_y & y_y & z_y & 0 \\    x_z & y_z & z_z & 0 \\    -(\vec{x} \cdot \vec{e}) &     -(\vec{y} \cdot \vec{e}) &     -(\vec{z} \cdot \vec{e}) & 1 \\   \end{array}  \right] \end{eqnarray*} 4行を \(a,b,c\)で置きかえるとこの行列は以下のように書ける． \begin{eqnarray*}  \left[   \begin{array}{cccc}    x_x & y_x & ...

Abstract この話はコンピュータグラフィクスとプログラミングの話である．以前 gluLookat 関数の作る Matrix に関して書いた( http://shitohichiumaya.blogspot.de/2011/01/what-matrix-glulookat-generates-1.html )．この記事を書いた動機はOpenGLとは独立したレンダラ(ray tracer など)を書いており，しかし OpenGL と画像をoverlay したいということがあったからである．そういう意味では特殊な話であるがこの記事は意外に参照されている．今回，我々の顧客が特殊なシステムを利用していて，この逆演算をする必要がでてきた．つまり OpenGL のProjection/Modelview matrix からカメラのパラメータを知りたいという要求である．これについてここに書いておく． はじめに 世の中にはいろいろな可視化システムがあるもので，可視化システムのカメラのパラメータが不明，つまりカメラがどこにあるのかわからない，というものがあるようだ．話を聞くと実は OpenGL に依存した大規模なシステムで，あるソフトウェアのレイヤーではカメラのパラメータがわからないという状況のようだ．しかし，OpenGL を使っているので，projection matrix と model view matrix にはアクセスできるということである．そこでこれらの matrix からカメラのパラメータを抽出する方法というものを尋ねられた． これはちょっと特殊な状況であると思うが，OpenGL の Projection/Modelviewmatrix が与えられた場合に，カメラのパラメータを抽出するにはどうするかというパズルとして考えれば面白いかもしれないと思い，ここに blog として記す． パースペクティブ行列からカメラのパラメータを計算する． まずは Perspective matrix に関連したパラメータを取りだそう． gluPerspective 関数は以下のような関数である．詳しくは OpenGL の manual を参照のこと． void gluPerspective(GLdouble fovyd,  GLdouble a...

8 歳の T 君が 7 について学んでいる．7 はどんな加算によって作られるかというものである．ここで利用している教材の一つは図 1 にあるような Zahlenhaus というものである．2つの部屋があり，それぞれに何人かがいる．全体で何人が一つの家にいますか? ということで加算というものを考えるものである． Figure 1. Zahlenhaus: 7 = 4 + 3 Figure 2. Zahlenhaus: Questions そこには，  7 = 3 + ?  7 = 4 + ? のような問題(図2)があり，? を埋めるのである．T 君は上記の質問にはまったく問題なく答える． しかし，次の質問がわからないという． 7 = 0 + ? ところで，学ぶ時，何がわからないのかをわかっているというのはとてもやりやすい．私自身，数学の本を読んでいてどこでわからなくなったのかをみつけるのに苦労することがある．そしてわからない部分がわかれば道が見えることが多い．どこがわからないかわからないと，どこまで本を戻ればいいのか見当がつかないからである． さて，Zahlenhaus に戻ろう．左の部屋には誰もいない．右の部屋には何人いる?と尋ねると，2 + 5 人とか3 + 4 人という．私はこれには困った．つまり，T 君は 7 = 0 + 2 + 5 と答えたのである，これは数学的にはまったく正しい．一つの部屋をまとめて数えなくてはいけない理由は特にないし，そういう仮定を明確に言ったわけではない．だいたい最初に 7 はいくつといくつ? というように聞いているのは練習の意味が強い．7 は 7 である．と答えて間違いはない．これはゲームだと思ってもらった方がいいかもしれない． しかし，それぞれの部屋に一つだけ数字を割り当てるという暗黙のルールによって 7 = 0 + 2 + 5 は間違いとされる．Zahlenhaus には部屋が 3つないからである．もし，Zahlenhaus に部屋が 3つあれば，これは正しくなる．しかし，ある計算が部屋の数で間違いだったり正しかったりするのは逆に混乱するのではないだろうか? 私はよくチャールズ・ドジソン(ペンネーム: ルイス・キャロル)の本「鏡の国のアリ...