この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。
プログラムの理論とはなにか
アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。
Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
基礎
まずは基礎です。
最初に読むのは、ソートとデータ構造が載った本で、このレベルはいろいろな本があるので、自分の使う言語での本や読みやすい本を選べばいいと思います。
なんでソートとデータ構造が最初かというと、いろいろ研究されていて話題が豊富なのと、多くのアルゴリズムがソートやデータ構造を使っていて、そこでアルゴリズムの性質が決まることが多いからです。
前にも挙げましたが、あとでいろいろ読む前提ならば、この本は読みやすくていいです。なにより薄いのがいいです。
- 作者: 長尾和彦
- 出版社/メーカー: 技術評論社
- 発売日: 2008/12/26
- メディア: 大型本
- 購入: 4人 クリック: 171回
- この商品を含むブログ (13件) を見る
読み物
基礎を終わったら本腰を入れた勉強にとりかかってもいいのですが、読み物で概要を知るのもいいと思います。
アルゴリズムの読み物といえば、この本です。計算量の分析について丁寧に扱っている本は他にはないので、かなりおすすめです。省略して「乱択ガール」というのはオススメしません。
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2011/02/26
- メディア: 単行本
- 購入: 19人 クリック: 779回
- この商品を含むブログ (103件) を見る
あとは、この本。変な機械を手に入れた女の子がアルゴリズムの世界にはまっていくという物語になっていますが、基本的に、グラフを扱った本です。グラフといっても、折れ線グラフとかのグラフではなくて、点が線で結びついた構造のことを表すグラフで、最短経路を求めるというのはグラフの中でも重要な問題です。
多くのアルゴリズムが、グラフの問題に変換できるので、グラフが大事になってきています。
- 作者: R.ブランデンベルク,P.グリッツマン,石田基広
- 出版社/メーカー: シュプリンガー・ジャパン株式会社
- 発売日: 2007/12/13
- メディア: 単行本
- 購入: 25人 クリック: 344回
- この商品を含むブログ (39件) を見る
それから、これは物語風の読み物というわけではないのだけど、どのようなアルゴリズムがあるかというのを概観するのにいい本です。
アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)
- 作者: 岩間一雄
- 出版社/メーカー: 共立出版
- 発売日: 2006/10/10
- メディア: 単行本
- 購入: 4人 クリック: 118回
- この商品を含むブログ (31件) を見る
同じシリーズに「入り口からの超入門」という本もあるのだけど、そっちはなんか狙いすぎで外した感じがあって、あまり気に入ってないのでリンクも貼らずw
この、「アルゴリズム・サイエンス」シリーズは結構いいので、気にいったところを揃えていくのもいいかもです。でも、気になるところほど刊行されてない。
ジャンプページ
学習
ある程度アルゴリズムになれたところで、腰をすえた勉強にとりかかりましょう。で、とりあげるのがこの本。
この本の見どころは計算幾何学の章で、計算幾何学というのは図形を扱うアルゴリズムです。ぶっちゃけ図形なんかほとんどの分野で扱わないし、ここにあるアルゴリズムを使うことはないだろうなとか思ってしまうんですけど、ここはアルゴリズムの選択でどのように計算量がかわってくるか、アルゴリズムのトレードオフをどう考えるかという議論がおもしろいです。
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本(ソフトカバー)
- 購入: 11人 クリック: 656回
- この商品を含むブログ (72件) を見る
あと、今回あげる中で唯一持ってない本なんですけど、この本もよく取り上げられています。
珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造
- 作者: ジョンベントリー,Jon Bentley,小林健一郎
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/10
- メディア: 単行本
- 購入: 30人 クリック: 551回
- この商品を含むブログ (162件) を見る
Webの記事では、この高橋直大さんの記事がかなりためになります。
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
発展
ここまで勉強してきたら、だいぶアルゴリズムの本が読めるようになってきます。
そこでこの本です。上であげたアルゴリズムクイックリファレンスでは、このアルゴリズムイントロダクションを参照するように指示されている箇所がかなりあります。
アルゴリズムクイックリファレンスは、ほんとにクイックでそれぞれのアルゴリズムについては簡単な説明しかなくわかりづらい面もあるのですが、この本ではそこが解説されています。
あと、データの内容によってループのそれぞれの繰り返しの処理量が違うようなアルゴリズムで、全体の計算量を求めるのに使う「ならし解析」というのがあるんですが、それについて説明している本は、ぼくが知ってる中ではこの本だけでした。
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)
- 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
- 出版社/メーカー: 近代科学社
- 発売日: 2007/03/01
- メディア: 単行本
- 購入: 10人 クリック: 169回
- この商品を含むブログ (48件) を見る
さて、アルゴリズム・デザイン。内容的にも物理的にも金銭的にも重いせいか、前回とりあげたときも、みんなクリックだけしてひとりも購入した人がいなかったのですが、広範囲な内容を深くとりあげてあって、実はリーズナブルなのかもしれません。
アルゴリズムイントロダクションや、そのダイジェストであるアルゴリズムクイックリファレンスは、どちらかというとアルゴリズムの解析の本なのですが、名前のとおりアルゴリズムをどうデザイン(設計)するかという本です。近似・乱択アルゴリズムなども取り上げられています。
あと、本棚に飾っとくとかっこいいです。

