アルゴリズム設計マニュアル 上
丸善出版
著者：S.S.スキーナ
訳者：平田富夫
第I部 実用的なアルゴリズムの設計
第1章 アルゴリズム設計への導入
1.1 ロボットのツアーの最適化
1.2 適切な仕事の選択
1.3 正しさの論証
1.3.1 アルゴリズムの表現
1.3.2 問題と性質
1.3.3 間違いを実証する
1.3.4 帰納法と再帰
1.3.5 総和
1.4 問題のモデル化
1.4.1 組合せオブジェクト
1.4.2 再帰的なオブジェクト
1.5 設計奮戦記について
1.6 ボクの設計奮戦記：超能力のモデル化
1.7 演習問題
第2章 アルゴリズム解析
2.1 計算のRAMモデル
2.1.1 最良，最悪，そして平均の計算量
2.2 ビックオー記法
2.3 増加率と支配関係
2.3.1 支配関係
2.4 ビックオーを使いこなす
2.4.1 関数の加算
2.4.2 関数の乗算
2.5 効率に関する議論
2.5.1 選択ソート
2.5.2 挿入ソート
2.5.3 文字列パターンマッチング
2.5.4 行列の乗算
2.6 対数とその応用
2.6.1 対数と2分探索
2.6.2 対数と木
2.6.3 対数とビット
2.6.4 対数と乗算
2.6.5 高速な指数計算
2.6.6 対数と総和
2.6.7 対数と刑事裁判
2.7 対数の性質
2.8 ボクの設計奮戦記：ピラミッドの謎
2.9 高度な解析(*)
2.9.1 難解な関数
2.9.2 極限と支配関係
2.10 演習問題
第3章 データ構造
3.1 連続データ構造と連結データ構造
3.1.1 配列
3.1.2 ポインタと連結構造
3.1.3 比較
3.2 スタックとキュー
3.3 辞書
3.4 2分探索木
3.4.1 2分探索木の実装
3.4.2 2分探索木はどれほどよいか？
3.4.3 平衡探索木
3.5 優先順位付きキュー
3.6 ボクの設計奮戦記：三角形を連ねる
3.7 ハッシングと文字列
3.7.1 衝突の回避
3.7.2 ハッシングを用いた効率的な文字列マッチング
3.7.3 ハッシングによる重複検出
3.8 特定目的のデータ構造
3.9 ボクの設計奮戦記：数珠つなぎ
3.10 演習問題
第4章 ソートと探索
4.1 ソートの応用
4.2 ソートの実際
4.3 ヒープソート：データ構造による高速ソート
4.3.1 ヒープ
4.3.2 ヒープを構成する
4.3.3 最小要素を取り出す
4.3.4 ヒープのより高速な構成法(*)
4.3.5 逐次挿入によるソート
4.4 ボクの設計奮戦記：飛行機のチケットをくれないか
4.5 マージソート：分割統治法によるソート
4.6 クイックソート：ランダム化によるソート
4.6.1 直観：クイックソートの平均の場合
4.6.2 ランダム化アルゴリズム
4.6.3 クイックソートは本当にクイック？
4.7 分配ソート：バケットを用いたそーと
4.7.1 ソートの下界
4.8 ボクの設計奮戦記：スキーナの抗弁
4.9 2分探索と関連アルゴリズム
4.9.1 出現の数え上げ
4.9.2 片側2分探索
4.9.3 平方根とその他の根
4.10 分割統治法
4.10.1 再帰式
4.10.2 分割統治法の再帰式
4.10.3 分割統治法の再帰式を解く(*)
4.11 演習問題
第5章 グラフ横断
5.1 グラフの特徴
5.1.1 交友グラフ
5.2 グラフのデータ構造
5.3 ボクの設計奮戦記：ボクはムーアの法則の犠牲者だった
5.4 ボクの設計奮戦記：グラフを手に入れる
5.5 グラフの横断
5.6 幅優先探索
5.6.1 横断を活用する
5.6.2 経路の発見
5.7 幅優先探索の応用
5.7.1 連結性分
5.7.2 2彩色グラフ
5.8 深さ優先探索
5.9 深さ優先探索の応用
5.9.1 閉路を見つける
5.9.2 関節点
5.10 有向グラフでの深さ優先探索
5.10.1 位相的ソート
5.10.2 強連結成分
5.11 演習問題
第6章 重み付きグラフのアルゴリズム
6.1 最小スパニングの木
6.1.1 プリムのアルゴリズム
6.1.2 クラスカルのアルゴリズム
6.1.3 union-findデータ構造
6.1.4 最小スパニング木の変種
6.2 ボクの設計奮戦記：ネットさえあればいい
6.3 最短経路
6.3.1 ダイクストラのアルゴリズム
6.3.2 全ペア最短経路
6.3.3 推移的閉包
6.4 ボクの設計奮戦記：電話で文書を作る
6.5 ネットワークフローと2部マッチング
6.5.1 2部マッチング
6.5.2 ネットワークフローの計算
6.6 アルゴリズムではなくグラフの設計
6.7 演習問題
第7章 組合せ探索とヒューリスティックな方法
7.1 バックトラック法
7.1.1 すべての部分集合を構成する
7.1.2 すべての順列を構成する
7.1.3 グラフのすべての経路を構成する
7.2 探索の枝刈り
7.3 数独
7.4 ボクの設計奮戦記：チェスボードを被覆する
7.5 ヒューリスティックな探索法
7.5.1 ランダムサンプリング
7.5.2 局所探索
7.5.3 シミュレーテッドアニーリング
7.5.4 シミュレーテッドアニーリングの応用
7.6 ボクの設計奮戦記：ラジオでないだけ
7.7 ボクの設計奮戦記：配列のアニーリング
7.8 他のヒューリスティックな探索法
7.9 並列アルゴリズム
7.10 ボクの設計奮戦記：速くったってどうしようもない
7.11 演習問題
第8章 動的計画法
8.1 キャッシング対計算
8.1.1 再帰によるフィボナッチ数
8.1.2 キャッシングによるフィボナッチ数
8.1.3 動的計画法によるフィボナッチ数
8.1.4 2項係数
8.2 近似文字列マッチング
8.2.1 再帰による編集距離
8.2.2 動的計画法による編集距離
8.2.3 経路の再構成
8.2.4 さまざまな編集距離
8.3 最長増加列
8.4 ボクの設計奮戦記：ロブスターの進化
8.5 分割問題
8.6 文脈自由文法の構文解析
8.6.1 最小重み三角分割
8.7 動的計画法の限界：TSP
8.7.1 動的計画法のアルゴリズムが正しいのはどのようなときか？
8.7.2 動的計画法はどのようなときに効率がよいのか？
8.8 ボクの設計奮戦記：過去はただのProlog
8.9 ボクの設計奮戦記：バーコードのためのテキスト圧縮
8.10 演習問題
第9章 手に負えない問題と近似アルゴリズム
9.1 問題と帰着
9.1.1 鍵となるアイデア
9.1.2 決定問題
9.2 アルゴリズムのための帰着
9.2.1 最近接ペア
9.2.2 最長増加部分列
9.2.3 最小公倍数
9.2.4 凸包(*)
9.3 初等的な困難性の帰着
9.3.1 ハミルトン閉路問題
9.3.2 独立集合問題と頂点被覆問題
9.3.3 クリーク問題
9.4 充足可能性問題
9.4.1 3-充足可能性問題
9.5 創造的な帰着
9.5.1 整数計画問題
9.5.2 頂点被覆問題
9.6 困難性証明のコツ
9.7 ボクの設計奮戦記：時計との困難な戦い
9.8 ボクの設計奮戦記：その後の失敗
9.9 P対NP
9.9.1 検証対発見
9.9.2 クラスPとクラスNP
9.9.3 なぜ充足可能性問題はすべての困難問題の母なのか？
9.9.4 NP困難対NP完全？
9.10 NP完全問題への対処
9.10.1 頂点被覆の近似
9.10.2 ユークリッド巡回セールスマン問題
9.10.3 最大非閉路部分グラフ
9.10.4 集合被覆問題
9.11 演習問題
第10章 どのようにしてアルゴリズムを設計するか
索引