■アルゴリズム・サイエンス 出口からの超入門 [book]

アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)

• 作者: 岩間 一雄
• 出版社/メーカー: 共立出版
• 発売: 2006-10-10
• ASIN: 4320121686
• メディア: 単行本
• 

まずは、タイトルの勝利である。
『出口』からの『超』入門って? 入門書じゃないってこと?
このタイトルがなければ書店でこの本を手にしなかっただろう。
隣には「アルゴリズム・サイエンス:入口からの超入門 (アルゴリズム・サイエンスシリーズ 1―超入門編)(浅野 哲夫)」も置いてあったのだけど。

さて、本書の話に入る前に「データ構造とアルゴリズム」という本の話をしたい。
特定の本ではなくてそういうジャンルの本で、普通の本屋に売っているような範囲の本の話。
そういう本って「教科書的」だと思うのだ。

ちょっと言い直す。
そういう本は、教科書か事典的だと思うのだ。
前者はそのまんまの意味で、大学などの授業で教科書として使われる様な本だということ。データ構造やアルゴリズムについての理解を深めるための本。
後者は、つまり、名の通ったデータ構造やアルゴリズムについて、特定の言語で実装するとどうなるか? を列挙した本だということ。

で、両方の意味を併せて「教科書的」だと思う。
それはつまり「どんな本でも扱う内容は変わらない」。
クラスについて説明しないJavaの「教科書」なんてないだろう。
ポインタについて説明しないCの「教科書」なんてないだろう。
同じように、二分探索も連結リストもクイックソートも説明しない「データ構造とアルゴリズム」の本なんてないだろう。
そんな意味で、「データ構造とアルゴリズム」という本って「教科書的」だと思う。

さて、この本は、そういう「教科書的」なアルゴリズム本を離れて跳躍する。
なんせ「出口からの」本だから。
各章のタイトルを挙げる。

第1章 ウォームアップ，その1
第2章 ウォームアップ，その2
第3章 情報を漏らさない
第4章 通信量を減らそう
第5章 乱数を利用する
第6章 オンラインアルゴリズム
第7章 近似アルゴリズム
第8章 厳密アルゴリズム
第9章 幾何の計算
第10章 分散アルゴリズム
第11章 オークション
第12章 ウェブグラフ
第13章 利己的ルーティング
第14章 あとがきに代えて

いずれの章も概略、問題、必要になる基本定理の解説、アルゴリズム、検証もしくは証明、まとめ、出典そして練習問題。という感じ。

第3章は、秘密通信の話、なのだけど暗号の話じゃない。
ゼロ知識証明、電話でするジャンケン。
第4章も、圧縮の話じゃない。この本はアルゴリズムの本。
2点間の間で共有されていないデータを持っていて、その間で通信して中央値を求めるには? といった話題。

第5章はタイトルの通り。アルゴリズムを作ろうとすると難解な問題でも、でたらめにやれば大体うまくいく、という類のもの。
第7章も同じように、最善の解を求めることが現実的に難しい(現実的な――実用的な時間内で終わることが期待できない)問題の話。
アルゴリズムについて学んだなら、NP問題、NP完全問題、P≠NP予想といったところを思い浮かべるだろう。そのような記述は出てくるが細かい話までは踏み込まない。あくまでも問題とアルゴリズムを示す。
第8章は、逆に最善の解でなければ意味がないタイプの問題。

この本でためになる(と私が感じた)のは、検証。
ここでは数式がでてくる。まぁ、計算量を求めるためには当然。
それ自身もためになるが、そこでの発想、展開方法もまたためになる。
アルゴリズムの評価、特に計算量という意味では上限でおさえればいい。
理解はしているけど、実際に、滅多に目にすることがない(のは私の勉強不足だけど)アルゴリズムに対する検討はためになる。

第12章で Pagerank の話が出てくる。
Google のWeb検索で有名になった「あれ」だ。
ごく小さいページ群をモデルにして行列計算を行っている。その行列にどの様な条件が必要となるのか?
固有値や規約性から説明をし、条件を満たすための正規化などをしている。
面白かった。
逆に、この理屈をみると Google があれだけの規模のサイト群でこんな計算をしているのか、と嘆息である(とまぁこれは冗談。現実の実装はああではないはず)。

本来の読者層は、情報科学を専門とする人だと思う。
でも、「データ構造とアルゴリズム」という新刊が出てももう手にする必要を感じない人。そうはいっても情報科学が専門ではない、「現場」の SE やプログラマーの人。
そんな人も読む価値はあると思う。
さっきも書いた通り、直接役に立つかは別にして、アルゴリズムの評価や検討をするための、考え方を身につけるために。

(追記)
この本で興味を持ったオンラインアルゴリズムの巻が配本されました。

オンラインアルゴリズムとストリームアルゴリズム (アルゴリズム・サイエンスシリーズ―数理技法編)

• 作者: 徳山 豪
• 出版社/メーカー: 共立出版
• 発売: 2007-08-10
• ASIN: 4320121716
• メディア: 単行本
• 

■Death note [movie]

DEATH NOTE デスノート / DEATH NOTE デスノート the Last name complete set [DVD]

• 監督: 金子修介
• 出演: 藤原竜也,松山ケンイチ,戸田恵梨香,中村獅童,鹿賀丈史
• 出版社/メーカー: バップ
• ASIN: B000MGBOL6
• 発売: 2007-03-14
• 

後編が原作と違うのは当然として、前編の終盤もちゃんと原作から変えてくるのは圧倒的に正しい。
川井憲次の音楽がうまくマッチしてるなぁ。さんざんサントラで聴いていたからなぁ、画がつくとまた印象も変わるよなぁ。

面白かった。
素直に面白かった。
でも結末が……。ある意味意外だった。
ホントに意外だった。
原作よりも切ない話になっちゃったなぁ、なんか。

途中ででてきた月くんの統計(?)のシーン。
殺された人間を統計してプロファイルしたって?
3次元にプロットして?
それってどんな特徴量?
あぁいうシーンに説得力を与えるのは難しいよなぁ。