アルゴリズム

アルゴリズムイントロダクション 第3版 総合版(世界標準MIT教科書)

Thomas H.Cormen
Clifford Stein
Ronald L.Rivest
Charles E.Leiserson

近代科学社

まえがき

I 基礎

  • 序論
  • 1 計算におけるアルゴリズムの役割
    • 1.1 アルゴリズム
    • 1.2 科学技術としてのアルゴリズム
  • 2 さぁ,始めよう
    • 2.1 挿入ソート
    • 2.2 アルゴリズムの解析
    • 2.3 アルゴリズムの設計
  • 3 関数の増加
    • 3.1 漸近記法
    • 3.2 標準的な記法と一般的な関数
  • 4 分割統治
    • 4.1 最大部分配列問題
    • 4.2 行列積のためのStrassenのアルゴリズム
    • 4.3 漸化式を解くための置換え法
    • 4.4 漸化式を解くための再帰木法
    • 4.5 漸化式を解くためのマスター法
    • 4.6 マスター定理の証明
  • 5 確率的解析と乱択アルゴリズム
    • 5.1 雇用問題
    • 5.2 指標確率変数
    • 5.3 乱択アルゴリズム
    • 5.4 確率的解析と指標確率変数のさらなる利用

II ソートと順序統計量

  • 序論
  • 6 ヒープソート
    • 6.1 ヒープ
    • 6.2 ヒープ条件の維持
    • 6.3 ヒープの構築
    • 6.4 ヒープソートアルゴリズム
    • 6.5 優先度付きキュー
  • 7 クイックソート
    • 7.1 クイックソートの記述
    • 7.2 クイックソートの性能
    • 7.3 乱択版クイックソート
    • 7.4 クイックソートの解析
  • 8 線形時間ソート
    • 8.1 ソートの下界
    • 8.2 計数ソート
    • 8.3 基数ソート
    • 8.4 バケツソート
  • 9 中央値と順序統計量
    • 9.1 最大値と最小値
    • 9.2 線形期待時間選択アルゴリズム
    • 9.3 線形最悪時間選択アルゴリズム

III データ構造

  • 序論
  • 10 基本データ構造
    • 10.1 スタックとキュー
    • 10.2 連結リスト
    • 10.3 ポインタとオブジェクトの実現
    • 10.4 根付き木の表現
  • 11 ハッシュ表
    • 11.1 直接アドレス表
    • 11.2 ハッシュ表
    • 11.3 ハッシュ関数
    • 11.4 オープンアドレス指定法
    • 11.5 完全ハッシュ法
  • 12 2分探索木
    • 12.1 2分探索木
    • 12.2 2分探索木に対する質問
    • 12.3 挿入と削除
    • 12.4 ランダムに構成した2分探索木
  • 13 2色木
    • 13.1 2色木の性質
    • 13.2 回転
    • 13.3 挿入
    • 13.4 削除
  • 14 データ構造の補強
    • 14.1 動的順序統計量
    • 14.2 データ構造補強法
    • 14.3 区間木

IV 高度な設計と解析の手法

  • 序論
  • 15 動的計画法
    • 15.1 ロッド切出し
    • 15.2 連鎖行列積
    • 15.3 動的計画法の基本要素
    • 15.4 最長共通部分列
    • 15.5 最適2分探索木
  • 16 貪欲アルゴリズム
    • 16.1 活動選択問題
    • 16.2 貪欲戦略の基本要素
    • 16.3 ハフマン符号
    • 16.4 マトロイドと貪欲法
    • 16.5 マトロイドとしてのタスクスケジューリング問題
  • 17 ならし解析
    • 17.1 集計法
    • 17.2 出納法
    • 17.3 ポテンシャル法
    • 17.4 動的な表

V 高度なデータ構造

  • 序論
  • 18 B木
    • 18.1 B木の定義
    • 18.2 B木上の基本操作
    • 18.3 B木からのキーの削除
  • 19 フィボナッチヒープ
    • 19.1 フィボナッチヒープの構造
    • 19.2 マージ可能ヒープ操作
    • 19.3 キー値の下方修正と節点の削除
    • 19.4 最大次数の上界
  • 20 van Emde Boas木
    • 20.1 設計方針の予備的考察
    • 20,2 再帰構造
    • 20.3 van Emde Boas木
  • 21 互いに素な集合族のためのデータ構造
    • 21.1 互いに素な集合族の操作
    • 21.2 連結リストによる互いに素な集合族の表現
    • 21.3 互いに素な集合の森
    • 21.4 経路圧縮を用いるランクによる合併の解析

