アルゴリズム

アルゴリズム入門 [新装版] 設計と解析

Sara Baase

ピアソンエデュケーション

まえがき

  • 目的
  • 前提条件
  • 第1版からの変更点
  • 教育上改良された点
  • プログラム
  • コースの概要
  • 参考文献
  • 謝辞

訳者まえがき

第1章 アルゴリズムと問題の解析:原理と例

  • 1.1 はじめに
  • 1.2 アルゴリズム言語,数学,データ構造
    • 1.2.1 アルゴリズム言語
    • 1.2.2 数学的予備知識
    • 1.2.3 データ構造
  • 1.3 アルゴリズムと問題の解析
    • 1.3.1 はじめに
    • 1.3.2 正当性
    • 1.3.3 仕事量
    • 1.3.4 平均と最悪の場合の解析
    • 1.3.5 領域の使用
    • 1.3.6 単純さ
    • 1.3.7 最適性
    • 1.3.8 下界と問題の複雑度
    • 1.3.9 実現とプログラミング
  • 1.4 成長の度合いによる関数の分類
    • 1.4.1 定義と表記
    • 1.4.2 オーダーがいかに重要か
    • 1.4.3 Ο,Ω,Θの性質
  • 1.5 順序つきリストの探索
    • 1.5.1 問題といくつかの解法
    • 1.5.2 二分探索の最悪の場合の解析
    • 1.5.3 平均的挙動の解析
    • 1.5.4 最適性
  • 練習問題
    • 第1.2節:アルゴリズム言語,数学,データ構造
    • 第1.3節:アルゴリズムを解析する
    • 第1.4節:成長の度合いによる関数の分類
    • 第1.5節:順序つきリストを探索する
    • 追加の問題
  • ノートと参考文献

第2章 ソート

  • 2.1 はじめに
  • 2.2 挿入ソート
    • 2.2.1 考え方
    • 2.2.2 最悪の場合
    • 2.2.3 平均的振る舞い
    • 2.2.4 記憶容量
    • 2.2.5 ある種のソートアルゴリズムの下界
  • 2.3 クイックソートとマージソート:分割統治法
    • 2.3.1 分割統治法への導入
    • 2.3.2 クイックソートの戦略
    • 2.3.3 クイックソートの解析
    • 2.3.4 基本クイックソートの改良
    • 2.3.5 分割統治法
    • 2.3.6 ソート済みリストのマージ
    • 2.3.7 マージソート
  • 2.4 キー比較によるソートの下界
    • 2.4.1 ソートアルゴリズムの決定木
    • 2.4.2 最悪の場合の下界
    • 2.4.3 平均的振る舞いの下界
  • 2.5 ヒープソート
    • 2.5.1 ヒープ
    • 2.5.2 ヒープソートの戦略
    • 2.5.3 FixHeap
    • 2.5.4 ヒープの構成
    • 2.5.5 ヒープとヒープソートアルゴリズムの実現方法
    • 2.5.6 最悪の場合の解析
    • 2.5.7 注意
  • 2.6 シェルソート
    • 2.6.1 アルゴリズム
    • 2.6.2 解析と注意
  • 2.7 基数ソート
    • 2.7.1 キーの性質を用いる
    • 2.7.2 基数ソート
  • 2.8 外部ソート
    • 2.8.1 問題
    • 2.8.2 ポリフェーズマージソート
    • 2.8.3 置き換え選択による連の構成
    • 2.8.4 アルゴリズム2.15の解析
    • 2.8.5 3本のテープを用いたポリフェーズマージ
    • 2.8.6 マージのための連の並べ方
  • 練習問題
    • 第2.1節:はじめに
    • 第2.2節:挿入ソート
    • 第2.3節:クイックソートとマージソート:分割統治法
    • 第2.4節:キー比較によるソートの下界
    • 第2.5節:ヒープソート
    • 第2.7節:基数ソート
    • 第2.8節:外部ソート
    • 追加問題
  • プログラム
  • ノートと参考文献

