この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。
プログラムの理論とはなにか
アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。
Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
基礎
まずは基礎です。
最初に読むのは、ソートとデータ構造が載った本で、このレベルはいろいろな本があるので、自分の使う言語での本や読みやすい本を選べばいいと思います。最初はなるべく薄い本がいいですね。
なんでソートとデータ構造が最初かというと、いろいろ研究されていて話題が豊富なのと、多くのアルゴリズムがソートやデータ構造を使っていて、そこでアルゴリズムの性質が決まることが多いからです。
前にも挙げましたが、あとでいろいろ読む前提ならば、この本は読みやすくていいです。なにより薄いのがいいです。
読み物
基礎を終わったら本腰を入れた勉強にとりかかってもいいのですが、読み物で概要を知るのもいいと思います。
アルゴリズムの読み物といえば、この本です。計算量の分析について丁寧に扱っている本は他にはないので、かなりおすすめです。省略して「乱択ガール」というのはオススメしません。
処理の形と計算量は、このエントリで説明してます。
あとは、この本。変な機械を手に入れた女の子がアルゴリズムの世界にはまっていくという物語になっていますが、基本的に、グラフを扱った本です。グラフといっても、折れ線グラフとかのグラフではなくて、点が線で結びついた構造のことを表すグラフで、最短経路を求めるというのはグラフの中でも重要な問題です。
多くのアルゴリズムが、グラフの問題に変換できるので、グラフが大事になってきています。
それから、これは物語風の読み物というわけではないのだけど、どのようなアルゴリズムがあるかというのを概観するのにいい本です。
同じシリーズに「入り口からの超入門」という本もあるのだけど、そっちはなんか狙いすぎで外した感じがあって、あまり気に入ってないのでリンクも貼らずw
この、「アルゴリズム・サイエンス」シリーズは結構いいので、気にいったところを揃えていくのもいいかもです。でも、気になるところほど刊行されてない。
アルゴリズム・サイエンスシリーズ | 共立出版
学習
ある程度アルゴリズムになれたところで、腰をすえた勉強にとりかかりましょう。で、とりあげるのがこの本。
この本の見どころは計算幾何学の章で、計算幾何学というのは図形を扱うアルゴリズムです。ぶっちゃけ図形なんかほとんどの分野で扱わないし、ここにあるアルゴリズムを使うことはないだろうなとか思ってしまうんですけど、ここはアルゴリズムの選択でどのように計算量がかわってくるか、アルゴリズムのトレードオフをどう考えるかという議論がおもしろいです。
あと、今回あげる中で唯一持ってない本なんですけど、この本もよく取り上げられています。
Webの記事では、この高橋直大さんの記事がかなりためになります。
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
発展
ここまで勉強してきたら、だいぶアルゴリズムの本が読めるようになってきます。
そこでこの本です。上であげたアルゴリズムクイックリファレンスでは、このアルゴリズムイントロダクションを参照するように指示されている箇所がかなりあります。
アルゴリズムクイックリファレンスは、ほんとにクイックでそれぞれのアルゴリズムについては簡単な説明しかなくわかりづらい面もあるのですが、この本ではそこが解説されています。
あと、データの内容によってループのそれぞれの繰り返しの処理量が違うようなアルゴリズムで、全体の計算量を求めるのに使う「ならし解析」というのがあるんですが、それについて説明している本は、ぼくが知ってる中ではこの本だけでした。
さて、アルゴリズム・デザイン。内容的にも物理的にも金銭的にも重いせいか、前回とりあげたときも、みんなクリックだけしてひとりも購入した人がいなかったのですが、広範囲な内容を深くとりあげてあって、実はリーズナブルなのかもしれません。
アルゴリズムイントロダクションや、そのダイジェストであるアルゴリズムクイックリファレンスは、どちらかというとアルゴリズムの解析の本なのですが、名前のとおりアルゴリズムをどうデザイン(設計)するかという本です。近似・乱択アルゴリズムなども取り上げられています。
あと、本棚に飾っとくとかっこいいです。
応用
だんだん扱う問題が複雑になってきて、まともにやってては解が出ないということも増えてきて、乱数を使ったり、厳密解じゃなくてもいいということにしたり、いろいろな手法も必要になってきてるようで、アルゴリズム本のトレンドにも、ソート→グラフ→乱択・近似という流れがあるように思います。
この本はそういった、まともにやってては解が出せない問題に対するアプローチの本です。
数式での説明が多くて、読解困難問題もかかえていますけども。
あと、最近は並列処理とかも大事になってきてるわけで、平行アルゴリズムも大事になってきてます。
ということで、平行アルゴリズムを扱った本。平行プログラミングの本ではThe Art of Multiprocessor Programming 並行プログラミングの原理から実践までも評価が高いのだけどこちらは平行プログラミングのための部品の設計の本で、問題をどのように平行に解くかというのは、この「並行コンピューティング技法」の方という印象。
それと、この本は手元にあるだけでまともには読んでないのだけど、アルゴリズムの広範囲な実用を取り扱ってて、あと鉄道ってだけでなんかわくわくしたりして、おもしろそうな本です。
と思ったら「出品者から」になってる。読まないだろうけどすぐ手に入らなくなるから買っとけと思った判断は間違ってなかったw
実践
で、アルゴリズムの勉強をしたところで、それを活かせるような題材は手近にはなかなかなく、実装力を磨く機会もなかなかなかったりするのだけど、そういうときはTopCoderのようなプログラムコンテストがいいと思います。
でもまあ、実際のプログラムコンテストに参加するのは敷居が高いし、まわりにやっている仲間がいなかったらノウハウの共有もできない、ということで、プログラムコンテストで出たいろいろな問題とその解き方のノウハウをまとめた本。
プログラムコンテストの問題が解けても実際の業務には役に立たないという話も多くみかけるのだけど、この本に「プログラミングコンテストで勝つには、柔軟な発想力と幅広い知識を用いて問題を解くアルゴリズムを考え、それらを正確に実装しデバッグできなければ」いけないと書いてあり、その能力がプログラムを書く業務で役に立たないわけがないと思います。あと、ぼくも含めて、そういう能力がないから、その能力が必要ない仕事しか回ってこないんじゃないかなーと思ったり。
基礎理論
最後に、ここまでアルゴリズムアルゴリズム言ってるけど、結局根底には計算理論というものがあって、そこもちゃんと独立して勉強しておいたほうがいいと思うので、その本。
3分冊で、それぞれは軽いので、持ち運び易くていいです。
計算理論の基礎 [原著第2版] 2.計算可能性の理論
計算理論の基礎 [原著第2版] 3.複雑さの理論
![計算理論の基礎 [原著第2版] 1.オートマトンと言語](https://m.media-amazon.com/images/I/51rjfNYrhjL._SL500_.jpg "計算理論の基礎 [原著第2版] 1.オートマトンと言語")
1冊にまとまっているほうがよければ、「アルゴリズム・サイエンス」シリーズのこの本も、たぶんいい本。あ、この本も持ってないや。
まあ、こんな感じでいろんなレベルのいろんな本が出てるので、好みで選んで長い時間かけて勉強していけばいいんじゃないでしょうか。ぼくもいろいろサボリすぎてたので、そろそろマジメにやります。