VI 不ラフアルゴリズム

  • 序論
  • 22 基本的グラフアルゴリズム
    • 22.1 グラフの表現
    • 22.2 幅優先探索
    • 22.3 深さ優先探索
    • 22.4 トポロジカルソート
    • 22.5 強連結成分
  • 23 最小全域木
    • 23.1 成長法による最小全域木の生成
    • 23.2 KruskalとPrimのアルゴリズム
  • 24 単一始点最短経路問題
    • 24.1 Bellman-Fordアルゴリズム
    • 24.2 有向非巡回グラフにおける単一始点最短路
    • 24.3 Dijkstraのアルゴリズム
    • 24.4 差分制約と最短路
    • 24.5 最短路の性質の証明
  • 25 全点対最短路
    • 25.1 最短路と行列積
    • 25.2 Floyd-Warshallアルゴリズム
    • 25.3 疎グラフに対するJohnsonのアルゴリズム
  • 26 最大フロー
    • 26.1 フローネットワーク
    • 26.2 Ford-Fulkerson法
    • 26.3 2部グラフの最大マッチング
    • 26.4 プッシュ再ラベルアルゴリズム
    • 26.5 再ラベルフロント移動アルゴリズム

VII 精選トピックス

  • 序論
  • 27 マルチスレッドアルゴリズム
    • 27.1 動的マルチスレッドの基礎
    • 27.2 行列乗算のためのマルチスレッドアルゴリズム
    • 27.3 マージソートのマルチスレッド化
  • 28 行列演算
    • 28.1 連立1次方程式の解法
    • 28.2 逆行列の計算
    • 28.3 対称正定値行列と最小2乗近似
  • 29 線形計画法
    • 29.1 標準形とスラック形
    • 29.2 線形計画としての問題の定式化
    • 29.3 シンプレックスアルゴリズム
    • 29.4 双対性
    • 29.5 初期実行可能基底解
  • 30 多項式とFFT
    • 30.1 多項式の表現
    • 30.2 DFTとFFT
    • 30.3 効率の良いFFTの実現
  • 31 整数論的アルゴリズム
    • 31.1 整数論の基本概念
    • 31.2 最大公約数
    • 31.3 剰余演算
    • 31.4 1次合同式の解法
    • 31.5 中国人剰余定理
    • 31.6 要素のベキ乗
    • 31.7 RSA公開鍵暗号系
    • 31.8 素数判定
    • 31.9 整数の素因数分解
  • 32 文字列照合
    • 32.1 素朴な文字列照合アルゴリズム
    • 32.2 Rabin-Karpアルゴリズム
    • 32.3 有限オートマトンを用いる文字列照合
    • 32.3 Knuth-Morris-Prattアルゴリズム
  • 33 計算幾何学
    • 33.1 線分の性質
    • 33.2 線分交差判定
    • 33.3 凸包の構成
    • 33.4 最近点対の発見
  • 34 NP完全法
    • 34.1 多項式時間
    • 34.2 多項式時間検証
    • 34.3 NP完全性と帰着可能性
    • 34.4 NP完全性の証明
    • 34.5 NP完全問題
  • 35 近似アルゴリズム
    • 35.1 頂点被覆問題
    • 35.2 巡回セールスマン問題
    • 35.3 集合被覆問題
    • 35.4 乱択化と線形計画法
    • 35.5 部分和問題

VIII 付録:数学的基礎

  • 序論
  • A 和
    • A.1 和の公式と性質
    • A.2 和の上界と下界
  • B 集合など
    • B.1 集合
    • B.2 関係
    • B.3 関数
    • B.4 グラフ
    • B.5 木
  • C 数え上げと確率
    • C.1 数え上げ
    • C.2 確率
    • C.3 離散確率変数
    • C.4 幾何分布と2項分布
    • C.5 2項分布の裾
  • D 行列
    • D.1 行列と行列演算
    • D.2 行列の基礎的性質

参考文献
訳者あとがき
教授の名前
索引
人名読み方ガイド