My Daily Programming Life...

最短経路の本



「最短経路の本」R.ブランデンベルク P.グリッツマン シュプリンガー・ジャパン株式会社

を読んだ。

基本的にはグラフ理論を現実的な側面から解説している本。レナという女の子が、コンピュータと話をしながら、グラフ理論やアルゴリズムについて学んでいくというストーリー。

最短経路
アルゴリズムの時間計算
最小全域木
オイラーグラフ
マッチング問題
中国人郵便配達問題
ハミルトングラフ
巡回セールスマン問題

といった内容を、図などを交えて、対話形式の話を読みながら学べる。
教科書のような作りではなく、章が比較的短くまとめられていて、しかも一つ一つの章の内容も難しすぎないため、非常に読みやすい。しかもいつの間にか一通りのグラフ理論の概要は理解できるようになっている(と思われる。)

グラフ理論ばかりではなく、チューリングや、オイラーなどの人物の逸話なども載っていて飽きない作りになっているし、何よりそれによって頭が疲れないようになっている。頭を使って考える部分と、少し休んで読める部分が交互にあるため、また次の章を読むときにも、エネルギーが残っている。

ただし、一つ一つ理解するには、それなりに時間がかかる部分もある。たださっと読んだだけでは理解できない部分もあり、頭を使って読み進めないと、次の瞬間には何を言っているのかわからなくなるようなことも多い。そういう意味では、教科書を進めるときのように、1ページ1ページ確実に理解して前に進むべき本だと思う。

主人公のレナは、数学が苦手な女の子の役割だが、少なくとも数学がそれなりに得意だった僕よりもよっぽど数学ができるという点はちょっと・・・と思うところはある。なので、まったく数学が苦手な人にはちょっと難しいかもしれない個所もある。(数学的に難しいというより、その場で自分で論理的に考えて、そこで言われていることを理解する力が必要になる。)

この本を読んだ後に、グラフ理論の教科書的なものを読んでいるが、この本を読んだ後で、教科書を読むのは非常に効率が良いと思う。教科書は数学的に正確な言葉で書かれていたりして、概要をつかむには、一つ一つを理解するのに時間がかかる。一方で概要が分かっていると、教科書はその概要を数学的に正しく書くとこうなるという説明として読めるので、頭の中のイメージをすぐにその式につなげることができる。式からイメージをつくるより、今あるイメージが式の中でどう表現されているかを考えるほうが楽だと思うし、この本はよい入門書になると思う。

最後の3章(全体の1割程度)は僕には難しすぎて理解できなかった。というより、個人的にはちょっと説明が雑すぎるんじゃないだろうかと思うところもある。おそらくこれですべてを理解してもらおうと思っていないというところはあると思うが、理解できない言葉(「1-木」ってなに?)ができたりして、説明されているようだけれど、理解できない。というわけで、最後の3章は読んでいない。

全体として、現実的な問題を解決するということを題材にして、説明されているので、その意味もはっきりしていて目的をもって読める。グラフ理論がどんなものか知りたい人、アルゴリズムに興味がある人は読んで損はない本だと思う。

Ubuntuでキーボードの配置変更方法

環境はUbuntu 10.4

xmodmapを使えばキーを入れ替えられる。

設定ファイルを指定して
> xmodmap file

とコマンドを入れればよい。設定ファイルの中身は、たとえば、CtrlとCapsを入れ替えるなら


remove Lock = Caps_Lock
remove Control = Control_L
keysym Control_L = Caps_Lock
keysym Caps_Lock = Control_L
add Lock = Caps_Lock
add Control = Control_L

と書かれた「file」を用意すればよい。ただし、gnomeの場愛、xmodmapを使わなくても入れ替える機能がある。「システム」->「設定」->「キーボード」->「レイアウト」->「オプション」->「Ctrlキーの位置」といくことで、Capsとの入れ替えを選べる。なので実際にxmodmapの使い方は、この「オプション」のリストに内容なキーの入れ替えを行いたい場合に使うのが良さそう。

今回は、日本語キーボードの「無変換」を「Windowsキー」と同じ挙動をさせようとした。Gnomeの場愛「Windowsキー」は「Super」というKeysym(キーの名前)になっているようで、これを使うといろいろショートカットが設定できるで、スペースのすぐ左にある「無変換」をこのキーとして利用できるのは便利だ(それに、個人的にWindowsでもそのような設定にしているからそうしたい。)