第3章 択問題と敵対者の議論

  • 3.1 はじめに
    • 3.1.1 選択問題
    • 3.1.2 下界
  • 3.2 最大と最小を見つける
  • 3.3 2番目に大きいキーを見つける
    • 3.3.1 はじめに
    • 3.3.2 トーナメント法
    • 3.3.3 敵対者の議論による下界
    • 3.3.4 maxとsecondLargestを見つけるトーナメント法の実現方法
  • 3.4 選択問題
    • 3.4.1 選択アルゴリズム
    • 3.4.2 選択アルゴリズムの解析
  • 3.5 メディアンを見つける下界
  • 練習問題
    • 第3.1節:はじめに
    • 第3.2節:最大と最小を求める
    • 第3.3節:2番目に大きいキーを見つける
    • 第3.4節:選択問題
    • 第3.5節:メディアンを見つける下界
    • その他の問題
  • ノートと参考文献

第4章 グラフとダイグラフ

  • 4.1 定義と表記法
    • 4.1.1 初歩的定義と実例
    • 4.1.2 グラフおよびダイグラフの計算機上の表現法
  • 4.2 最小木アルゴリズム
    • 4.2.1 定義とアルゴリズムの概観
    • 4.2.2 プログラムによる実現
    • 4.2.3 解析(時間と領域)
    • 4.2.4 下界
  • 4.3 最短路アルゴリズム
    • 4.3.1 背景
    • 4.3.2 アルゴリズム
  • 4.4 グラフ,ダイグラフの探索
    • 4.4.1 深さ優先と幅優先探索
    • 4.4.2 深さ優先探索と再帰
    • 4.4.3 深さ優先探索のプログラムによる実現と解析:グラフの連結成分の発見
    • 4.4.4 深さ優先探索木
    • 4.4.5 深さ優先探索の一般的枠組み
  • 4.5 グラフの2連結成分
    • 4.5.1 間接点と2連結成分
    • 4.5.2 2連結成分アルゴリズム
    • 4.5.3 解析
    • 4.5.4 一般化
  • 4.6 ダイグラフの強連結成分
    • 4.6.1 定義
    • 4.6.2 強成分アルゴリズム
    • 4.6.3 解析
  • 練習問題
    • 第4.1節:定義と表現法
    • 第4.2節:最小木アルゴリズム
    • 第4.3節:最短路アルゴリズム
    • 第4.4節:グラフ,ダイグラフの探索
    • 第4.5節:グラフの2連結成分
    • 第4.6節:ダイグラフの強連結成分
    • 追加問題
  • プログラム
  • ノートと参考文献

第5章 文字列照合

  • 5.1 問題と直接的解法
  • 5.2 Knuth-Morris^Prattのアルゴリズム
    • 5.2.1 パターン照合と有限オートマトン
    • 5.2.2 Knuth-Morris-Prattのフローチャート
    • 5.2.3 Knuth-Morris-Prattフローチャートの構成
    • 5.2.4 フローチャート構成の解析
    • 5.2.5 Knuth-Morris-Pratt走査アルゴリズム
  • 5.3 Boyer-Mooreアルゴリズム
    • 5.3.1 新しいアイデア
    • 5.3.2 "古い"アイデアの併合
    • 5.3.3 Boyer-Mooreの走査アルゴリズム
    • 5.3.4 注意
  • 練習問題
    • 第5.1節:問題と直接解法
    • 第5.2節:Knuth-Morris-Prattのアルゴリズム
    • 第5.3節:Boyer-Mooreのアルゴリズム
    • 追加問題
  • プログラム
  • ノートと参考文献

第6章 動的計算法

  • 6.1 まえがき
  • 6.2 行列の積と最適二分探索木
    • 6.2.1 行列の連続積
    • 6.2.2 最適二分探索木の構成
  • 6.3 近似列照合
  • 6.4 グラフおよびダイグラフの距離
  • 6.5 動的計画アルゴリズムを開発に関する注意
  • 練習問題
    • 第6.2節:行列の積と最適二分探索木
    • 第6.3節:文字列の近似的照合
    • 第6.4 グラフおよびダイグラフの距離
    • 追加問題
  • プログラム
  • ノートと参考文献

第7章 多項式と行列

  • 7.1 はじめに
  • 7.2 多項式関数の評価
    • 7.2.1 アルゴリズム
    • 7.2.2 多項式評価の下界
    • 7.2.3 係数の前処理
  • 7.3 ベクトルと行列の積
    • 7.3.1 標準的アルゴリズムの概観
    • 7.3.2 ウィノグラードの行列乗算法
    • 7.3.3 行列の積の下界
    • 7.3.4 ストラッセンによる行列積の方法
  • 7.4 高速フーリエ変換と畳み込み
    • 7.4.1 はじめに
    • 7.4.2 高速フーリエ変換
    • 7.4.3 畳み込み
    • 7.4.4 付録:複素数と1の複素根
  • 練習問題
    • 第7.2節:多項式関数の評価
    • 第7.3節:ベクトルと行列の掛け算
    • 第7.4節:高速フーリエ変換と畳み込み
    • 追加の問題
  • プログラム
  • ノートと参考文献