- 作者: Jon Kleinberg,Eva Tardos,浅野孝夫,浅野泰仁,小野孝男,平田富夫
- 出版社/メーカー: 共立出版
- 発売日: 2008/07/10
- メディア: 単行本
- 購入: 10人 クリック: 421回
- この商品を含むブログ (51件) を見る
応用
だんだん扱う問題が複雑になってきて、まともにやってては解が出ないということも増えてきて、乱数を使ったり、厳密解じゃなくてもいいということにしたり、いろいろな手法も必要になってきてるようで、アルゴリズム本のトレンドにも、ソート→グラフ→乱択・近似という流れがあるように思います。
この本はそういった、まともにやってては解が出せない問題に対するアプローチの本です。
数式での説明が多くて、読解困難問題もかかえていますけども。
- 作者: J.ホロムコヴィッチ,和田幸一,増澤利光,元木光雄
- 出版社/メーカー: シュプリンガー・フェアラーク東京
- 発売日: 2005/12/08
- メディア: 大型本
- 購入: 2人 クリック: 27回
- この商品を含むブログ (9件) を見る
あと、最近は並列処理とかも大事になってきてるわけで、平行アルゴリズムも大事になってきてます。
ということで、平行アルゴリズムを扱った本。平行プログラミングの本ではThe Art of Multiprocessor Programming 並行プログラミングの原理から実践までも評価が高いのだけどこちらは平行プログラミングのための部品の設計の本で、問題をどのように平行に解くかというのは、この「並行コンピューティング技法」の方という印象。
並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング
- 作者: Clay Breshears,千住治郎
- 出版社/メーカー: オライリージャパン
- 発売日: 2009/12/21
- メディア: 大型本
- 購入: 12人 クリック: 598回
- この商品を含むブログ (38件) を見る
それと、この本は手元にあるだけでまともには読んでないのだけど、アルゴリズムの広範囲な実用を取り扱ってて、あと鉄道ってだけでなんかわくわくしたりして、おもしろそうな本です。
鉄道のスケジューリングアルゴリズム―コンピュータで運行計画をつくる
- 作者: 鉄道総合技術研究所運転システム研究室
- 出版社/メーカー: エヌ・ティー・エス
- 発売日: 2006/02
- メディア: 単行本
- クリック: 16回
- この商品を含むブログ (1件) を見る
と思ったら「出品者から」になってる。読まないだろうけどすぐ手に入らなくなるから買っとけと思った判断は間違ってなかったw
実践
で、アルゴリズムの勉強をしたところで、それを活かせるような題材は手近にはなかなかなく、実装力を磨く機会もなかなかなかったりするのだけど、そういうときはTopCoderのようなプログラムコンテストがいいと思います。
でもまあ、実際のプログラムコンテストに参加するのは敷居が高いし、まわりにやっている仲間がいなかったらノウハウの共有もできない、ということで、プログラムコンテストで出たいろいろな問題とその解き方のノウハウをまとめた本。
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: 毎日コミュニケーションズ
- 発売日: 2010/09/11
- メディア: 単行本(ソフトカバー)
- 購入: 52人 クリック: 1,538回
- この商品を含むブログ (83件) を見る
プログラムコンテストの問題が解けても実際の業務には役に立たないという話も多くみかけるのだけど、この本に「プログラミングコンテストで勝つには、柔軟な発想力と幅広い知識を用いて問題を解くアルゴリズムを考え、それらを正確に実装しデバッグできなければ」いけないと書いてあり、その能力がプログラムを書く業務で役に立たないわけがないと思います。あと、ぼくも含めて、そういう能力がないから、その能力が必要ない仕事しか回ってこないんじゃないかなーと思ったり。
基礎理論
最後に、ここまでアルゴリズムアルゴリズム言ってるけど、結局根底には計算理論というものがあって、そこもちゃんと独立して勉強しておいたほうがいいと思うので、その本。
3分冊で、それぞれは軽いので、持ち運び易くていいです。
計算理論の基礎 [原著第2版] 2.計算可能性の理論
- 作者: Michael Sipser,太田和夫,田中圭介,阿部正幸,植田広樹,藤岡淳,渡辺治
- 出版社/メーカー: 共立出版
- 発売日: 2008/05/21
- メディア: 単行本
- 購入: 6人 クリック: 68回
- この商品を含むブログ (30件) を見る
計算理論の基礎 [原著第2版] 3.複雑さの理論
1冊にまとまっているほうがよければ、「アルゴリズム・サイエンス」シリーズのこの本も、たぶんいい本。あ、この本も持ってないや。
複雑さの階層 (アルゴリズム・サイエンスシリーズ―数理技法編)
- 作者: 荻原光徳
- 出版社/メーカー: 共立出版
- 発売日: 2006/11
- メディア: 単行本
- 購入: 1人 クリック: 10回
- この商品を含むブログ (3件) を見る
まあ、こんな感じでいろんなレベルのいろんな本が出てるので、好みで選んで長い時間かけて勉強していけばいいんじゃないでしょうか。ぼくもいろいろサボリすぎてたので、そろそろマジメにやります。