最短経路の本
「最短経路の本」R．ブランデンベルク P．グリッツマン シュプリンガー・ジャパン株式会社
を読んだ。
基本的にはグラフ理論を現実的な側面から解説している本。レナという女の子が、コンピュータと話をしながら、グラフ理論やアルゴリズムについて学んでいくというストーリー。
最短経路
アルゴリズムの時間計算
最小全域木
オイラーグラフ
マッチング問題
中国人郵便配達問題
ハミルトングラフ
巡回セールスマン問題
といった内容を、図などを交えて、対話形式の話を読みながら学べる。
教科書のような作りではなく、章が比較的短くまとめられていて、しかも一つ一つの章の内容も難しすぎないため、非常に読みやすい。しかもいつの間にか一通りのグラフ理論の概要は理解できるようになっている（と思われる。）
グラフ理論ばかりではなく、チューリングや、オイラーなどの人物の逸話なども載っていて飽きない作りになっているし、何よりそれによって頭が疲れないようになっている。頭を使って考える部分と、少し休んで読める部分が交互にあるため、また次の章を読むときにも、エネルギーが残っている。
ただし、一つ一つ理解するには、それなりに時間がかかる部分もある。たださっと読んだだけでは理解できない部分もあり、頭を使って読み進めないと、次の瞬間には何を言っているのかわからなくなるようなことも多い。そういう意味では、教科書を進めるときのように、1ページ1ページ確実に理解して前に進むべき本だと思う。
主人公のレナは、数学が苦手な女の子の役割だが、少なくとも数学がそれなりに得意だった僕よりもよっぽど数学ができるという点はちょっと・・・と思うところはある。なので、まったく数学が苦手な人にはちょっと難しいかもしれない個所もある。（数学的に難しいというより、その場で自分で論理的に考えて、そこで言われていることを理解する力が必要になる。）
この本を読んだ後に、グラフ理論の教科書的なものを読んでいるが、この本を読んだ後で、教科書を読むのは非常に効率が良いと思う。教科書は数学的に正確な言葉で書かれていたりして、概要をつかむには、一つ一つを理解するのに時間がかかる。一方で概要が分かっていると、教科書はその概要を数学的に正しく書くとこうなるという説明として読めるので、頭の中のイメージをすぐにその式につなげることができる。式からイメージをつくるより、今あるイメージが式の中でどう表現されているかを考えるほうが楽だと思うし、この本はよい入門書になると思う。
最後の3章（全体の1割程度）は僕には難しすぎて理解できなかった。というより、個人的にはちょっと説明が雑すぎるんじゃないだろうかと思うところもある。おそらくこれですべてを理解してもらおうと思っていないというところはあると思うが、理解できない言葉（「1-木」ってなに？）ができたりして、説明されているようだけれど、理解できない。というわけで、最後の3章は読んでいない。
全体として、現実的な問題を解決するということを題材にして、説明されているので、その意味もはっきりしていて目的をもって読める。グラフ理論がどんなものか知りたい人、アルゴリズムに興味がある人は読んで損はない本だと思う。
Ubuntuでキーボードの配置変更方法
環境はUbuntu 10.4
xmodmapを使えばキーを入れ替えられる。
設定ファイルを指定して
とコマンドを入れればよい。設定ファイルの中身は、たとえば、CtrlとCapsを入れ替えるなら
と書かれた「file」を用意すればよい。ただし、gnomeの場愛、xmodmapを使わなくても入れ替える機能がある。「システム」->「設定」->「キーボード」->「レイアウト」->「オプション」->「Ctrlキーの位置」といくことで、Capsとの入れ替えを選べる。なので実際にxmodmapの使い方は、この「オプション」のリストに内容なキーの入れ替えを行いたい場合に使うのが良さそう。
今回は、日本語キーボードの「無変換」を「Windowsキー」と同じ挙動をさせようとした。Gnomeの場愛「Windowsキー」は「Super」というKeysym（キーの名前）になっているようで、これを使うといろいろショートカットが設定できるで、スペースのすぐ左にある「無変換」をこのキーとして利用できるのは便利だ（それに、個人的にWindowsでもそのような設定にしているからそうしたい。）
設定ファイルには
設定ファイルの書き方はここが詳しい。
さて、しかし、これだと毎回ログインの度にこのコマンドを行わなくてはいけない。
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」はおそらく先ほどのダイアログに出てくるすべてのファイルのリストだと思う。このリストを空にすると、また起動時に読み込むファイルを選択するダイアログが表示されるようになる。
これで、読み込むファイルを変更したくなったりしてもまたできる。
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
設定ファイルの書き方はここが詳しい。
さて、しかし、これだと毎回ログインの度にこのコマンドを行わなくてはいけない。
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 に修正。間違ってた。）
環境は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に比べるとちょっと少ない感じがするけど、これからきっといいものが出てくるんだろう。
こんな素晴らしいコンテンツはみんな利用すべきだ。東大に行けなくたって東大の授業受けられるんだから、すばらしい。まあ実際にそこで入学して受けるのとは、環境などの点で異なるかも知れないけど、これだけの教育機会が得られるというのは本当に素晴らしいと思う。
今日のニュースにはiTunes Uに参加するという記事があった。
iTunes Uは大学の授業や教材を配信する目的で設けられたものらしい。
東大のコンテンツはStanfordとかUCBerkeleyに比べるとちょっと少ない感じがするけど、これからきっといいものが出てくるんだろう。
こんな素晴らしいコンテンツはみんな利用すべきだ。東大に行けなくたって東大の授業受けられるんだから、すばらしい。まあ実際にそこで入学して受けるのとは、環境などの点で異なるかも知れないけど、これだけの教育機会が得られるというのは本当に素晴らしいと思う。
ただで授業を！
前回のポストで、フリーで受けられる授業をまとめるといいかもしれないということを書いた。
やっぱり、すでにやっている人がいて
http://freescienceonline.blogspot.com/
にかなりたくさんまとまっている。僕が知っている奴は全部ここにあるし、ここにあってこれいい、っていうのも多々ある。
すごいのは、これを書いている人はこのほかにもブログを持っていて、それはプログラミングに関するブログだったりする。そして、その中で実際にこの授業を端から受けてそのノートや、内容を公開している。かなりシリアスにオンライン授業を受けていて、そのノートは普通の授業を受けるのとまったく変わらないような内容になっている。
アルゴリズムの授業を受けた内容は以下にまとめられている。（約１年かけてすべての授業を受けて、それぞれブログに書いている！すごい。）
http://www.catonmat.net/category/introduction-to-algorithms
ぜひ有効活用したいとともに、どうようのまとめページを作りたいと思っている。
やっぱり、すでにやっている人がいて
http://freescienceonline.blogspot.com/
にかなりたくさんまとまっている。僕が知っている奴は全部ここにあるし、ここにあってこれいい、っていうのも多々ある。
すごいのは、これを書いている人はこのほかにもブログを持っていて、それはプログラミングに関するブログだったりする。そして、その中で実際にこの授業を端から受けてそのノートや、内容を公開している。かなりシリアスにオンライン授業を受けていて、そのノートは普通の授業を受けるのとまったく変わらないような内容になっている。
アルゴリズムの授業を受けた内容は以下にまとめられている。（約１年かけてすべての授業を受けて、それぞれブログに書いている！すごい。）
http://www.catonmat.net/category/introduction-to-algorithms
ぜひ有効活用したいとともに、どうようのまとめページを作りたいと思っている。
パズル
ヘルニアで寝込んでしまった。早１か月。いまだに10分以上立ったり座ったりはできない。
つらい・・・。
まあ、そんなことを言っていてもどうもならないし、病院に行ってはいるので、そこで言われるようにするしかないということで、勉強をしようと思って、本なりビデオなりを見ている。
そんなとき、以前にFacebookの採用情報欄にパズルが載っていたのを思い出した。プログラミングの問題が載っていて、それを解いて送ると、まあ、採用に少しは考慮してくれるみたいな感じのやつ。
ただし、結構難しい。
というわけで、今回はこれをやってみることにした。
http://www.facebook.com/careers/puzzles.php#!/careers/puzzles.php?puzzle_id=8
Peak Trafficという問題。
いろいろアルゴリズムなどを調べながらやった。
今回はちょっと１日当たりパソコンを触っていられる時間も限られているので、２週間ぐらいかけてちょっとづつ調べたり、プログラム書いたりして完成させた。
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で見られる。
この辺は、どこかのページにテキストブックとともにまとめておく価値がありそうだ。
つらい・・・。
まあ、そんなことを言っていてもどうもならないし、病院に行ってはいるので、そこで言われるようにするしかないということで、勉強をしようと思って、本なりビデオなりを見ている。
そんなとき、以前にFacebookの採用情報欄にパズルが載っていたのを思い出した。プログラミングの問題が載っていて、それを解いて送ると、まあ、採用に少しは考慮してくれるみたいな感じのやつ。
ただし、結構難しい。
というわけで、今回はこれをやってみることにした。
http://www.facebook.com/careers/puzzles.php#!/careers/puzzles.php?puzzle_id=8
Peak Trafficという問題。
いろいろアルゴリズムなどを調べながらやった。
今回はちょっと１日当たりパソコンを触っていられる時間も限られているので、２週間ぐらいかけてちょっとづつ調べたり、プログラム書いたりして完成させた。
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で見られる。
この辺は、どこかのページにテキストブックとともにまとめておく価値がありそうだ。
