アルゴリズムイントロダクション

引用

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). The MIT Press.

章の要約

第4版は7部・全35章で、その後に数学的背景の付録が続き、全体で約1,300ページある（MIT Pressは2022年刊行のハードカバーを1,312ページとしている）。各部は短い導入で始まる。

第I部 第1〜5章：基礎

第1章「The Role of Algorithms in Computing（計算におけるアルゴリズムの役割）」と第2章「Getting Started（入門）」はアルゴリズムとその解析を導入する。第3章「Characterizing Running Times（実行時間の特徴づけ）」は漸近記法を扱い、第4章「Divide-and-Conquer（分割統治）」はこの部で最も長い章の一つである。第5章「Probabilistic Analysis and Randomized Algorithms（確率的解析と乱択アルゴリズム）」は後の乱択手法の下地を作る。

第II部 第6〜9章：ソートと順序統計量

ヒープソート、クイックソート、線形時間ソート、中央値と順序統計量。これらで比較ソート、非比較ソート、選択問題を扱う。

第III部 第10〜13章：データ構造

基本的なデータ構造、ハッシュ表、二分探索木、赤黒木。ハッシュ表には約40ページの章があり、本版の変更点にもハッシュ表の新しい内容が挙げられている。

第IV部 第14〜16章：高度な設計と解析の技法

動的計画法、貪欲アルゴリズム、償却解析。動的計画法は本書でも長い章の一つ（約55ページ）である。この部では、最適化問題のための二つの主要な設計戦略と、操作列を解析する主要な道具を導入する。

第V部 第17〜19章：高度なデータ構造

データ構造の拡張、B木、互いに素な集合のデータ構造。

第VI部 第20〜25章：グラフアルゴリズム

基本的なグラフアルゴリズム、最小全域木、単一始点最短経路、全点対最短経路、最大フロー、二部グラフのマッチング。最後の章は今回の版で新設された。

第VII部 第26〜35章：選ばれた話題

並列アルゴリズム、オンラインアルゴリズム、行列演算、線形計画法、多項式とFFT、整数論的アルゴリズム、文字列照合、機械学習アルゴリズム、NP完全性、近似アルゴリズム。オンラインアルゴリズムと機械学習アルゴリズムは今回の版の新しい章である。NP完全性と近似アルゴリズムがこの部を締めくくる。

付録：数学的背景

総和、集合など、数え上げと確率、行列（付録A〜D）。その後に参考文献と索引が続く。

主要概念

第1〜5章

• 漸近記法と実行時間：機械に依存せずアルゴリズムを比較するための語彙で、第3章で展開される。
• 分割統治と漸化式：第4章は再帰的設計と、そこから生じる漸化式を解く方法を併せて扱う。MIT Pressは第4版の変更点として漸化式に関する新しい内容を挙げている。
• 乱択アルゴリズム：第5章はアルゴリズムの確率的解析を導入する。

第6〜19章

• ソートの限界と選択：第6〜9章は比較ソートと線形時間ソートを区別し、順序統計量を扱う。
• 動的計画法、貪欲法、償却解析：第IV部の三つの技法。ポテンシャル関数に関する新しい内容も、本版の変更点に挙げられている。
• 平衡・拡張された探索構造：赤黒木、B木、データ構造の拡張（第13、17、18章）。

第20〜35章

• 最短経路、全域木、フローとマッチング：第VI部のグラフの各章。
• NP完全性と近似：第34、35章。効率的な厳密アルゴリズムがないと信じられている問題とその近似を扱う。
• 選ばれた話題：並列・オンラインアルゴリズム、線形計画法、FFT、整数論、文字列照合、機械学習が、短く独立した章として置かれる。本版は変更点として接尾辞配列に関する新しい内容も挙げている。

批判的分析

長所

• 厳密さと網羅性。 出版社は本書を厳密さと網羅性を兼ね備えたものと説明し、各章は自己完結的で、アルゴリズムは疑似コードで書かれているため、さまざまな箇所から読み始められる。
• 数学的背景を収録。 付録A〜Dが総和、集合、数え上げと確率、行列を扱い、前提知識の多くを本書内で復習できる。
• 演習と問題。 第4版は演習を140問、問題を22問追加し、読者の意見に基づいて従来の問題も改善している。
• 内容の新しさ。 二部グラフのマッチング、オンラインアルゴリズム、機械学習の章が加わり、漸化式、ハッシュ表、ポテンシャル関数、接尾辞配列にも新しい内容がある。
• 表現の改訂。 MIT Pressによれば、第4版はカラーを導入し、文章をより明快で、より親しみやすく、ジェンダー中立的なものに改めている。
• 長い教育実績。 数十年にわたり多くの講義で指定され続けている。後述の「よくある講義での割り当て」に挙げたJohns Hopkins（2024年秋学期）やUC Denverの講義も、以前のMIT、Stanford、BerkeleyのOpenCourseWareやアーカイブ済みのシラバスも、本書をモジュール的に使っている。なお第2版は2001年、第3版は2009年、第4版は2022年に出ているため、講義の年代によって使われている版が異なる。

短所

• 分量の大きさ。 35章・千ページを超える本書は教科書であると同時に参考書でもあり、一つの講義で全体を扱うことはできないため、読者が取捨選択する必要がある。後述の講義例にも本書全体を割り当てているものは一つもなく、たとえばStanford CS 161（2016年春学期）は、部全体ではなく2.3、3.1、4.3〜4.5、8.1〜8.2といった個々の節を割り当てている。
• 疑似コードのみ。 アルゴリズムは疑似コードで示されるので、動くプログラムが欲しい読者は自分で実装しなければならない。
• 選ばれた話題は簡潔。 線形計画法（約27ページ）や機械学習（約39ページ）などは各1章で、完全な扱いというより入門の役割を果たす。
• 初学者には負担が大きい。 数学的な書き方と長さのため、アルゴリズムとの最初の出会いとしては難しく、講義と併用するか二周目に読むほうがよい。
• 授業資料と版の不一致。 無料で入手できるシラバスのいくつかは第3版やそれ以前の版に基づいている（後述の講義例を参照）。第4版は、特にグラフの部で一部の章番号を振り直し、新しい章も加えているため、旧版の読書リストはそのままでは移し替えられない。

