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

引用

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ページある。各部は短い導入で始まる。

第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章は再帰的設計と、そこから生じる漸化式を解く方法を併せて扱う。
• 乱択アルゴリズム：第5章はアルゴリズムの確率的解析を導入する。

第6〜19章

• ソートの限界と選択：第6〜9章は比較ソートと線形時間ソートを区別し、順序統計量を扱う。
• 動的計画法、貪欲法、償却解析：第IV部の三つの技法。
• 平衡・拡張された探索構造：赤黒木、B木、データ構造の拡張（第13、17、18章）。

第20〜35章

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

批判的分析

長所

• 厳密さと網羅性。 出版社は本書を厳密さと網羅性を兼ね備えたものと説明し、各章は自己完結的で、アルゴリズムは疑似コードで書かれているため、さまざまな箇所から読み始められる。
• 数学的背景を収録。 付録A〜Dが総和、集合、数え上げと確率、行列を扱い、前提知識の多くを本書内で復習できる。
• 演習と問題。 第4版は演習を140問、問題を22問追加し、読者の意見に基づいて従来の問題も改善している。
• 内容の新しさ。 二部グラフのマッチング、オンラインアルゴリズム、機械学習の章が加わり、漸化式、ハッシュ表、ポテンシャル関数、接尾辞配列にも新しい内容がある。

短所

• 分量の大きさ。 35章・千ページを超える本書は教科書であると同時に参考書でもあり、一つの講義で全体を扱うことはできないため、読者が取捨選択する必要がある。
• 疑似コードのみ。 アルゴリズムは疑似コードで示されるので、動くプログラムが欲しい読者は自分で実装しなければならない。
• 選ばれた話題は簡潔。 線形計画法（約27ページ）や機械学習（約39ページ）などは各1章で、完全な扱いというより入門の役割を果たす。
• 初学者には負担が大きい。 数学的な書き方と長さのため、アルゴリズムとの最初の出会いとしては難しく、講義と併用するか二周目に読むほうがよい。

コースにおける位置づけ

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

専門的な発展としては、本書の第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部の各章はおおむね独立しており、関心に応じて任意の順に読める。

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