アルゴリズム

アルゴリズム設計マニュアル 上

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章 どのようにしてアルゴリズムを設計するか

索引