コースにおける位置づけ

アルゴリズムのコースでは、本書は包括的な参考書である。Cormen自身のAlgorithms Unlockedは、本書に進む準備がまだできていない読者のための、アルゴリズムの仕組みを説明する短い入門書であり、RoughgardenのAlgorithms Illuminatedは標準的な設計パラダイムを対話的な文体で示し、ビデオ講義が付く。どちらも最初の一周に適している。SkienaのThe Algorithm Design Manualは問題を見分けて設計を選ぶための実践的な手引きで、問題カタログを備え、実装が目的のときに本書と組み合わせやすい。

KleinbergとTardosのAlgorithm Designは、後述のStanford CS 161（2016年春学期）で代替の教科書として挙げられている。

専門的な発展としては、本書の第35章が近似アルゴリズムの短い導入であり、これをVaziraniのApproximation AlgorithmsとWilliamsonとShmoysのThe Design of Approximation Algorithmsが本格的に展開している。MitzenmacherらのProbability and Computingは、第5章で始まる乱択の内容を発展させる。

本書の使い方

本書は高学年の学部生と大学院生に向き、長く使える参考書でもある。証明、総和、基本的な確率に慣れていると役立ち、付録A〜Dで復習できる。

典型的な最初のコースでは、第I部と第II部を読み、第III部・第IV部から数章（ハッシュ表、二分探索木、動的計画法、貪欲アルゴリズム）を選び、第VI部の基本的なグラフアルゴリズム、全域木、最短経路へ進む。償却解析、B木、最大フロー、NP完全性は二学期目の自然な題材である。第VII部の各章はおおむね独立しており、関心に応じて任意の順に読める。

各章は演習と問題とともに読むこと。疑似コードは、まず手でたどり、次に好きな言語で書いてみるのが理解しやすい。

よくある講義での割り当て

公開されている読書リストを見ると、講義が本書を選択的に使っていることがわかる。章番号は各シラバスが明示している版に従っており、すべてが第4版と一致するわけではない。第4版はグラフ関連の内容の多くで章番号を振り直しており（たとえば基本的なグラフアルゴリズムは、第4版のシラバスでは第20章、第3版のシラバスでは第22章として現れる）、新しい章も加えている。旧版のリストを流用する前に、MIT Pressの第3版から第4版への移行ガイド（Transition Guide）で話題を対応づけること。

最近のもの（おおむね8年以内）：

• Johns Hopkins 601.433/633、2024年秋学期（第3版必須、第4版も可）： 日程表の読書課題は第1〜9、11〜13、15〜18、21〜26、29、34〜35章にわたり、後半の講義ではオンラインアルゴリズムとアルゴリズム的学習を扱う。漸近解析とソートからグラフ、フロー、線形計画法、NP完全性、近似までを通覧する学部・大学院共通の構成である。（日程表）
• MIT OCW 6.006、2020年春学期（第3版を任意の参考書として）： 文書教材は講義ノートと演習（recitation）ノートであり、CLRS第3版は有用だが必須ではない参考書として挙げられている。（シラバス）

第4版のシラバス（ページ上に学期の年は明記されていない）：

• UC Denver CSCI 5451（第4版、2022年の教科書）： 第1、3〜4、6〜7、9、12〜15、19〜24、28〜29、32、34〜35章。第4版の章番号が明示されている（基本的なグラフは第20章、最小全域木は第21章、最大フローは第24章）。（コースページ）

以前のアーカイブ済みリスト：

• Stanford CS 161、2016年春学期（第3版）： 第1章；2.3、3.1；4.3〜4.5；第9章；第7章と第5章；8.1〜8.2；第12章；第11章；第22章；第24章と第6章；24.3；24.1と24.3；25.2と15.4；第16章と第23章；26.1〜26.3。
• MIT OCW 6.006、2011年秋学期（第3版）： 第1章と第3章；2.1〜2.3、4.3〜4.6；6.1〜6.4；12.1〜12.3；8.1〜8.3；11.1〜11.4；17；22.1〜22.4；24.；15.；34.1〜34.3。
• MIT OCW 6.046J、2005年秋学期（第2版、2001年）： 第1〜9、11〜17、22〜25章。2009年の第3版より前のものなので、章番号は第2版のものとして扱うこと。
• UC Berkeley CS 170、2005年秋学期（第2版）： 第1〜5、11、15、16.3、21〜24、26、29〜30、34〜35章。同じ注意が当てはまり、第3版ではなく第2版である。

これらのリストを通じて、基礎、ソート、ハッシュ、基本的なグラフアルゴリズム、動的計画法が共通の中核をなしている。後半の「選ばれた話題」の章は一部の講義にしか現れず、章を挙げているリストはいずれも本書全体ではなく選んだ章を割り当てている。

版に関する注意

2022年刊の第4版ハードカバーのISBNは9780262046305で、電子版には別の識別子がある。どのシラバスに従う場合も、事前に節名と擬似コードを手元の版と照合すること。第3版の読書課題を第4版の章番号に対応づけるときは、章名から推測せず、上記の移行ガイドを使うこと。

学習の準備としては、ループ不変条件とその初期化・保存を説明できるかを確認するとよい。動的計画法では、まず状態と基底条件を定義することから始めること。