アルゴリズムイントロダクション (第 2 巻) 第 3 版

原著は、計算機科学の基礎分野で世界的に著名な 4 人の専門家が MIT での計算機アルゴリズムの教育用に著したテキストで、今回訳出したのは第 3 版です。前版までで既にアルゴリズムとデータ構造に関する世界標準教科書としての地位を確立しておりますが、より良い教科書を目指して再び全面的な記述の見直しがなされ、それを基に新たな章や節の追加なども含めて大幅な改訂がなされております。単にアルゴリズムをわかりやすく解説するだけでなく、最終的にアルゴリズム設計に至るまでに、どのような概念が必要で、それがどのように解析に裏打ちされているのかを科学的に詳述しているところに大きな特徴があります。

動的計画法や貪欲法の正しさを自分で示し、グラフの最短路や最大フローの計算量を説明できるようになりたい人に向けた、アルゴリズムの本格的な教科書の分冊です。『アルゴリズムイントロダクション 第 2 巻 第 3 版』は、T. コルメン、C. ライザーソン、R. リベスト、C. シュタインの 4 名による Introduction to Algorithms 原著第 3 版の日本語版のうち、原著の第 15 章から第 26 章を収めた巻で、副題は「高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム」です。訳者は浅野 哲夫、岩野 和生、梅尾 博司、山下 雅史、和田 幸一の 5 名で、近代科学社の「世界標準 MIT 教科書」の一冊として 2012 年 12 月 26 日に発売されました。

原著第 15 章から第 26 章、3 部 12 章の構成

本巻は原著の第 IV 部から第 VI 部にあたる 3 部で構成され、章番号も原著どおり 15 から 26 までが振られています。最初の部「高度な設計と解析の手法」は第 15 章「動的計画法」、第 16 章「貪欲アルゴリズム」、第 17 章「ならし解析」の 3 章で、ロッド切出し、連鎖行列積、最長共通部分列、ハフマン符号、マトロイドと貪欲法といった節が並びます。続く「高度なデータ構造」は第 18 章「B 木」、第 19 章「フィボナッチヒープ」、第 20 章「van Emde Boas 木」、第 21 章「互いに素な集合族のためのデータ構造」の 4 章です。最後の「グラフアルゴリズム」は第 22 章「基本的グラフアルゴリズム」から第 26 章「最大フロー」までの 5 章で、幅優先探索と深さ優先探索、トポロジカルソート、強連結成分から、Kruskal と Prim のアルゴリズム、Dijkstra のアルゴリズム、Floyd-Warshall アルゴリズム、Ford-Fulkerson 法、2 部グラフの最大マッチングまでが目次に並びます。巻頭にまえがき、巻末に参考文献、訳者あとがき、索引が付きます。

設計手法とデータ構造の解析の背景

アルゴリズムを使う側に立つと、ライブラリの関数を呼べば済むように見えます。しかし、どの手法がどの条件で正しく動き、どれだけの時間がかかるかを判断できなければ、データが増えたときの遅さや誤った結果の原因を突き止められません。動的計画法は重なり合う部分問題の答えを再利用する考え方で、貪欲法は局所的な選択が全体の最適につながる条件を示せて初めて安全に使えます。ならし解析は、ときどき重い処理が混ざる操作の列を全体で平均して評価する方法で、配列を伸び縮みさせる動的な表のように、1 回ごとの最悪値だけでは実態を見誤る場面で効いてきます。データ構造の側では、B 木 はディスクのように 1 回の読み出しが高くつく記憶装置で探索の回数を減らす設計としてデータベースの索引の土台になり、互いに素な集合族のデータ構造は最小全域木を求める処理の中核で使われます。こうした判断を支えるのが、入力の大きさに対する手間の増え方を見積もる 計算量 の考え方です。版元の紹介文が、アルゴリズム設計に至るまでに必要な概念と、それがどのように解析に裏打ちされているのかを科学的に詳述していると説明しています。

第 1 巻の続きとして読む前提と、本巻に含まれない範囲

章番号が第 15 章から始まるとおり、本巻は第 1 巻の続きにあたる分冊です。通読するなら第 1 巻の前半の章が先にあたります。版元は、各節末に多様なレベルの問題が配置され、教科書としてだけでなく技術系専門家の手引書や事典としても活用できると案内しており、必要な章だけを引いて精読する使い方にも向きます。一方で、本巻の目次は第 26 章「最大フロー」で終わり、原著の第 27 章以降にあたる題材は含まれていません。原著の範囲をまとめて手元に置きたい場合は、版元が関連する書籍として案内している第 1 巻と総合版も合わせて確認してください。

特定の言語ですぐ動くコードを写して使いたい人や、頻出の解法パターンを短時間で覚えたい人のための本ではなく、概念と解析を順に積み上げる書き方です。目的に合う一冊を比べたい場合は アルゴリズム本の選び方 が参考になります。反対に、動的計画法やグラフの問題を前にしたとき、なぜその解き方で正しいのか、どこまで速くできるのかを自分の言葉で説明できるようになりたい人に向けて、本巻はその説明を原著の順に積み上げた一冊です。