| 1 |
第1章 はじめに:いくつかの代表的問題 |
|
|
|
|
| 2 |
1.1 最初の問題:安定マッチング |
|
|
|
|
| 3 |
1.2 五つの代表的な問題 |
|
|
|
|
| 4 |
解答付き演習問題 |
|
|
|
|
| 5 |
演習問題 |
|
|
|
|
| 6 |
ノートと発展文献 |
|
|
|
|
| 7 |
第2章 アルゴリズム解析の基礎事項 |
|
|
|
|
| 8 |
2.1 計算容易性 |
|
|
|
|
| 9 |
2.2 増加の漸近的オーダー |
|
|
|
|
| 10 |
2.3 リストと配列による安定マッチングアルゴリズムの実装 |
|
|
|
|
| 11 |
2.4 よく現れる計算時間の復習 |
|
|
|
|
| 12 |
2.5 より複雑なデータ構造:優先順位付きキュー |
|
|
|
|
| 13 |
解答付き演習問題 |
|
|
|
|
| 14 |
演習問題 |
|
|
|
|
| 15 |
ノートと発展文献 |
|
|
|
|
| 16 |
第3章 グラフ |
|
|
|
|
| 17 |
3.1 基本的定義と応用 |
|
|
|
|
| 18 |
3.2 グラフの連結性とグラフ走査 |
|
|
|
|
| 19 |
3.3 キューとスタックを用いたグラフ走査 |
|
|
|
|
| 20 |
3.4 二部グラフ性の判定:幅優先探索の応用 |
|
|
|
|
| 21 |
3.5 有向グラフの連結性 |
|
|
|
|
| 22 |
3.6 有向無閉路グラフとトポロジカル順序付け |
|
|
|
|
| 23 |
解答付き演習問題 |
|
|
|
|
| 24 |
演習問題 |
|
|
|
|
| 25 |
ノートと発展文献 |
|
|
|
|
| 26 |
第4章 グリーディアルゴリズム |
|
|
|
|
| 27 |
4.1 区間スケジューリング:グリーディアルゴリズムの先進性 |
|
|
|
|
| 28 |
4.2 遅延最小化スケジューリング:交換議論 |
|
|
|
|
| 29 |
4.3 最適キャッシング:より複雑な交換議論 |
|
|
|
|
| 30 |
4.4 グラフにおける最短パス |
|
|
|
|
| 31 |
4.5 最小全点木問題 |
|
|
|
|
| 32 |
4.6 Kruskalのアルゴリズムの実装:Union‐Findデータ構造 |
|
|
|
|
| 33 |
4.7 クラスタリング |
|
|
|
|
| 34 |
4.8 Huffman符号とデータ圧縮 |
|
|
|
|
| 35 |
4.9 最小コスト有向木:多フェーズグリーディアルゴリズム |
|
|
|
|
| 36 |
解答付き演習問題 |
|
|
|
|
| 37 |
演習問題 |
|
|
|
|
| 38 |
ノートと発展文献 |
|
|
|
|
| 39 |
第5章 分割統治法 |
|
|
|
|
| 40 |
5.1 最初の漸化式:マージソートアルゴリズム |
|
|
|
|
| 41 |
5.2 さらなる漸化式 |
|
|
|
|
| 42 |
5.3 反転数の数え上げ |
|
|
|
|
| 43 |
5.4 最近点対の発見 |
|
|
|
|
| 44 |
5.5 整数の積の計算 |
|
|
|
|
| 45 |
5.6 畳込みと高速フーリエ変換 |
|
|
|
|
| 46 |
解答付き演習問題 |
|
|
|
|
| 47 |
演習問題 |
|
|
|
|
| 48 |
ノートと発展文献 |
|
|
|
|
| 49 |
第6章 動的計画法 |
|
|
|
|
| 50 |
6.1 重み付き区間スケジューリング:再帰的手続き |
|
|
|
|
| 51 |
6.2 動的計画法の原理:部分問題上での記憶化と反復 |
|
|
|
|
| 52 |
6.3 区分最小二乗法:多肢選択 |
|
|
|
|
| 53 |
6.4 部分集合和とナップサック:変数の追加 |
|
|
|
|
| 54 |
6.5 RNA二次構造:区間上での動的計画法 |
|
|
|
|
| 55 |
6.6 系列アライメント |
|
|
|
|
| 56 |
6.7 分割統治法による線形の領域の系列アライメント |
|
|
|
|
| 57 |
6.8 グラフの最短パス |
|
|
|
|
| 58 |
6.9 最短パスと距離ベクトルプロトコル |
|
|
|
|
| 59 |
6.10 グラフの負閉路 |
|
|
|
|
| 60 |
解答付き演習問題 |
|
|
|
|
| 61 |
演習問題 |
|
|
|
|
| 62 |
ノートと発展文献 |
|
|
|
|
| 63 |
第7章 ネットワークフロー |
|
|
|
|
| 64 |
7.1 最大フロー問題とFord‐Fulkersonアルゴリズム |
|
|
|
|
| 65 |
7.2 ネットワークの最大フローと最小カット |
|
|
|
|
| 66 |
7.3 良い増加パスの選択 |
|
|
|
|
| 67 |
7.4 プリフロープッシュ最大フローアルゴリズム |
|
|
|
|
| 68 |
7.5 最初の応用:二部グラフのマッチング問題 |
|
|
|
|
| 69 |
7.6 有向グラフと無向グラフにおける素パス |
|
|
|
|
| 70 |
7.7 最大フロー問題の拡張版 |
|
|
|
|
| 71 |
7.8 市場調査デザイン |
|
|
|
|
| 72 |
7.9 航空スケジューリング |
|
|
|
|
| 73 |
7.10 画像分割 |
|
|
|
|
| 74 |
7.11 プロジェクト選択 |
|
|
|
|
| 75 |
7.12 野球ペナントレースの優勝の可能性の消去 |
|
|
|
|
| 76 |
7.13 発展:辺にコストの付随するマッチング問題 |
|
|
|
|
| 77 |
解答付き演習問題 |
|
|
|
|
| 78 |
演習問題 |
|
|
|
|
| 79 |
ノートと発展文献 |
|
|
|
|
| 80 |
第8章 NPと計算困難性 |
|
|
|
|
| 81 |
8.1 多項式時間リダクション |
|
|
|
|
| 82 |
8.2 “ガジェット”を用いたリダクション:充足可能性問題 |
|
|
|
|
| 83 |
8.3 効率的な証明とNPの定義 |
|
|
|
|
| 84 |
8.4 NP-完全問題 |
|
|
|
|
| 85 |
8.5 系列化問題 |
|
|
|
|
| 86 |
8.6 分割問題 |
|
|
|
|
| 87 |
8.7 グラフ彩色問題 |
|
|
|
|
| 88 |
8.8 数値問題 |
|
|
|
|
| 89 |
8.9 co‐NPとNPの非対称性 |
|
|
|
|
| 90 |
8.10 計算困難な問題の部分的な分類 |
|
|
|
|
| 91 |
解答付き演習問題 |
|
|
|
|
| 92 |
演習問題 |
|
|
|
|
| 93 |
ノートと発展文献 |
|
|
|
|
| 94 |
第9章 PSPACE:クラスNPを超える問題のクラス |
|
|
|
|
| 95 |
9.1 クラスPSPACE |
|
|
|
|
| 96 |
9.2 PSPACEに属する困難な問題 |
|
|
|
|
| 97 |
9.3 限量化問題とゲームの多項式領域解法 |
|
|
|
|
| 98 |
9.4 計画問題の多項式領域解法 |
|
|
|
|
| 99 |
9.5 PSPACE-完全性の証明 |
|
|
|
|
| 100 |
解答付き演習問題 |
|
|
|
|
| 101 |
演習問題 |
|
|
|
|
| 102 |
ノートと発展文献 |
|
|
|
|
| 103 |
第10章 計算容易性の拡大 |
|
|
|
|
| 104 |
10.1 小さい点カバーの発見 |
|
|
|
|
| 105 |
10.2 木におけるNP-困難問題の解法 |
|
|
|
|
| 106 |
10.3 円弧集合の彩色 |
|
|
|
|
| 107 |
10.4 グラフの木分解 |
|
|
|
|
| 108 |
10.5 木分解の構成 |
|
|
|
|
| 109 |
解答付き演習問題 |
|
|
|
|
| 110 |
演習問題 |
|
|
|
|
| 111 |
ノートと発展文献 |
|
|
|
|
| 112 |
第11章 近似アルゴリズム |
|
|
|
|
| 113 |
11.1 グリーディアルゴリズムと最適解に対する近似解の上界:負荷均等化問題への適用 |
|
|
|
|
| 114 |
11.2 センター選択問題 |
|
|
|
|
| 115 |
11.3 集合カバー:一般的なグリーディヒューリスティック |
|
|
|
|
| 116 |
11.4 価格付け法・点カバーへの適用 |
|
|
|
|
| 117 |
11.5 価格付け法による最大化:素パス問題 |
|
|
|
|
| 118 |
11.6 線形計画法とラウンディング:点カバーへの適用 |
|
|
|
|
| 119 |
11.7 負荷均等化問題(再考):より高度なLPの応用 |
|
|
|
|
| 120 |
11.8 究極の近似保証:ナップサック問題 |
|
|
|
|
| 121 |
解答付き演習問題 |
|
|
|
|
| 122 |
演習問題 |
|
|
|
|
| 123 |
ノートと発展文献 |
|
|
|
|
| 124 |
第12章 局所探索 |
|
|
|
|
| 125 |
12.1 最適化問題の景観図 |
|
|
|
|
| 126 |
12.2 Metropolisアルゴリズムとシミュレーテッドアニーリング |
|
|
|
|
| 127 |
12.3 Hopfieldニューラルネットワークへの局所探索の応用 |
|
|
|
|
| 128 |
12.4 局所探索による最大カットの近似 |
|
|
|
|
| 129 |
12.5 近傍関係の選択 |
|
|
|
|
| 130 |
12.6 局所探索による分類 |
|
|
|
|
| 131 |
12.7 最善反応行動とNash均衡 |
|
|
|
|
| 132 |
解答付き演習問題 |
|
|
|
|
| 133 |
演習問題 |
|
|
|
|
| 134 |
ノートと発展文献 |
|
|
|
|
| 135 |
第13章 乱択アルゴリズム |
|
|
|
|
| 136 |
13.1 第一の応用:競合の解消 |
|
|
|
|
| 137 |
13.2 大域的最小カットの発見 |
|
|
|
|
| 138 |
13.3 ランダム変数と期待値 |
|
|
|
|
| 139 |
13.4 MAX3-SATに対する乱択近似アルゴリズム |
|
|
|
|
| 140 |
13.5 乱択分割統治法:中央値発見とクイックソート |
|
|
|
|
| 141 |
13.6 ハッシング:辞書の乱択実装 |
|
|
|
|
| 142 |
13.7 最近点対を求める乱択アプローチ |
|
|
|
|
| 143 |
13.8 乱択キャッシング |
|
|
|
|
| 144 |
13.9 Chernoff限界 |
|
|
|
|
| 145 |
13.10 負荷均等化 |
|
|
|
|
| 146 |
13.11 パケットルーティング |
|
|
|
|
| 147 |
13.12 背景:いくつかの基本的な確率の定義 |
|
|
|
|
| 148 |
解答付き演習問題 |
|
|
|
|
| 149 |
演習問題 |
|
|
|
|
| 150 |
ノートと発展文献 |
|
|
|
|
| 151 |
第14章 永遠に動作するアルゴリズム |
|
|
|
|
