アルゴリズム

アルゴリズムクイックリファレンス

George T.Heineman
Gary Pollice
Stanley Selkow
オライリージャパン

目次
まえがき

第I部

1章 アルゴリズムは大事だ

  • 1.1 問題を理解せよ
  • 1.2 必要なら実験しろ
  • 1.3 救援のためのアルゴリズム
  • 1.4 ついでの話
  • 1.5 この話の教訓
  • 1.6 参考文献

2章 アルゴリズムの数学

  • 2.1 問題インスタンスのサイズ
  • 2.2 関数の成長率
  • 2.3 最良、平均、最悪時の分析
  • 2.4 性能でグループ分けする
  • 2.5 異種の演算の混合
  • 2.6 ベンチマーク
  • 2.7 最後に一言
  • 2.8 参考文献

3章 パターンとドメイン

  • 3.1 パターン――コミュニケーションの言語
  • 3.2 アルゴリズムのパターン形式
  • 3.3 疑似コードのパターン形式
  • 3.4 設計形式
  • 3.5 評価実験の形式
  • 3.6 ドメインとアルゴリズム
  • 3.7 浮動小数点計算
  • 3.8 手動メモリ割り付け
  • 3.9 プログラミング言語を選ぶ
  • 3.10 参考文献

第II部

4章 整列アルゴリズム

  • 4.1 概観
  • 4.2 挿入ソート
  • 4.3 中央値ソート
  • 4.4 クイックソート
  • 4.5 選択ソート
  • 4.6 ヒープソート
  • 4.7 数え上げソート
  • 4.8 バケツソート
  • 4.9 整列アルゴリズムの選択基準
  • 4.10 参考文献

5章 探索

  • 5.1 概観
  • 5.2 逐次探索
  • 5.3 二分探索
  • 5.4 ハッシュに基づいた探索
  • 5.5 二分木探索
  • 5.6 参考文献

6章 グラフアルゴリズム

  • 6.1 概観
  • 6.2 深さ優先探索
  • 6.3 幅優先探索
  • 6.4 単一始点最短経路
  • 6.5 全対最短経路
  • 6.6 最小被覆木アルゴリズム
  • 6.7 参考文献

7章 AIにおける経路発見

  • 7.1 概観
  • 7.2 深さ優先探索
  • 7.3 幅優先探索
  • 7.4 A*探索
  • 7.5 比較
  • 7.6 ミニマックス
  • 7.7 NegMax
  • 7.8 アルファベータ法

8章 ネットワークフローアルゴリズム

  • 8.1 概観
  • 8.2 最大フロー
  • 8.3 二部マッチング
  • 8.4 増加道についての考察
  • 8.5 最小コストフロー
  • 8.6 積み替え
  • 8.7 輸送
  • 8.8 割り当て
  • 8.9 線形プログラミング
  • 8.10 参考文献

9章 計算幾何学

  • 9.1 概観
  • 9.2 凸包走査
  • 9.3 線分走査法
  • 9.4 最近傍質問
  • 9.5 範囲質問
  • 9.6 参考文献

第III部

10章 他のすべてがうまくいかなかったとき

  • 10.1 主題の変形
  • 10.2 近似アルゴリズム
  • 10.3 オフラインアルゴリズム
  • 10.4 並列アルゴリズム
  • 10.5 乱択(Randomized)アルゴリズム
  • 10.6 間違うかもしれないがその確率を減少させたアルゴリズム
  • 10.7 参考文献

11章 結び

  • 11.1 概観
  • 11.2 原則:汝のデータを知れ
  • 11.3 原則:問題を小さく分割せよ
  • 11.4 原則:正しいデータ構造を選べ
  • 11.5 原則:性能を上げるにはストレージを追加せよ
  • 11.6 原則:解が明らかでないなら、探索を構築せよ
  • 11.7 原則:解が明らかでないなら、解を持つ別の問題に帰着させよ
  • 11.8 原則:アルゴリズムを書くのは難しい、アルゴリズムを試験するのはもっと難しい

第IV部

付録 ベンチマーク

  • A.1 統計の基礎
  • A.2 ハードウェア
  • A.3 例
  • A.4 報告
  • A.5 精度

索引
訳者あとがき