第8章 推移的閉包、プール行列、同値関係

  • 8.1 2項関係の推移的閉包
    • 8.1.1 定義と背景
    • 8.1.2 深さ優先探索による可達行列の計算
  • 8.2 Warshallのアルゴリズム
    • 8.2.1 推移的閉包を求めるWarshallのアルゴリズム
    • 8.2.2 Warshallのアルゴリズムの拡張
    • 8.2.3 ビット行列に対するWarshallのアルゴリズム
  • 8.3 行列演算による推移的閉包の計算
  • 8.4 ビット行列の積-Kronrodのアルゴリズム
    • 8.4.1 まえがき
    • 8.4.2 Kronrodのアルゴリズム
    • 8.4.3 下界
  • 8.5 動的同値関係とUnion-Findプログラム
    • 8.5.1 動的同値関係
    • 8.5.2 応用:Kruskalの最小木アルゴリズム
    • 8.5.3 素朴なプログラムによる実現
    • 8.5.4 Union-Findプログラム
    • 8.5.5 同値プログラムおよびKruskalのアルゴリズムに戻る
    • 8.5.6 その他の応用
  • 練習問題
    • 第8.1節:2項関係の推移的閉包
    • 第8.2節:Warshallのアルゴリズム
    • 第8.3節:行列演算による推移的閉包の計算
    • 第8.4節:ビット行列の積-Kronrodのアルゴリズム
    • 第8.5節:動的同値関係とUnion-Findプログラム
    • 追加の問題
  • プログラム
  • ノートと参考文献

第9章 NP完全問題

  • 9.1 PとNP
    • 9.1.1 いくつかの問題例
    • 9.1.2 クラスP
    • 9.1.3 クラスNP
    • 9.1.4 入力のサイズ
  • 9.2 NP完全問題
    • 9.2.1 多項式帰着
    • 9.2.2 何が問題を難しくしているのか
    • 9.2.3 最適化問題と決定問題
  • 9.3 近似アルゴリズム
  • 9.4 箱詰め問題
    • 9.4.1 最初適合戦略
    • 9.4.2 他のヒューリスティックス
  • 9.5 ナップザック問題とサブセットサム問題
  • 9.6 グラフの彩色
    • 9.6.1 いくつかの基本技術
    • 9.6.2 グラフの近似彩色は困難である
    • 9.6.3 グラフの彩色アルゴリズム
  • 練習問題
    • 第9.1節:PとNP
    • 第9.2節:NP完全問題
    • 第9.3節:近似アルゴリズム
    • 第9.4節:箱詰め問題
    • 第9.5節:ナップザック問題とサブセットサム問題
    • 第9.6節:グラフの彩色
    • 追加問題
  • ノートと参考文献

第10章 並列アルゴリズム

  • 10.1 並列性,PRAM,その他のモデル
    • 10.1.1 はじめに
    • 10.1.2 PRAM
    • 10.1.3 その他のモデル
  • 10.2 いくつかのPRAMアルゴリズムと書き込み衝突の取り扱い
    • 10.2.1 二分ファンインテクニック
    • 10.2.2 いくつかの簡単に並列化可能なアルゴリズム
    • 10.2.3 書き込み衝突の解消
    • 10.2.4 最大値を計算する高速なアルゴリズム
  • 10.3 マージとソート
    • 10.3.1 はじめに
    • 10.3.2 並列マージ
    • 10.3.3 ソート
  • 10.4 並列連結成分アルゴリズム
    • 10.4.1 戦略とテクニック
    • 10.4.2 アルゴリズム
    • 10.4.3 アルゴリズムのPRAMでの実現
  • 10.5 下界
    • 10.5.1 論理関数を計算する
    • 10.5.2 nビット関数の計算の下界
  • 練習問題
    • 第10.2節:いくつかのPRAMアルゴリズムと書き込み衝突の取り扱い
    • 第10.3節:マージとソート
    • 第10.4節:並列連結成分アルゴリズム
    • 第10.5節:下界
    • 追加問題
  • ノートと参考文献

参考文献
アルゴリズム索引
索引

  • 人名索引
  • 項目索引(欧文)
  • 項目索引(和文)