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

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

アルゴリズム・サイエンスシリーズとして刊行されている中の１冊。シリーズの他の本はそれぞれ専門的なトピックを挙げているけど、これは超入門編として、いくつかの例題を通して、アルゴリズムがどのように使われるかを紹介している。トピックも多岐にわたり、それぞれさらに深い話とどうつながっているのかも紹介してあるので、学部生が自主ゼミで輪読とかすると面白いかも。

この本の特色は、ソースコードやデータ構造の話がほとんど出てこないことだ。ソートやサーチの話もトピックとして出てくるけど、教科書的な話は出てこない。抽象的なところからでなく、具体的な問題から話が始まる、「出口からの入門」としてはこのスタンスはよいと思う。実装の話はなく、むしろ数式のほうが多いので、コードをいじりながら読む必要はなく、電車の中や、寝ながら読んでも楽しめる本になっている。

特に個人的に興味を持ったのはグラフ理論まわりのアルゴリズム。グラフの塗り分け問題の話で、乱数を利用するのは、いわゆるエルデシュ的なアプローチなのかもしれないけれど、簡潔に説明してある。
ウェブグラフの話は PageRank の計算方法を説明している。以前に自分でも説明をどこかに書いた記憶があるけど、この本のほうがわかりやすい。

利己的ルーティングの話では、道路網でどの経路をとるのかを戦略とみなして、ゲーム理論と絡めている。これはアルゴリズム的ゲーム理論という分野の一面らしい。これは道路網だけじゃなくて、社会システムの設計全体に関わる話につながっているように思える。学問領域としてはまだ若いみたいだけど、面白そう。