きしだのはてな このページをアンテナに追加 RSSフィード

2009-03-18(水) プログラムの動かし方の本

プログラムの動かし方の本 21:26 プログラムの動かし方の本を含むブックマーク

Seasarカンファレンスで、基礎としてプログラムの動かし方であげた本。と、それに加えて挙げれなかった本。

ちなみにSeasarカンファレンスでの内容はid:tanamonがまとめてくれてる。というか、手書きスライドの書き起こしをしてもらってます。

「手書きで書く→ソーシャルに清書してもらう」という、新しいプレゼン手法が生まれました!

差のつく勉強法200のメモ - tanamonの日記


プレゼンや以前のエントリでは、プログラムというのは計算論と意味論に分かれると書いたけど、プログラム意味論という分野と混同してへんな議論になっちゃうので、「プログラムをどう動かすか」と「プログラムをどう書くか」に分かれるとします。命令的な側面と宣言的な側面だと言ってもいいかもしれない。今回は命令的な側面について。


まずは、基礎となる数学、離散数学について。

やさしく学べる離散数学

やさしく学べる離散数学

この本は広く浅く取り上げられてて、離散数学って言ったときにどんな内容を扱うのかがわかっていい。

ただ、本の分量的に説明が簡潔になりすぎてて、これで理解するというのは難しいとは思う。概観を与えてくれる本としていい。


「やさしく学べる離散数学」の記述で理解できて物足りないのならこの本。読むためにはそれなりの力がいりそうだけど、もっと詳しく書いてあった。


「コンピュータのための離散数学」とか「情報技術のための離散数学」という本がいくつか出てるけど、組み合わせ論グラフ理論の本になってて、集合論・論理は扱われないものも多い。

そういうのは「プログラムをどう動かすか」の話についての離散数学になると考えてるのだけど、それならこの本でもいいかもしれない。


ということで、離散数学の中で、プログラムをどう動かすかという命令的な側面にかかわるのは、組み合わせ論グラフ理論だと思う。

ということで、組み合わせ論はこの本。読み物として読める。


グラフ理論は、読み物的に読める本を探してないので、普通の教科書的な本を挙げようと思うんだけど、そういう本はほとんどどれも同じに見えた。マトロイドとかは扱ってないけど、この本でいいんじゃないかとか思う。

情報科学のためのグラフ理論 (入門 有限・離散の数学)

情報科学のためのグラフ理論 (入門 有限・離散の数学)

ってか、だれかマトロイドって何か教えてください。


グラフ理論は、出来のいいアルゴリズムの本は扱っているので、そっちでいいとも思う。そういう、グラフ理論に触れてる出来のいいアルゴリズムの本としては、この本。

Java データ構造とアルゴリズム基礎講座

Java データ構造とアルゴリズム基礎講座

この本のいいところは、薄いこと!ムダがない。ムダにアルゴリズムの列挙になっていない。

普通のアルゴリズムの入門書は、アルゴリズムカタログになってて、「アルゴリズムを勉強するというのは、いろいろなアルゴリズムを知っておいて、必要になったときに使えること」だという誤解を持ってしまいかねない。

そういう視点で「アルゴリズムの勉強」を捉えると、「アルゴリズムが実装されたライブラリが普及しているからアルゴリズムの勉強は不要」ということになってしまう。

アルゴリズムを勉強するというのは、与えられた問題をいかに砕いて効率よく手続きを実装するかを勉強することで、「データ構造とアルゴリズム基礎講座」はそういう点でとてもいい。


もうちょっと詳しく読みたいならこの本がいい。

この本は、JavaScriptのような仮コードを使っているだけで、まったく「JavaScriptによる」という冠はふさわしくない。書評にあるように『出版社の「売らんかな」の都合』でこういう冠がついたのだけど、それでこの本の対象とは違う層を呼び込んで、amazonで星1つになってるのだから、バカなことをしたものだと思う。

まあ、それはそうとして、内容はいい本で、Webに関するアルゴリズムとしてPageRankとかも扱ってたりするので、3900円でも高くないし、読み応えもある。


アルゴリズムを勉強するときに、かならず裏には計算量や計算可能性という言葉がでてくる。プログラムをどう動かすか考えるときには、計算機になにができるかを知っておく必要がある。

そういう、計算機になにができるかを知るには、この本がいい。じっくり読めば読める本だと思うし、3分冊になってて持ち運びやすいので、気長に読めばいいんじゃないかと思う。


3冊という分量と、合計1万円近くする金額がいやなら、この本でもいいかも。大判ではあるけど薄いから持ち運びやすいしね。


ただ、勉強をここまでやって、計算可能性、つまり計算機の限界を知ると、計算困難な問題はあきらめるしかないと思ってしまう。実際には、そういう計算困難な問題には乱数を使ったアプローチや近似アプローチが研究されてて、本も結構でてる。

あと、アルゴリズムの本で扱われているアルゴリズムは、入力はすべて揃っている前提になっていることが多い。けれども、実際には入力がまだ揃わないうちになにか結果を出さないといけないとか、入力のすべてをメモリに載せることができないとか、入力の一部だけを使うアルゴリズムを考える必要もあったりする。

ということで、アルゴリズムというのがどういうところにつながるかを見るのに、この本がおすすめ。

むしろ、この本のシリーズは、全部もっておけばいいんじゃないかな。


で、ここまで勉強したことをトータルで結び付けたければこの本。アルゴリズムの設計のしかた「アルゴリズムデザイン」を勉強しまくれる。

アルゴリズムデザイン

アルゴリズムデザイン

というか、他の本よまなくても、この本よんどけばいいと思う。ここまで挙げた本は、この「アルゴリズムデザイン」を読むための準備といっても過言じゃない。


ただ、「アルゴリズムデザイン」はでかいし分厚いし重いし高いからイヤじゃっていう人は、この本が結構おなじような範囲を扱っているし、ちゃんと基礎的なことから書いてあるのでおすすめ。7000円だし普通に厚いけどね。

中古で4000円とかから出てるのは、学校の教科書で使ったのが面白さが理解できなくて売りに出されたんかなぁと思う。


最後に、個別のアルゴリズムについて、その特性などを知っておくのも必要だとは思うので、そういう人のためには、たぶんこれでしょう。ぼくは読んでないけど。

まあ、それ以外のここに挙げた本たちも、途中までしか読んでないやつがたくさんあるので、ちゃんと読まないといけない。


アルゴリズムのカタログという点では、これでもいいのかな。と思ったら絶版か・・・

Javaによるアルゴリズム事典

Javaによるアルゴリズム事典

オブジェクト指向がどうこうという、なんだか変な理由で星ひとつになってますが。

あと、これは事典ですが、「アルゴリズム辞典」という本もありますね。「辞典」は「ことば(辞)」を集めた本で、アルゴリズムを集めた本としては「ことがら(事)」を集めた本という「事典」になるはずだけど。「アルゴリズム辞典」ということは用語集なのかな。