|
怒りに取り憑かれていた．なにかを書くことは沈静化に少しは役立つ．しかしゴールデンウイークはまともな研究はできなかった． けれど Revise before review になっている論文をどう改訂するかという方針はできた．少し安心．締め切りをちゃんと調べてみた．メールには書いてなかったけど，投稿システムには 6 月はじめとあった．そういうことなんだろう． 仕事が進まないので，アルゴリズムの解説書なんかを読んだ．ハノイの塔の問題を解く Ruby プログラムを動かしてみた．たった10行ちょっとだけど，ちゃんと動いた．
再帰，すごいじゃないか！ しかしこんなことで感動してよいのか？ 素人のボクは感動してよいだろう．だってプロの浅野哲夫が『アルゴリズム・サイエンス：入口からの超入門』(2006) の「再帰の威力」で以下のように独白しているから (148ページ):
Mac OS X Leopard の最新機能は意外と便利．
追記 (5/14/08). Spaces の説明を修正．  |
 |
|
追加キーワード: グラフ理論，ネットワーク最適化，展開形ゲーム，ゲームツリー，可視化，ヴィジュアル，グラフィックス． 前回記事にある「油分け問題」に続き，今回は最短路問題を解くダイクストラ法 (Dijkstra 法) の Ruby プログラミングを担当科目の課題にした．こちらはアルゴリズム自体はその疑似コードとともに授業で学んだので，あとは Ruby で表現する問題だ (受講生によればそこがむずかしい)．たとえば Wikipedia にある疑似コードを下敷きにしていいと受講生には伝えた． 自分でもプログラムを書いてみた．路線探索プログラムの本質的な部分が初心者にも書けたということであり，なかなか素晴らしい．(ちなみに路線探索では2番目以降に表示する経路をどうするかがむずかしいらしい．←こちらのサイトにはダイクストラ法の図解もある．) だが，なにかもの足りない．いや，将来「もの足りない」と言う学生が出てきそうな気がする．そう，なにもかも文字として処理されるのだ！ つまり重み付き枝たち (たとえば距離あるいは重み 10 の枝 (s, 1) を [:s,1,10] と書く) を要素とする配列と出発点 (たとえば :s と書く) を持つインスタンス problem を作れば，あとは problem.shortest_path_to(v) とやることで任意の点 v への最短路とその距離が配列として返って来る．図がどこにも現れないのである． そういう学生には，「心配はいらない．こういうグラフをテキストデータから描いてくれるプログラムは存在するはずだ」と答えるつもりだった．グラフというのは点と点のむすびつきの情報だけで決まるものであり，画像としての表現はその本質ではないからだ．把握のしやすさや見栄えを別にすれば，データを画像としてではなくテキストデータとして保持するのが本質的なやり方と言える．たぶん Mathematica あたりもそんな描画機能を備えているだろう．そんなところにたまたま飛び込んで来たのが，こちらの解説記事「ITpro【特選フリーソフト】テキストをグラフに変換 Graphviz」だ．ふむふむ，Graphviz ってのがあるんだね．ということで，Mac OS X edition of Graphviz を試してみた． 読者は「平面グラフ (点の位置をうまく選べば，辺が交差しないように平面上に描けるグラフ) をじっさいに辺が交差しないように描いてくれるんだろうか？」などの興味を持つかもしれない．平面グラフかどうかは理論的にはクラトウスキーの定理で判定できるが，このソフトがその判定機能を備えているかどうかは知らない．デモンストレーションを一見したところ，交差する枝が少ない気はするので，それに近い機能を利用しているんじゃないかとは思うが． 個人的には，これが家系図に使えるかどうかに関心がある．(ちょっと試したところ，残念ながら日本語が文字化けしたけど．) じっさい，同じ疑問をもったひとはいたようで，その返答として Graphviz で家系図を描いた例はあった．ポイントは親子関係を有向枝で表し，男性のノードを長方形で女性のノードを楕円で表すことにより区別することだろう．ノードを形で区別することは (ノードにノード名と異なるラベルをつける，あるいはノード名の付け方に規則を導入するという意味で多少)《グラフ》の定義を逸脱しているが (追記参照)，こうすることで「父・母・子」の3項関係を表すことはできる．ただし，このままでは兄弟の順番は (ラベルなしでは) 表現できないし，父母と兄弟の間の枝を交差させず直線で描こうとすれば (リマーク 1)，たぶん (先祖を子孫より位置的に上に描くといった) 階層構造は崩れる．じっさい，さっきの例のコードを描画してみたところ，根っこ以外のどのノードも出次数が 1，つまり子供がひとりだけということになっていた．すなわちこの家系図はある個人の直系尊属のみを記録したものであり，兄弟や傍系の存在に起因する複雑さを回避したものだった．
というわけで，Graphviz で家系図を作るとすれば，親子間の枝が複雑に交差するのは許す一方で，階層構造の表現を優先するのがよさそうだ．ここまでできるのだから，一組の夫婦にかんする親子関係の枝をまとめる方法 (つまり完全2部グラフ K2,n のすっきりした描き方) を提供してくれてもいい気はするけどね．[追記 2 参照] 追記 1 (1/26/2008). リマーク 1 などに若干手を入れた． 「お前は「父・母・子」の3項関係にこだわり過ぎている．家系図を描く上で重要なのはだれとだれが子供の親であるかであって，そのどちらが父親でどちらが母親かということではない．あくまでも親子関係という2項関係が基本だ．数学でも，2項関係の理論を多項関係のそれに拡張して本質的なちがいがあったか？ よき振る舞いをする多項関係は，2項関係に一定の条件を加えたものにすぎないのではないか？ お前の専門とする社会選択でも，《選好》という2項関係をもとにした理論と，多数からなにかを選ぶ選択関数という多項関係をもとにした理論とで大きなちがいがあったか？」とのお告げがあった． アダムとイブの関係を基本にして「生めよ，ふえよ，地に満ちよ」と祝福した神のお告げにしては意外だが，そこは問わないことにする．なるほど，《親子関係》を基本と考えて，それぞれのノードが親をふたつ持つ (入次数が2である) ことだけ要求すれば，たしかにどちらが父でどちらが母かは系図作成上重要ではないかもしれない．親の一方に「男」と，もう一方に「女」とラベルをつけることで満足ならば，3項関係を持ち出すまでもない．このばあい，親子関係のグラフは《グラフ》の定義を逸脱してはいない． 同様のことは「2部グラフ」と呼ばれるグラフでも起こる．2部グラフとはたとえば互いにセックスをしたことのある男女に枝を引くようなグラフであり，もちろん《グラフ》の定義を逸脱していない．ホモセクシャルを考慮外にすれば，男同士あるいは女同士のあいだには枝がない．つまりそれぞれの点に「男」あるいは「女」とラベルをつけられるようなグラフだ．その際，男性である太朗に「女」のラベルをつけたならば，太朗とセックスしたことのある花子には「男」のラベルをつけることになる．グラフへの追加的な構造として「男集合」「女集合」といたラベルのついた集合を導入しないかぎり，性別の逆転はありうる． 追記 2 (2/7/2008). 「Graphviz で家系図を作るとすれば，親子間の枝が複雑に交差するのは許す一方で」と書いたが，もちろん下図のように婚姻関係などを表す点をダミーとして入れれば枝の交差はなくせる．人間を表さない点が導入されるとか，入力ファイルの可読性が下がる (上がる?) といった問題を除けば，現実的な描き方かもしれない．
 |
