Algorithms Illuminated: Omnibus Edition（アルゴリズムを照らす：合本版）

引用

Roughgarden, T. (2022). Algorithms Illuminated: Omnibus Edition. Soundlikeyourself Publishing (distributed by Cambridge University Press).

章の要約

オムニバス版（2022年9月）は、別々に刊行された Algorithms Illuminated の4つのパートを、重複部分を除いて約690ページのハードカバー1冊にまとめたものである。4部24章からなり、二つの付録、エピローグ（「アルゴリズム設計のフィールドガイド」）、ヒントと解答を備える。序文によれば本書は、熟練したチューターが1年間の個人授業で語る内容の書き起こしのようなもので、著者が2012年から続けているオンライン講座と、スタンフォード大学で担当した学部の講義に基づいている。星印のついた節は最も高度な部分で、初読では流れを損なわずに飛ばすことができ、各章は「Upshot（要点）」のまとめと問題で終わる。

第I部 第1〜2章：はじめに、漸近記法

本書は整数の掛け算とカラツバ法から始まり、マージソートとその解析を経て、アルゴリズム解析の指針で第1章を閉じる。第2章はビッグO、ビッグΩ、ビッグΘ記法を展開する。序文はこれを、定数倍と低次の項を意図的に無視するという選択として説明している。

第I部 第3〜6章：分割統治アルゴリズム、マスター定理、クイックソート、線形時間選択

分割統治法を反転数の数え上げ、シュトラッセンの行列乗算、最近点対問題に適用する。続いて、こうした漸化式を解析するマスター定理を6つの例と星印つきの証明とともに扱い、ランダム化クイックソート（よいピボットが重要な理由と、ソートにはΩ(n log n)回の比較が必要であることの星印つきの証明を含む）、そしてランダム化アルゴリズムRSelectと決定的アルゴリズムDSelectによる線形時間選択を扱う。

第II部 第7〜9章：グラフの基礎、グラフ探索とその応用、ダイクストラの最短経路アルゴリズム

グラフの用語、応用、大きさ、表現法。幅優先探索と最短経路、連結成分、深さ優先探索、トポロジカルソート、強連結成分、Webの構造。そして星印つきの正しさの証明と実行時間を含むダイクストラ法を扱う。

第II部 第10〜12章：ヒープ、探索木、ハッシュテーブルとブルームフィルタ

序文がここで目指すのは、読者をデータ構造の「教養ある利用者」にすることであり、実装は星印つきの任意の節に置かれている。ヒープではダイクストラ法の高速化への利用を扱い、探索木では整列済み配列から平衡探索木へと進み、ハッシュテーブルの後にはブルームフィルタとその誤り率の発見的解析が続く。

第III部 第13〜15章：貪欲アルゴリズム入門、ハフマン符号、最小全域木

スケジューリング問題とその正しさの証明を通した貪欲法のパラダイム、木として見た最適な接頭符号のためのハフマンのアルゴリズム、そしてヒープとunion-findで高速化したプリム法とクラスカル法による最小全域木を扱い、単連結クラスタリングへの応用も示す。

第III部 第16〜18章：動的計画法入門、発展的な動的計画法、最短経路再訪

動的計画法は、パス上の重み付き独立集合問題を通して導入され、解の復元アルゴリズム、手法の原理、ナップサック問題が続く。その後、配列アラインメントと最適二分探索木を扱い、最後に負の辺の長さに対するベルマン–フォード法と、全点対最短経路のためのフロイド–ワーシャル法を扱う。

第IV部 第19〜21章：NP困難性とは何か、正しさを妥協する：効率的な非厳密アルゴリズム、速さを妥協する：非効率な厳密アルゴリズム

第IV部は最小全域木と巡回セールスマン問題の対比から始まり、易しい問題と難しい問題、NP困難な問題に対する戦略、NP困難性を証明する簡単な手順、よくある「初心者の誤り」を説明する。第20章は速い非厳密アルゴリズムを扱う。メイクスパン最小化、最大被覆、影響最大化、2-OPTヒューリスティック、局所探索の原理である。第21章は厳密だが遅い方法を扱う。ベルマン–ヘルド–カープ法、長いパスを見つけるカラーコーディング、そして混合整数計画ソルバーと充足可能性（SAT）ソルバーを使うべき場面である。

第IV部 第22〜24章：問題のNP困難性の証明、P、NP、その他もろもろ、事例研究：FCCインセンティブ・オークション

帰着、3-SATとクック–レビンの定理、帰着のテンプレート、そして独立集合、有向ハミルトン路、巡回セールスマン問題、部分和問題のNP困難性の証明。全節に星印がついた章でP、NP、P≠NP予想、指数時間仮説、NP完全性を扱い、最後に米国の周波数オークションの事例研究で、貪欲ヒューリスティックとソルバーによる実行可能性の判定が実際に使われた様子を示す。

付録、エピローグ、ヒント

帰納法による証明と離散確率の簡単な復習、アルゴリズム設計のフィールドガイド、章末問題のヒントまたは解答。

主要概念

第I部：基礎

• 漸近記法：ビッグO、ビッグΩ、ビッグΘで、実行時間が入力の大きさに応じてどう増えるかを表す。
• 分割統治法：部分問題に分け、再帰的に解き、素早く結合する。
• マスター定理：多くの分割統治の漸化式について実行時間を与える公式。
• ランダム化アルゴリズム：ランダム化クイックソートやRSelectのように「コインを投げる」アルゴリズム。

