Jon Kleinberg, Eva Tardos『アルゴリズムデザイン』

アルゴリズムデザイン

……高いよ！　と誰もが叫びそうですが。
ふつうのアルゴリズムの本が、どちらかというとイディオムやデザインパターンレベルの、つまり実装寄りの話が多い（ような気がする）中、もうちょっと問題領域側に近寄った本、ということらしいです。つまり、現実の問題に対して、それに対処するにはどのようなアルゴリズムを選択すればよいのか、問題とアルゴリズムをどのように結びつけるのか、といったような本。

解いてほしい問題をもって相談にくる人にとっては、その問題がNP-困難であるのであきらめるしかない、という返答は決して満足できるものではない。（p505）

というのは象徴的な文かも。

……と言いつつも、PSPACEとか、「永遠に動作するアルゴリズム」とかの方も面白そうかも。アルゴリズムなのに「永遠に動作する」とは！（＜アルゴリズムのよくある定義では「停止すること＝永遠に動作しないこと」というものもあるくらいなのに注意）　これも本書ではテトリスを例にとっていて（この辺のカジュアルな感じはよいです）、テトリスを解くためのアルゴリズムは無限ストリームにに対して反応するものとされていて、これはネットワークのルータや分散ファイル共有システム、機械学習の分野でも見られるとしています。なるほど。

こういうのは、仕事で必要になるのは1年に1回あるかないか（普通はない）のですが、まさかのときのために手元にあるのはよいかも、という本でしょう。