設定ファイルには
keysym Muhenkan = Super_L
とした。(各キーがどのようなコードだったりKeysymに割り当てられているかはxevコマンドで確かめられる。)
設定ファイルの書き方はここが詳しい

さて、しかし、これだと毎回ログインの度にこのコマンドを行わなくてはいけない。
Ubuntuの場合ログイン時に勝手にこのxmodmapを読み込んでくれるようになっている(UbuntuというよりGnomeの機能か)
ホームディレクトリに「.Xmodmap」というファイルを作成して置いておく。その中にキー設定を書いておけばよい。
このファイルを作って再ログインすると、下のようなダイアログが表示される。


「.Xmodmap」を選択して「読み込む」をクリックして、自動的に読み込まれるようにする。「次回からこのメッセージを表示しない」をチェックしておけば、それいこう「.Xmodmap」がログイン時に自動的に読み込まれる。あとは好きなようにこのファイルを設定すればよい。

ところで、このダイアログでの設定はどこに保存されているんだろうか、と疑問になり、それも調べた。実は、自分でやっているときに、このダイアログが表示されて何も読み込まない設定にして、OKを押してしまった。それ以降ダイアログは出ないし、どこで読み込む設定をしてよいのか結構時間がかかった。

この設定にはgconf-editorを使う。ターミナルから、そのまま起動すれば出てくる。


Windowsでいうならレジストリみたいな感じだろうか。ツリーから
「desktop」->「gnome」->「peripherarls」->「keyboard」->「general」
を選んで、その中の二つの値を見る。
「known_file_list」と「update_handlers」の二つ。
「update_handlers」は起動時に読み込むファイル名を書けばいいらしい。リストなので複数のファイル名を書き込める。あとから、他にも読み込むファイルを追加したい場合にはここに書けばよい。

「known_file_list」はおそらく先ほどのダイアログに出てくるすべてのファイルのリストだと思う。このリストを空にすると、また起動時に読み込むファイルを選択するダイアログが表示されるようになる。

これで、読み込むファイルを変更したくなったりしてもまたできる。

screenコマンドでVisual Bellを無効にしたいとき

最近Ubuntuを使い始めていろいろやっている。Linux自体まともにクライアントとして使うのは初めてで、いろいろ設定して使いやすくしている中で、問題がでてくるので、解決したものからブログに。

環境はUbuntu 10.4

screenコマンドは一つのターミナルで複数の対話シェルを使えるようにするようなものだけれど、切り替えたときから、VisualBellが有効になってしまっていて、ちょっと間違えると画面がチカチカしてよくない。

最終的に行き着いた結論は
$HOME/.screenrc
を作成しその中に
vbell off
と書いておくこと。これでscreen起動時にこれを読み込んでVisualBellをオフにしてくれる。


(2010/10/23 .screen -> .screenrc に修正。間違ってた。)

暗号技術入門



「暗号技術入門」結城浩 ソフトバンク クリエイティブ株式会社
を読んだ。

対称暗号
公開鍵暗号
ハッシュ関数
メッセージ認証コード
デジタル署名
疑似乱数生成

これらを題材に順番に説明して、現在の暗号技術のなかでどのように使われているかを説明している。

どのように使われているか、どのような意味を持つか、なぜそれを使うのか、またこの技術で解決できない問題は何なのかということを順番にわかりやすく説明している。
暗号の作成者、実装者視点ではなく、利用者視点で書かれている。
という意味で、自分でプログラミングで直接暗号を使う必要はないけど、なんだかいまいち暗号通信がどうなっているのかよく分からない、HTTPSがどうして安全なのかよく分からない、そもそも安全なのか不安だという利用者向けの入門書だった。

個人的にはもう少し暗号技術その物の導入を期待したので、ちょっと物足りない感じだった。公開鍵暗号、デジタル書名の使われ方が分かっている人であれば、得るものは多くはないかもしれない。もう少し暗号そもののの説明が欲しい感じがした。ブロック暗号の話はかかれているが、ストリーム暗号は言葉が出てきているだけで具体的な説明はなかったりもする。

暗号技術全体の像を掴む上ではいいかもしれない。ただし、ちょっとページ数をかけすぎている気がする。それだけ丁寧だということはあるけれど。