第II部：グラフアルゴリズムとデータ構造

• 線形時間のグラフ探索：幅優先探索と深さ優先探索、そして連結性や順序づけへの応用。
• ダイクストラ法：辺の長さが負でない場合の単一始点最短経路。
• ヒープ、探索木、ハッシュテーブル：用途が必要とする操作によって選ぶ構造。ブルームフィルタはときどきの誤りと引き換えに空間を節約する。

第III部：貪欲アルゴリズムと動的計画法

• 貪欲法のパラダイムと正しさの証明：近視眼的で取り消せない決定で、特別な問題でのみ最適になる。
• 最小全域木とunion-find：プリム法とクラスカル法、そしてクラスカル法を高速化するデータ構造。
• 動的計画法：ナップサック、配列アラインメント、ベルマン–フォード法のように、重なり合う部分問題を体系的に解く。

第IV部：NP困難な問題のためのアルゴリズム

• NP困難性と帰着：常に正しく常に速いアルゴリズムが存在しそうにない問題を見分けること。
• ヒューリスティックと局所探索：正しさを妥協する速いアルゴリズム。
• 厳密な指数時間アルゴリズムとソルバー：動的計画法、MIPソルバー、SATソルバーによって全数探索を改善すること。

批判的分析

長所

• 教えるために作られている。 序文によれば、本文には解答つきのクイズが100問以上散りばめられ、章末問題は簡単な確認問題から自由度の高い挑戦問題まであり、そのすべてにヒントまたは解答がつく。さらに、テストケースつきのプログラミング課題が関連Webサイトにある。
• 大部の本の中に明確な道筋がある。 星印は飛ばしてよい高度な内容を示し、各章は「Upshot」で終わる。序文は、どの章のまとまりが互いに独立しているかを説明している（分割統治法、貪欲法、動的計画法はどの順序でも教えられる）。
• 無料の動画講座。 著者はすべての節を扱う200本以上の動画を収録しており、カーガーの縮約アルゴリズムやジョンソンのアルゴリズムといった追加の話題もある。反転授業や独学に向いている。
• NP困難性の実践的な扱い。 第IV部は困難性の証明にとどまらず、その先にすべきこと、すなわちヒューリスティック、局所探索、厳密な指数時間アルゴリズム、MIPとSATのソルバー、そして実際の事例研究にまで進む。

短所

• コードではなく疑似コード。 本書はアルゴリズムを疑似コードで記述し、実装はプログラミング課題に委ねている。特定の言語ですぐ使えるコードがほしい読者には別の資料が必要である。
• 数学的な前提知識。 序文は、ある程度のプログラミング経験と、帰納法や背理法による証明への慣れを前提としている。付録は簡単な復習にすぎない。その素養のない読者は、設計は追えても解析は追えない。
• 範囲の取捨選択。 ネットワークフローや線形計画法といった話題は目次に現れず、一部の高度な話題はオンライン動画にしかない。
• 分量。 約690ページのオムニバス版には一つの講義を超える内容が含まれる。序文自身も、学部の講義（第I〜III部）と修士の講義（第III〜IV部）に分けることを提案している。

コースにおける位置づけ

本書は、このコースで最初のアルゴリズムの講義の主教科書となる。Cormenの Algorithms Unlocked は、まだ教科書に進む準備ができていない読者のための、短く数学の少ない入門書で、第I〜II部の予習として使える。Skienaの The Algorithm Design Manual は同様の技法を実践的な観点から扱い、アルゴリズム的な問題のカタログを備えているので、アルゴリズムを応用する段階でRoughgardenと並行して、あるいはその後に役立つ。Cormen、Leiserson、Rivest、Steinの Introduction to Algorithms は包括的な教科書兼参考書で、厳密な扱いとより広い範囲を求める学生に向いており、本書が扱わない話題も含む。

第IV部は、コース内の専門書へとつながる。Vaziraniの Approximation Algorithms とWilliamsonとShmoysの The Design of Approximation Algorithms は、第20章の「正しさを妥協する」というテーマを、保証された近似比とともに発展させる。MitzenmacherとUpfalの Probability and Computing は、ランダム化クイックソート、RSelect、ブルームフィルタの背後にある確率論を展開する。

本書の使い方

本書は、2〜3年次前後のコンピュータサイエンスの学部生、プログラミングができて証明を追える独学者、面接の準備をするソフトウェアエンジニアに向いている。必要であれば、まず付録AとBで帰納法と確率を復習するとよい。

実際的な読み方：

• 最初の講義（中核）： 第I〜III部、第1〜18章。初読では星印の節を飛ばす。序文によれば、データ構造の章（第10〜12章）は、10.4節を除いてグラフの章（第7〜9章）の前でも後でもよい。
• 2つ目の講義または独学： 第IV部。第19章から始め、実践的な技法として第20〜21章、帰着について第22章を読む。第23章は全節に星印がついた任意の章であり、第24章は動機づけのための事例研究である。
• 星印の節： 主要な考え方がわかったら、証明（マスター定理、クイックソートの解析、ダイクストラ法の正しさ）のために戻って読む。

クイズに出会ったら、先を読む前に立ち止まって答えること。章末問題に取り組み、ヒントと解答はその後で確認する。関連Webサイトのテストケースを使って各章で少なくとも一つのアルゴリズムを実装し、紙面で難しい節には動画を使うとよい。試験の前には「Upshot」の節とフィールドガイドを読むこと。