|
|
|
年明けには Ruby プログラミングをやった．去年の夏に「プログラミング教育用なんかにもいいかも」と書いたことのある ruby だけど，いま教えているオペレーションズ・リサーチの授業でじっさい ruby プログラミングをやることにした．プログラミングの経験がないという受講生が「プログラミングをやってみるいい機会」と意欲を見せたため，「じゃあ，すぐにマスターできる言語で行こう」と，急遽予定に組み入れた． といってもボクもほとんど知らない言語だ (というか，プログラミング自体の経験も浅い) ．まずはこちらの文献集にあった，まつもとの「rubyユーザガイド」 (ちょっと古い; また，初心者である自分にはあまり分かりやすくなかった) と Chris Pine の「プログラミング入門: Rubyを使って」(大部分は初心者でも読めるだろうけど，9章の後半と10章はむずかしそう) をざっと読んだ．プログラミングをはじめてからは，その文献集の「入門編」の「サイト」にある情報や，「オブジェクト指向スクリプト言語 Ruby リファレンスマニュアル」その他を参照した． プログラミングに出した課題はこんなタイプの問題だ: 「カップ 0, 1, 2 はそれぞれ 10, 7, 3 の容量を持つ．最初は容量10のカップに水が満杯の状態 [10, 0, 0] である．カップ i から j への水の移し替えを繰り返して，目標である [5, 5, 0]を実現したい．」この例にかんするかぎりは，9段階の移し替えで目標が達成できることが，すべての場合を網羅的に調べることで手作業で確認できる． (上述の科目で少し学ぶ) グラフ理論を知っていれば，この種の問題をプログラムで扱えるように表現するのは簡単だろう．アルゴリズムを考えることもたやすい． それでもはじめての言語というのはいろいろと戸惑うものだ．ありがちなミスのパタンは，マニュアルと悪戦苦闘したり試行錯誤を繰り返すうちにだいたい分かって来た．で，できあがった最初のプログラムは，9段階の移し替えを実行するだけで 5 時間もかかり，10 段階以上は結果を出せなかった．そんなバカな！ 「オブジェクト指向でプログラムを書いたのが悪かったんだろうか？」「再帰で関数を定義したのが悪かったんだろうか？」などと疑った．Mac OS X にはじめからインストールしてあった ruby がたまたま当たりが悪いバージョンなのかもしれないと思って，最新安定版 1.8.6 に入れ替えたり，クリスマスにリリースされたばかりの「高速」不安定版 1.9.0 を (一年近く触れていなかった) Windows PC にインストールしたりもした．だがそれらの対処法はいずれも見当違いだった．
では，なにがプログラムをそんなに遅くしていたのか？ どうやら関数の相互参照であるようだ．たとえば history(t) という関数を定義するのに history(t-1) と obtained(t-1) を参照する一方で，obtained(t-1) を定義するのに obtained(t-2) と history(t-1) を参照するようになっていた．数学的には問題はなさそうだが，おそらくプログラム的には問題になるんだろうな．history(t) の定義のなかに使われていた関数 obtained(t-1) を単なるローカル変数に置き換えた．するとそれまで5時間かかってもできなかった計算が，1秒程度でできるようになった！ やれやれ．
それにしても「おまじない」の類いをほとんど記述せずにプログラムが書けるのは気持ちいい．できたプログラムは普通に書くアルゴリズムよりもむしろ簡単かも．たとえば (?) 上記の水移し問題 (油移し問題) のインスタンスである abura にたいする結果を表示する---より具体的にはその履歴 history(t) を t = 0 から t = 12 まで表示する---には，以下のように書けばいい:
追記 (1/10/2008). あまりにも単純すぎてポイントが伝わらなかった例を差し替えた．以下は修正前の記述．「プログラムでは x = x + 1 と書いて，右辺の値の左辺の変数への代入を表すけど，数学ではふつうそうはやらない．わざわざ添字をつけて xt = xt-1 + 1 とするか，関数にして x(t) = x(t-1) + 1 とやりたくなるわけだ．(この例は簡単すぎるので説得力ないけど，もっとむずかしくなると添字をつけて何段階目の更新かというのをはっきりさせた方が分かりやすくなる例は少なくないはずだ．)」  |
|
|
|
オブジェクト指向言語 Ruby についてちょっと調べてみた．代表的なオブジェクト指向言語である Java とちがって，コンパイルなしで使えるのが魅力のひとつだ．(もっとも最近は掌田津耶乃の記事「コンパイル不要Javaの時代がやってくる！？」のような展開もあるみたいだけど．) Ruby を使うと，プログラムが簡単になるとかいろいろいい点はあるようだ (熱烈な支持者が多いようなので，そちらを参照)．プログラミング教育用なんかにもいいかも．試しに以前の記事「中学受験問題を無理やり解く」で書いたプログラムを Ruby 用に書き直してみた．(逆引きその他の参考書を引きつつ，文法知識ほぼゼロで作成．Java 用のファイルをもとにしたため，インデントにスペースとタブが混じるなどの不統一は残っている．) コードはアルゴリズムをほとんどそのまま書いた感じだ． コードから分かるように，型を指定した変数宣言も不要．じつは上述の記事で java コードを書いたとき変数の型に関して問題が起こり，数値型を double にしたり long にしたりして問題を回避する必要があった．今回の ruby では，その種の問題は起きなかった．どうやら数値が大きくなったら，任意の長さの整数を扱える型に自動的に移るようだ．Ruby の紹介ではあまり強調されていないみたいだけど，個人的には重要なメリットと思う．  |
|
|
|
フリーの数値計算プログラム Octave は Matlab の代表的なクローンだ．Mac OS X で Octave を利用するためのもっとも簡単な方法を紹介する．
まず，こちらの数値計算プログラムの Mac OS X 用バイナリを置いたサイトからコンパイル済みのプログラムを入手する．画面上部の水色バーの Octave をクリックすれば該当場所に飛ぶ． Intel Mac のばあい octave-intel-bin.tar.gz をクリックすると，ダウンロードしたファイルは勝手に解凍をはじめる (設定によるが)．そのなかから octave-intel-bin.tarをホームフォルダに移して，他に作成されたファイルとフォルダは捨てる． 次に Terminal を起動して上のサイトに書いてある通り (ただしファイル名を修正) に 行列計算のやり方はたとえばこちらの操作例やこちらのコマンド集を見れば十分だろう．さらに詳しくはこういうマニュアルもある． とっても簡単!  |
|
|
|
LaTeX での論文作成において，theorem-like environment は定理や命題などを表現するのに便利だ．ただし英語のばあい，通常は中身がイタリック体になってしまう．特に強調するわけでもない Remark や Example をイタリック体で表記されてもうれしくない． このようなときは Frank Mittelbach の theorem package を利用するとよい．LaTeX が使える環境なら利用できるはずだ．たとえばプリアンブルで以下のように宣言すれば，Definition, Example, Remark の中身の書体が本文と同じになる一方で，Theorem などの書体は通常の定理環境のものになる．(Theorem, Proposition, Corollary, Lemma に同系列の番号が振られるというのは指摘するまでもないだろう．)
theorem パッケージの説明は (システムのどこかにあるはずの Mittelbach のオリジナル解説以外に)『好き好き LaTeX2e 初級編』にある．(上記のように Theorem と Definition といった環境ごとに書体を変えられる点の説明は不十分だが．) 問題点
リマーク．theorem パッケージを利用する以前は，以下のような環境定義をもちいていた．参考まで．
|
|
|
|
| ホーム |
|