もう少し簡単に、全体像を掴みたい人は「マスタリングTCP/IP SSL/TLS編」がよいと思う。プロトコルに関する本ではあるけど、最初に基本的な暗号全体に関する説明がある。これを読んで、もうちょっと詳しく、または丁寧な説明が欲しい人は「暗号技術入門」を読むのがいいと思う。

東大でもOCW

ここのところオンラインの授業について書いているが、東大でも数年前から授業を配信しているらしい。

今日のニュースにはiTunes Uに参加するという記事があった。
iTunes Uは大学の授業や教材を配信する目的で設けられたものらしい。

東大のコンテンツはStanfordとかUCBerkeleyに比べるとちょっと少ない感じがするけど、これからきっといいものが出てくるんだろう。

こんな素晴らしいコンテンツはみんな利用すべきだ。東大に行けなくたって東大の授業受けられるんだから、すばらしい。まあ実際にそこで入学して受けるのとは、環境などの点で異なるかも知れないけど、これだけの教育機会が得られるというのは本当に素晴らしいと思う。

ただで授業を!

前回のポストで、フリーで受けられる授業をまとめるといいかもしれないということを書いた。

やっぱり、すでにやっている人がいて
http://freescienceonline.blogspot.com/
にかなりたくさんまとまっている。僕が知っている奴は全部ここにあるし、ここにあってこれいい、っていうのも多々ある。

すごいのは、これを書いている人はこのほかにもブログを持っていて、それはプログラミングに関するブログだったりする。そして、その中で実際にこの授業を端から受けてそのノートや、内容を公開している。かなりシリアスにオンライン授業を受けていて、そのノートは普通の授業を受けるのとまったく変わらないような内容になっている。
アルゴリズムの授業を受けた内容は以下にまとめられている。(約1年かけてすべての授業を受けて、それぞれブログに書いている!すごい。)
http://www.catonmat.net/category/introduction-to-algorithms

ぜひ有効活用したいとともに、どうようのまとめページを作りたいと思っている。

パズル

ヘルニアで寝込んでしまった。早1か月。いまだに10分以上立ったり座ったりはできない。
つらい・・・。

まあ、そんなことを言っていてもどうもならないし、病院に行ってはいるので、そこで言われるようにするしかないということで、勉強をしようと思って、本なりビデオなりを見ている。

そんなとき、以前にFacebookの採用情報欄にパズルが載っていたのを思い出した。プログラミングの問題が載っていて、それを解いて送ると、まあ、採用に少しは考慮してくれるみたいな感じのやつ。
ただし、結構難しい。

というわけで、今回はこれをやってみることにした。
http://www.facebook.com/careers/puzzles.php#!/careers/puzzles.php?puzzle_id=8
Peak Trafficという問題。

いろいろアルゴリズムなどを調べながらやった。
今回はちょっと1日当たりパソコンを触っていられる時間も限られているので、2週間ぐらいかけてちょっとづつ調べたり、プログラム書いたりして完成させた。

Facebookにこのトピックに関しての掲示板があったのでそこも参考にした。すでに解いている人が、テスト用データやどのくらい処理に時間がかかったかなどを載せている。
http://www.facebook.com/careers/puzzles.php#!/topic.php?uid=15325934266&topic=6943

とりあえず、今日Facebookに送ったところ、正解とのこと。扱ったことのないデータ構造やアルゴリズムだったのでそれだけでもかなり勉強になった。

ただ、何日か前に一応答えを出せるプログラムは書いたのだけれど遅いのが気になって少し何とかならないかと挑戦したけど、だめだった。
さっきの掲示板に投稿している人は、あるテストデータ(60MB程度)を処理するのにPythonで書いて、10秒以内だそうだ。ちなみに僕のはRubyで書いて6分;;。お話になりません。

どうしたらいいんだろうと考えたけど、だめだった。まだまだ考えられる余地はあるので、まだがんばる。
PythonとRubyの差も多少はありそうだが、そんなレベルの違いじゃないな。

ちなみに、そんなときに出会ったのが以下のレクチャー
(これ自体はこのとはの直接の答えではないけど、何か得られるものがないかと思って見た。)
この前のMITの授業といい、こんなのが見られるなんて何て素晴らしいんだ。
ほかにもUCBerkleyのStructure and Interpretation of Computer Programを使った授業もYouTubeで見られる。
この辺は、どこかのページにテキストブックとともにまとめておく価値がありそうだ。



Vimの不明な挙動

