# アルゴリズムイントロダクション 第3版 ## 概要 Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein による、アルゴリズムの設計と解析の標準的な教科書である。原著は *Introduction to Algorithms, Third Edition*(The MIT Press, 2009)、日本語版は浅野哲夫・岩野和生・梅尾博司・山下雅史・和田幸一の共訳で近代科学社から 2013 年に刊行された。著者 4 名の頭文字から CLRS の通称で知られる。 本書の方法は一貫している。個々のアルゴリズムを事例として並べるのではなく、まず漸近記法という共通の物差し(第 3 章)を据え、以後すべての手続きを擬似コードと定理・補題・証明という同一形式で提示する。設計技法(分割統治・動的計画法・貪欲法・乱択化・ならし解析)を先に道具として確立し、データ構造とグラフアルゴリズムをその道具の適用先として構成する。終盤の第 34 章で NP 完全性を導入して「効率的に解ける問題」の境界を引き、第 35 章の近似アルゴリズムでその外側への対処を示すことで、全体が「何が計算できて、何ができないか」という一つの問いの下にまとまる。 全 35 章と数学的基礎の付録 4 編からなり、章は互いに前提を明示しながら積み上がる。第 17 章のならし解析が第 19 章のフィボナッチヒープと第 21 章の互いに素な集合族の解析を支え、それらが第 23・24 章のグラフアルゴリズムの計算量を決める、といった依存が全巻を貫いている。 ## 書誌情報 - 書名: アルゴリズムイントロダクション 第3版 総合版(第1巻+第2巻+精選トピックス、第1〜35章・付録) - 原書: *Introduction to Algorithms, Third Edition*(The MIT Press, 2009) - 著者: [[Thomas H. Cormen]]、[[Charles E. Leiserson]]、[[Ronald L. Rivest]]、[[Clifford Stein]] - 訳者: 浅野哲夫、岩野和生、梅尾博司、山下雅史、和田幸一 - 出版社: [[近代科学社]] - 発行日: 2013 年 12 月 31 日(初版第 1 刷)、2017 年 9 月 30 日(初版第 4 刷) - ISBN: 978-4-7649-0408-8 - 構成: 全 35 章 + 付録 A〜D。第 I 部 基礎(1〜5 章)、第 II 部 ソートと順序統計量(6〜9 章)、第 III 部 データ構造(10〜14 章)、第 IV 部 高度な設計と解析の手法(15〜17 章)、第 V 部 高度なデータ構造(18〜21 章)、第 VI 部 グラフアルゴリズム(22〜26 章)、第 VII 部 精選トピックス(27〜35 章)、第 VIII 部 付録:数学的基礎(A〜D) - 原本: `.raw/books/algorithms-introduction-3rd-jp/` ## 構成と主要テーマ ### 第 I 部 基礎(1〜5 章) 本書全体の物差しを作る部。アルゴリズムを「明確に定義された計算手続き」として定義し、ループ不変式による正当性証明、漸近記法による実行時間の評価、漸化式を解く 3 手法、そして確率的解析と乱択アルゴリズムの区別という、以降の全章が前提とする道具を順に据える。 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 1 計算におけるアルゴリズムの役割]] — アルゴリズムを定義し、応用領域と、挿入ソート対マージソートの実行時間差を通じて「アルゴリズムは 1 つの科学技術である」と位置づける導入章 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 2 さあ，始めよう]] — 挿入ソートのループ不変式による正当性証明と、分割統治法によるマージソートの構成・再帰木解析で $\Theta(n\lg n)$ を導く → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 3 関数の増加]] — $\Theta$・$O$・$\Omega$・$o$・$\omega$ を関数集合として厳密に定義し、以降の章で使う標準的な数学関数の性質を整理する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 4 分割統治]] — 最大部分配列問題と Strassen の行列乗算を例に、漸化式を解く置換え法・再帰木法・主定理(マスター定理)を確立する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 5 確率的解析と乱択アルゴリズム]] — 入力分布への仮定を置く確率的解析と、アルゴリズム自身が乱数を使う乱択アルゴリズムを雇用問題で対比し、指標確率変数と期待値の線形性を導入する ### 第 II 部 ソートと順序統計量(6〜9 章) ソートを題材に、上界と下界の両方向から計算量を論じる部。ヒープソート・クイックソートで比較ソートの代表を押さえ、決定木モデルで $\Omega(n\lg n)$ の下界を証明したうえで、比較以外の情報を使ってその下界を回避する線形時間ソートへ進む。 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 6 ヒープソート]] — 配列で表現する完全 2 分木としてヒープを導入し、$O(n\lg n)$ かつその場ソートである HEAPSORT と、応用としての優先度付きキューを構成する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 7 クイックソート]] — 最悪 $\Theta(n^2)$・期待 $\Theta(n\lg n)$ の分割統治ソートを、PARTITION の性能直観・乱択化・指標確率変数による厳密な期待時間解析まで扱う → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 8 線形時間ソート]] — 決定木モデルで比較ソートの $\Omega(n\lg n)$ 下界を証明し、計数ソート・基数ソート・バケツソートでこれを回避する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 9 中央値と順序統計量]] — 乱択で期待線形時間の RANDOMIZED-SELECT と、中央値の中央値による決定的最悪線形時間の SELECT を対比する ### 第 III 部 データ構造(10〜14 章) 動的集合の実装を、素朴な表現から平衡木へ段階的に高度化する部。第 12 章が「木の高さが最悪 $\Theta(n)$ になる」という限界を示し、第 13 章の 2 色木がそれを解決し、第 14 章が既存構造に属性を足して新操作を得る「補強」という方法論そのものを取り出す。 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 10 基本データ構造]] — スタック・キュー・連結リスト・根付き木を、番兵・多重配列表現・単一配列表現・左-子右-兄弟表現という「表現の選択」の問題として扱う → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 11 ハッシュ表]] — チェイン法とオープンアドレス指定法という 2 つの衝突解決法、除算法・乗算法・万能ハッシュ法という 3 つのハッシュ関数設計、および完全ハッシュ法を扱う → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 12 2分探索木]] — 全操作が木の高さ $h$ に比例する $O(h)$ で実現できるが、$h$ は挿入順序次第で $\Theta(n)$ まで悪化しうることを示し、平衡木への動機を与える → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 13 2色木]] — 5 つの 2 色条件が高さを $O(\lg n)$ に抑えることを示し、挿入・削除の修正が定数個の場合分けと回転に還元されることを証明する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 14 データ構造の補強]] — 2 色木に部分木サイズや端点最大値を足して順序統計量木・区間木を得る手順を 4 段階に定式化し、定理 14.1 で補強の維持可能条件を与える ### 第 IV 部 高度な設計と解析の手法(15〜17 章) 第 I 部の分割統治に続く、3 つの設計・解析技法を確立する部。動的計画法と貪欲法は適用条件の強さで一列に並び、ならし解析は最悪の操作列に対する 1 操作あたりのコストという新しい評価軸を導入する。 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 15 動的計画法]] — 部分構造最適性と部分問題の重複という 2 つの適用条件、およびトップダウンのメモ化とボトムアップの表計算という 2 つの実装様式を、4 つの応用例で示す → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 16 貪欲アルゴリズム]] — 貪欲選択性が部分構造最適性に加わる追加条件であることを示し、0-1 ナップサック問題と分割可能ナップサック問題の対比で動的計画法との境界を引く → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 17 ならし解析]] — 確率を使わず最悪の操作列に対する 1 操作あたりの平均コストを求める手法を、集計法・出納法・ポテンシャル法の 3 技法で導入する ### 第 V 部 高度なデータ構造(18〜21 章) 第 III 部の平衡木を超えて、特定の前提を利用することで性能を引き出すデータ構造の部。ディスクアクセス回数(B 木)、ならし解析(フィボナッチヒープ・互いに素な集合族)、整数キーという前提(van Emde Boas 木)が、それぞれ異なる方向の改善をもたらす。 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 18 B木]] — 2 次記憶へのアクセス回数を最小化するために分岐数を大きく取る平衡探索木を、根から葉への 1 パスで挿入・削除が完結する形で構成する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 19 フィボナッチヒープ]] — ポテンシャル法を前提に INSERT・UNION・DECREASE-KEY をならし $O(1)$ に抑え、最小全域木・最短路アルゴリズムを高速化する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 20 van Emde Boas木]] — キーが整数だという追加情報を使い、比較モデルの $\Omega(\lg n)$ を破って優先度付きキューの全操作を $O(\lg\lg u)$ で実現する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 21 互いに素な集合族のためのデータ構造]] — ランクによる併合と経路圧縮の組合せが $m$ 回の操作を $O(m\,\alpha(n))$ に抑えることを、ポテンシャル法で証明する ### 第 VI 部 グラフアルゴリズム(22〜26 章) グラフを対象に、探索・全域木・最短路・フローを扱う部。大半のアルゴリズムが「不変式を保ちながら 1 ステップ進める」という共通の骨格を持ち、緩和・安全な辺・増加道がそのステップにあたる。第 V 部までのデータ構造の選択が、そのまま各アルゴリズムの計算量を決める。 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 22 基本的グラフアルゴリズム]] — 隣接リストと隣接行列の表現を導入し、BFS・DFS と、その応用としてのトポロジカルソート・強連結成分分解を $\Theta(V+E)$ で構成する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 23 最小全域木]] — 「安全な辺を 1 本ずつ加える」一般法を定理 23.1 で正当化し、互いに素な集合族を使う Kruskal と優先度付きキューを使う Prim をその具体化として示す → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 24 単一始点最短路問題]] — INITIALIZE-SINGLE-SOURCE と RELAX を共通操作とし、緩和の順序と回数だけが異なる Bellman-Ford・DAG-SHORTEST-PATHS・Dijkstra を統一的に正当化する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 25 全点対最短路]] — 隣接行列上の動的計画法(反復 2 乗法・Floyd-Warshall)と、疎グラフ向けに再重み付けして Dijkstra を反復する Johnson を対比する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 26 最大フロー]] — 残余ネットワークと増加道による Ford-Fulkerson 法を最大フロー最小切断定理で正当化し、増加道を使わないプッシュ再ラベル法を別系統として対置する ### 第 VII 部 精選トピックス(27〜35 章) 応用領域ごとのアルゴリズムを集めた部だが、末尾の 2 章が全巻の到達点になる。第 34 章が多項式時間帰着によって「効率的に解ける問題」の境界を引き、第 35 章がその外側に対する近似という妥協を提示することで、本書全体が「何が計算できるか」という問いに答え終わる。 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 27 マルチスレッドアルゴリズム]] — 仕事量とスパンという 2 尺度を導入し、並列度と貪欲スケジューラの限界を定式化して、行列乗算とマージソートを再解析する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 28 行列演算]] — LUP 分解による連立 1 次方程式の解法、行列乗算と逆行列計算の漸近的等価性、対称正定値行列と最小 2 乗近似を扱う → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 29 線形計画法]] — 標準形とスラック形による定式化、頂点間を移動するシンプレックスアルゴリズム、最適性を保証する双対性を扱い、最短路・フロー問題の線形計画への定式化を示す → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 30 多項式とFFT]] — 係数表現と点値表現の相互変換を 1 の原始 $n$ 乗根と FFT で $\Theta(n\lg n)$ にすることで、多項式乗算を $\Theta(n^2)$ から $\Theta(n\lg n)$ へ落とす → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 31 整数論的アルゴリズム]] — 入力をビット長で測る枠組みの下、ユークリッドの互除法から剰余演算・ベキ乗・RSA・Miller-Rabin 素数判定・Pollard の $\rho$ 法まで積み上げる → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 32 文字列照合]] — 素朴な方法・Rabin-Karp・有限オートマトン・Knuth-Morris-Pratt を、前処理時間と照合時間のトレードオフとして比較する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 33 計算幾何学]] — 外積による除算を使わない幾何述語を土台に、走査線法の線分交差判定、2 種の凸包構成、分割統治による最近点対発見を扱う → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 34 NP完全性]] — 決定問題としての P・NP の形式化と多項式時間帰着を定義し、CIRCUIT-SAT を起点とする帰着の連鎖で代表的問題の NP 完全性を証明する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Chapter 35 近似アルゴリズム]] — NP 完全問題に対し最適性を諦めて近似比を保証する枠組みを立て、定数近似・対数近似・FPTAS という近似可能性の階層を示す ### 第 VIII 部 付録: 数学的基礎(A〜D) 本編が前提とする数学の道具を定義する参照資料。本編を読む順序には組み込まれず、必要になった時点で参照される。 → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Appendix A 和]] — 実行時間解析で繰り返し使う級数の評価技法(帰納法・項の上界・和の分割・積分近似)を集める → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Appendix B 集合など]] — 集合・関係・関数・グラフ・木の定義を与え、第 III 部・第 V 部・第 VI 部が使う離散数学の語彙を確立する → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Appendix C 数え上げと確率]] — 数え上げ・確率公理・確率変数・期待値の線形性・幾何分布・2 項分布・裾限界を定義し、確率的解析と乱択アルゴリズムを支える → [[@2013__KindaiKagaku__アルゴリズムイントロダクション 第3版 - Appendix D 行列]] — 行列の種類と演算、逆行列・階数・行列式・正定値性を定義し、第 4・25・28 章の線形代数を支える ## 影響と位置づけ 著者 4 名の頭文字から CLRS と呼ばれ、計算機科学の学部・大学院教育において世界的に標準の教科書として使われている。第 3 版では第 27 章「マルチスレッドアルゴリズム」と第 20 章「van Emde Boas 木」が新たに加えられ、マルチコアの普及と整数キー構造の成熟が反映された。 本書の影響は内容そのものより形式にある。擬似コードの書き方、ループ不変式による正当性証明、漸近記法による実行時間の提示という様式が事実上の共通言語となり、以後のアルゴリズム文献はこの様式を前提に書かれている。 ## 関連 - 概念: [[アルゴリズム設計技法]] / [[計算複雑性]] / [[グラフアルゴリズム]] / [[B-Tree]] - 人物: [[Thomas H. Cormen]] / [[Charles E. Leiserson]] / [[Ronald L. Rivest]] / [[Clifford Stein]] - 組織: [[近代科学社]] / [[MIT]] ## 出典 - T. コルメン, C. ライザーソン, R. リベスト, C. シュタイン 共著, 浅野哲夫・岩野和生・梅尾博司・山下雅史・和田幸一 共訳, 『アルゴリズムイントロダクション 第3版 総合版』, 近代科学社, 2013.