プログラムの動かし方の本

Seasarカンファレンスで、基礎としてプログラムの動かし方であげた本。と、それに加えて挙げれなかった本。
ちなみにSeasarカンファレンスでの内容はid:tanamonがまとめてくれてる。というか、手書きスライドの書き起こしをしてもらってます。
「手書きで書く→ソーシャルに清書してもらう」という、新しいプレゼン手法が生まれました！
差のつく勉強法200のメモ - tanamonの日記

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

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

やさしく学べる離散数学

この本は広く浅く取り上げられてて、離散数学って言ったときにどんな内容を扱うのかがわかっていい。
ただ、本の分量的に説明が簡潔になりすぎてて、これで理解するというのは難しいとは思う。概観を与えてくれる本としていい。

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

離散数学―コンピュータサイエンスの基礎数学 (マグロウヒル大学演習)

「コンピュータのための離散数学」とか「情報技術のための離散数学」という本がいくつか出てるけど、組み合わせ論・グラフ理論の本になってて、集合論・論理は扱われないものも多い。
そういうのは「プログラムをどう動かすか」の話についての離散数学になると考えてるのだけど、それならこの本でもいいかもしれない。

離散数学への招待〈上〉

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

離散数学「数え上げ理論」―「おみやげの配り方」から「Nクイーン問題」まで (ブルーバックス)

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

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

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

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

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

この本のいいところは、薄いこと！ムダがない。ムダにアルゴリズムの列挙になっていない。
普通のアルゴリズムの入門書は、アルゴリズムカタログになってて、「アルゴリズムを勉強するというのは、いろいろなアルゴリズムを知っておいて、必要になったときに使えること」だという誤解を持ってしまいかねない。
そういう視点で「アルゴリズムの勉強」を捉えると、「アルゴリズムが実装されたライブラリが普及しているからアルゴリズムの勉強は不要」ということになってしまう。
アルゴリズムを勉強するというのは、与えられた問題をいかに砕いて効率よく手続きを実装するかを勉強することで、「データ構造とアルゴリズム基礎講座」はそういう点でとてもいい。

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

JavaScriptによるアルゴリズムデザイン―オブジェクト指向からDB・Web・マイニングまで

この本は、JavaScriptのような仮コードを使っているだけで、まったく「JavaScriptによる」という冠はふさわしくない。書評にあるように『出版社の「売らんかな」の都合』でこういう冠がついたのだけど、それでこの本の対象とは違う層を呼び込んで、amazonで星1つになってるのだから、バカなことをしたものだと思う。
まあ、それはそうとして、内容はいい本で、Webに関するアルゴリズムとしてPageRankとかも扱ってたりするので、3900円でも高くないし、読み応えもある。

アルゴリズムを勉強するときに、かならず裏には計算量や計算可能性という言葉がでてくる。プログラムをどう動かすか考えるときには、計算機になにができるかを知っておく必要がある。
そういう、計算機になにができるかを知るには、この本がいい。じっくり読めば読める本だと思うし、３分冊になってて持ち運びやすいので、気長に読めばいいんじゃないかと思う。

計算理論の基礎 [原著第2版] 1.オートマトンと言語

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

計算論への入門―オートマトン・言語理論・チューリング機械 (スタンダードテキスト)

ただ、勉強をここまでやって、計算可能性、つまり計算機の限界を知ると、計算困難な問題はあきらめるしかないと思ってしまう。実際には、そういう計算困難な問題には乱数を使ったアプローチや近似アプローチが研究されてて、本も結構でてる。
あと、アルゴリズムの本で扱われているアルゴリズムは、入力はすべて揃っている前提になっていることが多い。けれども、実際には入力がまだ揃わないうちになにか結果を出さないといけないとか、入力のすべてをメモリに載せることができないとか、入力の一部だけを使うアルゴリズムを考える必要もあったりする。
ということで、アルゴリズムというのがどういうところにつながるかを見るのに、この本がおすすめ。

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

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

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

アルゴリズムデザイン

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

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

計算困難問題に対するアルゴリズム理論

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

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

The Art of Computer Programming Volume1 Fundamental Algorithms Third Edition 日本語版 (ASCII Addison Wesley Programming Series)

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

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

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

オブジェクト指向がどうこうという、なんだか変な理由で星ひとつになってますが。
あと、これは事典ですが、「アルゴリズム辞典」という本もありますね。「辞典」は「ことば(辞)」を集めた本で、アルゴリズムを集めた本としては「ことがら(事)」を集めた本という「事典」になるはずだけど。「アルゴリズム辞典」ということは用語集なのかな。