第１章はじめに：いくつかの代表的問題
- １．１最初の問題：安定マッチング
- １．２五つの代表的な問題
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第２章アルゴリズム解析の基礎事項
- ２．１計算容易性
- ２．２増加の漸近的オーダー
- ２．３リストと配列による安定マッチングアルゴリズムの実装
- ２．４よく現れる計算時間の復習
- ２．５より複雑なデータ構造：優先順位付きキュー
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第３章グラフ
- ３．１基本的定義と応用
- ３．２グラフの連結性とグラフ走査
- ３．３キューとスタックを用いたグラフ走査
- ３．４二部グラフ性の判定：幅優先探索の応用
- ３．５有向グラフの連結性
- ３．６有向無閉路グラフとトポロジカル順序付け
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第４章グリーディアルゴリズム
- ４．１区間スケジューリング：グリーディアルゴリズムの先進性
- ４．２遅延最小化スケジューリング：交換議論
- ４．３最適キャッシング：より複雑な交換議論
- ４．４グラフにおける最短パス
- ４．５最小全点木問題
- ４．６Ｋｒｕｓｋａｌのアルゴリズムの実装：Ｕｎｉｏｎ‐Ｆｉｎｄデータ構造
- ４．７クラスタリング
- ４．８Ｈｕｆｆｍａｎ符号とデータ圧縮
- ４．９最小コスト有向木：多フェーズグリーディアルゴリズム
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第５章分割統治法
- ５．１最初の漸化式：マージソートアルゴリズム
- ５．２さらなる漸化式
- ５．３反転数の数え上げ
- ５．４最近点対の発見
- ５．５整数の積の計算
- ５．６畳込みと高速フーリエ変換
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第６章動的計画法
- ６．１重み付き区間スケジューリング：再帰的手続き
- ６．２動的計画法の原理：部分問題上での記憶化と反復
- ６．３区分最小二乗法：多肢選択
- ６．４部分集合和とナップサック：変数の追加
- ６．５ＲＮＡ二次構造：区間上での動的計画法
- ６．６系列アライメント
- ６．７分割統治法による線形の領域の系列アライメント
- ６．８グラフの最短パス
- ６．９最短パスと距離ベクトルプロトコル
- ６．１０グラフの負閉路
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第７章ネットワークフロー
- ７．１最大フロー問題とＦｏｒｄ‐Ｆｕｌｋｅｒｓｏｎアルゴリズム
- ７．２ネットワークの最大フローと最小カット
- ７．３良い増加パスの選択
- ７．４プリフロープッシュ最大フローアルゴリズム
- ７．５最初の応用：二部グラフのマッチング問題
- ７．６有向グラフと無向グラフにおける素パス
- ７．７最大フロー問題の拡張版
- ７．８市場調査デザイン
- ７．９航空スケジューリング
- ７．１０画像分割
- ７．１１プロジェクト選択
- ７．１２野球ペナントレースの優勝の可能性の消去
- ７．１３発展：辺にコストの付随するマッチング問題
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第８章ＮＰと計算困難性
- ８．１多項式時間リダクション
- ８．２ “ガジェット”を用いたリダクション：充足可能性問題
- ８．３効率的な証明とＮＰの定義
- ８．４ＮＰ−完全問題
- ８．５系列化問題
- ８．６分割問題
- ８．７グラフ彩色問題
- ８．８数値問題
- ８．９ｃｏ‐ＮＰとＮＰの非対称性
- ８．１０計算困難な問題の部分的な分類
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第９章ＰＳＰＡＣＥ：クラスＮＰを超える問題のクラス
- ９．１クラスＰＳＰＡＣＥ
- ９．２ＰＳＰＡＣＥに属する困難な問題
- ９．３限量化問題とゲームの多項式領域解法
- ９．４計画問題の多項式領域解法
- ９．５ＰＳＰＡＣＥ−完全性の証明
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第１０章計算容易性の拡大
- １０．１小さい点カバーの発見
- １０．２木におけるＮＰ−困難問題の解法
- １０．３円弧集合の彩色
- １０．４グラフの木分解
- １０．５木分解の構成
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第１１章近似アルゴリズム
- １１．１グリーディアルゴリズムと最適解に対する近似解の上界：負荷均等化問題への適用
- １１．２センター選択問題
- １１．３集合カバー：一般的なグリーディヒューリスティック
- １１．４価格付け法・点カバーへの適用
- １１．５価格付け法による最大化：素パス問題
- １１．６線形計画法とラウンディング：点カバーへの適用
- １１．７負荷均等化問題（再考）：より高度なＬＰの応用
- １１．８究極の近似保証：ナップサック問題
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第１２章局所探索
- １２．１最適化問題の景観図
- １２．２Ｍｅｔｒｏｐｏｌｉｓアルゴリズムとシミュレーテッドアニーリング
- １２．３Ｈｏｐｆｉｅｌｄニューラルネットワークへの局所探索の応用
- １２．４局所探索による最大カットの近似
- １２．５近傍関係の選択
- １２．６局所探索による分類
- １２．７最善反応行動とＮａｓｈ均衡
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第１３章乱択アルゴリズム
- １３．１第一の応用：競合の解消
- １３．２大域的最小カットの発見
- １３．３ランダム変数と期待値
- １３．４ＭＡＸ３−ＳＡＴに対する乱択近似アルゴリズム
- １３．５乱択分割統治法：中央値発見とクイックソート
- １３．６ハッシング：辞書の乱択実装
- １３．７最近点対を求める乱択アプローチ
- １３．８乱択キャッシング
- １３．９Ｃｈｅｒｎｏｆｆ限界
- １３．１０負荷均等化
- １３．１１パケットルーティング
- １３．１２背景：いくつかの基本的な確率の定義
- 解答付き演習問題
- 演習問題
- ノートと発展文献
第１４章永遠に動作するアルゴリズム