今日、とあるファイルをVimを使って編集しようとしたら、なぜかテキストフォーマットが効かない。
XMLだったのだけれど、色がついたりいつもなら自動的にするはずなのに。

いつもと使っているPCが違ったので、なんかVIMRCとかがおかしいんだろうとか、そんな風に思って、
いつもの設定にファイルを上書きしたりして、戻した。

んー、でも治らない。なんでだ。
Vimはここから落としてきたもの。
http://www.kaoriya.net/

んで、仕方なくいつも使っている環境と見比べながらいろいろ試した。
バージョンが違うのか、VIMRC,GVIMRCの場所や名前がおかしいのかなど調べたけどよくわからず。

新しい環境は、Windows 7で、僕はVimのファイルをProgram Files下に全部コピーしていた。
なんとなくそれがだめなのかなと思って、すべてC:\直下に移動。
するとうまくいった。
あら、どういうことだ。でもなんかおかしい。
で、今度は、Program Files下だけれど名前を変えてみた。そしたらうまくいった・・・。

結局行き着いた先はVimを入れているフォルダの名前を1文字変えるだけ。それだけでうまくいく。

C:\Program Files\Vim72

C:\Program Files\Vim7
にするだけでいい。というかこうじゃなくてもVim72じゃなければいいみたい。
ということで
C:\Program Files\Vim
とした。そういえば前の環境もこの名前にしていた。

でも、これだけで状況がこんなに違ってしまうってどういうことだ?
Vim本体がC:\Program Files\Vim72という名前に対してセンシティブなのはなんでだ。

ちなみに環境変数なんかも見てみたけど、とくにこれらの値はなかった。ほかに考えられるのはなんだろうか。

誰か知ってたら教えてください。

ViEmuでCtrl+CやCtrl+Vを有効にする

Visual StudioでViと同様のキー操作を可能にするためのツールにViEmuがある。これを使うとほとんどViと同様の操作でテキスト編集ができるため、Viを普段使っている人にはとっても便利。

ただし、デフォルトだとCtrl+CやCtrl+VはViのキーバインドではなく、標準のコピー、ペーストになっている。
Ctrl+Cやコマンドキャンセル、Ctrl+Vはブロック選択なので、使いたい人は使いたいだろう。

実は、これらを有効に(つまりViと同様のキーに)するのは簡単。

Visual Studioのメニュー
「ツール」→「オプション」と選択し、ダイアログで
「ViEmu - General」のタブを開く。「Keyboard...」を選択し以下の画面へ。





重要なのは右下の「Key scanned, with Ctrl...」とあるテキストボックス。
ViEmuはここにある文字とCtrlの組み合わせが、VisualStudioとViとぶつかるかどうかをスキャンする。

たとえば、このテキストボックスに「C」とある場合、ViEmuは「Ctrl+C」がVisualStudioとViとで衝突が起きるかどうかを検出する。逆にこのテキストボックスに「C」がなければViEmuはそれについては何もしない。つまりVisual Studio標準のままにする。

デフォルトでは、このテキストボックス内にはVとCは含まれない。つまり、そのまま放置しているということだ。

というわけで、この中にCとVの文字を上の画像のように入れる。そして「Apply」キーを押す。

ただし、これだけではViEmuはまだこのキーバインドを入れ替えない。
このダイアログボックスの右上のリストには、衝突が検出されたもののリストがある。

これを置き換えたい(つまり、Viのキーバインドにしたい)場合には、その下にある「Save and Remove」を押す。

これで、完了。


このダイアログのなかのリストとボタンの関係は、若干直観的ではない。理解するまでにちょっと時間がかいかる。
とりあえず、Ctrl+VやCtrl+Cを有効に(Viと同じに)したければ上のことだけやればよい

Windows 7でSMBサーバにつながらないとき

Windows 7から、Linuxで動作しているSMBサーバにつなげようとしたらつながらないという問題に遭遇した。
Windows XPとかならちゃんと見える。

いろいろ調べた結果よくわからないけど、以下のような解決方法

http://www.tomshardware.com/forum/75-63-windows-samba-issue



Control Panel - Administrative Tools - Local Security Policy

Local Policies - Security Options



Network security: LAN Manager authentication level
Send LM & NTLM responses

Minimum session security for NTLM SSP
Disable Require 128-bit encryption



とりあえず、これでつながるようにはなった。セキュリティ上問題があるかどうかは知らないけど。
feedSubscribe to my feed