アルゴリズム

アルゴリズムの基礎

五十嵐善英
西谷泰昭

コロナ社

1.アルゴリズムと計算量

  • 1.1 問題と問題例
  • 1.2 アルゴリズムの効率
  • 1.3 計算量
  • 1.4 計算量のオーダ

2.データ構造

  • 2.1 リスト
  • 2.2 スタックとキュー
  • 2.3 グラフとその表現
  • 2.4 木
  • 2.5 ヒープ
  • 2.6 集合の表現と演算

3.アルゴリズムの設計技法

  • 3.1 再帰法
  • 3.2 再帰方程式
  • 3.3 分割統治法
  • 3.4 動的計画法

4.ソーティング

  • 4.1 素朴なアルゴリズム
  • 4.2 決定木
  • 4.3 マージソート
  • 4.4 ヒープソート
  • 4.5 クイックソート
  • 4.6 バケットソート
  • 4.7 選択問題

5.集合操作

  • 5.1 2分探索法
  • 5.2 2分探索木
  • 5.3 最適2分探索木
  • 5.4 ハッシュ法
  • 5.5 直和所属問題

6.貪欲アルゴリズム

  • 6.1 仕事選択問題
  • 6.2 最小全域木
    • 6.2.1 クルスカルのアルゴリズム
    • 6.2.2 プリムのアルゴリズム
  • 6.3 グラフ彩色問題
  • 6.4 つり銭問題

7.グラフアルゴリズム

  • 7.1 グラフ探索
    • 7.1.1 深さ優先探索
    • 7.1.2 幅優先探索
  • 7.2 単一頂点からの最短経路
  • 7.3 すべての頂点間の最短経路
  • 7.4 最大流量
  • 7.5 2部グラフの最大マッチング

8.確率的アルゴリズム

  • 8.1 ランダム化の効果
  • 8.2 ラスベガスアルゴリズム
  • 8.3 モンテカルロアルゴリズム
  • 8.4 偏重モンテカルロアルゴリズム
  • 8.5 Rabinの素数判定アルゴリズム

9.文字列照合

  • 9.1 素朴なアルゴリズム
  • 9.2 Knuth-Morris-Prattのアルゴリズム
  • 9.3 Boyer-Mooreのアルゴリズム
  • 9.4 正規表現とのパターン照合

10.NP完全問題

  • 10.1 非決定性多項式時間
  • 10.2 多項式時間の変換
  • 10.3 Cookの定理
  • 10.4 NP完全問題の例

付録 PASCAL
参考文献
演習問題の解答
索引