アルゴリズム

アルゴリズムデザイン

Jon Kleinberg
Eva Tardos
共立出版

詳細な解説付き問題の一覧
詳細な解説付きアルゴリズムの一覧
序文

第1章 はじめに:いくつかの代表的問題

  • 1.1 最初の問題:安定マッチング
  • 1.2 五つの代表的な問題
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第2章 アルゴリズム解析の基礎事項

  • 2.1 計算容易性
  • 2.2 増加の漸近的オーダー
  • 2.3 リストと配列による安定マッチングアルゴリズムの実装
  • 2.4 よく現れる計算時間の復習
  • 2.5 より複雑なデータ構造:優先順位付きキュー
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第3章 グラフ

  • 3.1 基本的定義と応用
  • 3.2 グラフの連結性とグラフ走査
  • 3.3 キューとスタックを用いたグラフ走査
  • 3.4 二部グラフ性の判定:幅優先探索の応用
  • 3.5 有向グラフの連結性
  • 3.6 有向無閉路グラフとトポロジカル順序付け
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第4章 グリーディアルゴリズム

  • 4.1 区間スケジューリング:グリーディアルゴリズムの先進性
  • 4.2 遅延最小化スケジューリング:交換議論
  • 4.3 最適キャッシング:より複雑な交換議論
  • 4.4 グラフにおける最短パス
  • 4.5 最小全点木問題
  • 4.6 Kruskalのアルゴリズムの実装:Union-Findデータ構造
  • 4.7 クラスタリング
  • 4.8 Huffman符号とデータ圧縮
  • 4.9 最小コスト有向木:多フェーズグリーディアルゴリズム
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第5章 分割統治法

  • 5.1 最初の漸化式:マージソートアルゴリズム
  • 5.2 さらなる漸化式
  • 5.3 反転数の数え上げ
  • 5.4 最近点対の発見
  • 5.5 整数の積の計算
  • 5.6 畳込みと高速フーリエ変換
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第6章 動的計画法

  • 6.1 重み付き区間スケジューリング:再帰的手続き
  • 6.2 動的計画法の原理:部分問題上での記憶化と反復
  • 6.3 区分最小二乗法:多肢選択
  • 6.4 部分集合和とナップサック:変数の追加
  • 6.5 RNA二次構造:区間上での動的計画法
  • 6.6 系列アライメント
  • 6.7 分割統治法による線形の領域の系列アライメント
  • 6.8 グラフの最短パス
  • 6.9 最短パスと距離ベクトルプロトコル
  • 6.10 グラフの負閉路
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第7章 ネットワークフロー

  • 7.1 最大フロー問題とFord-Fulkersonアルゴリズム
  • 7.2 ネットワークの最大フローと最小カット
  • 7.3 良い増加パスの選択
  • 7.4 プリフロープッシュ最大フローアルゴリズム
  • 7.5 最初の応用:二部グラフのマッチング問題
  • 7.6 有向グラフと無向グラフにおける素パス
  • 7.7 最大フロー問題の拡張版
  • 7.8 市場調査デザイン
  • 7.9 航空スケジューリング
  • 7.10 画像分割
  • 7.11 プロジェクト選択
  • 7.12 野球ペナントレースの優勝の可能性の消去
  • 7.13 発展:辺にコストの付随するマッチング問題
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第8章 NPと計算困難性

  • 8.1 多項式時間リダクション
  • 8.2 “ガジェット”を用いたリダクション:充足可能性問題
  • 8.3 効率的な証明とNPの定義
  • 8.4 NP-完全問題
  • 8.5 系列化問題
  • 8.6 分割問題
  • 8.7 グラフ彩色問題
  • 8.8 数値問題
  • 8.9 co-NPとNPの非対称性
  • 8.10 計算困難な問題の部分的な分類
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第9章 PSPACE:クラスNPを超える問題のクラス

  • 9.1 クラスPSPACE
  • 9.2 PSPACEに属する困難な問題
  • 9.3 限量化問題とゲームの多項式領域解法
  • 9.4 計画問題の多項式領域解法
  • 9.5 PSPACE-完全性の証明
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第10章 計算容易性の拡大

  • 10.1 小さい点カバーの発見
  • 10.2 木におけるNP-困難問題の解法
  • 10.3 円弧集合の彩色
  • 10.4 グラフの木分解
  • 10.5 木分解の構成
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第11章 近似アルゴリズム

  • 11.1 グリーディアルゴリズムと最適解に対する近似解の上界:負荷均等化問題への適用
  • 11.2 センター選択問題
  • 11.3 集合カバー:一般的なグリーディヒューリスティック
  • 11.4 価格付け法:点カバーへの適用
  • 11.5 価格付け法による最大化:素パス問題
  • 11.6 線形計画法とラウンディング:点カバーへの適用
  • 11.7 負荷均等化問題(再考):より高度な LPの応用
  • 11.8 究極の近似保証:ナップサック問題
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第12章 局所探索

  • 12.1 最適化問題の景観図
  • 12.2 Metropolisアルゴリズムとシミュレーテッドアニーリング
  • 12.3 Hopfieldニューラルネットワークへの局所探索の応用
  • 12.4 局所探索による最大カットの近似
  • 12.5 近傍関係の選択
  • 12.6 局所探索による分類
  • 12.7 最善反応行動と Nash均衡
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第13章 乱択アルゴリズム

  • 13.1 第一の応用:競合の解消
  • 13.2 大域的最小カットの発見
  • 13.3 ランダム変数と期待値
  • 13.4 MAX3-SATに対する乱択近似アルゴリズム
  • 13.5 乱択分割統治法:中央値発見とクイックソート
  • 13.6 ハッシング:辞書の乱択実装
  • 13.7 最近点対を求める乱択アプローチ
  • 13.8 乱択キャッシング
  • 13.9 Chernoff限界
  • 13.10 負荷均等化
  • 13.11 パケットルーティング
  • 13.12 背景:いくつかの基本的な確率の定義
  • 解答付き演習問題
  • 演習問題
  • ノートと発展文献

第14章 永遠に動作するアルゴリズム

参考文献
人名索引
問題索引
アルゴリズム索引
用語和(英)索引
用語英(和)索引