アルゴリズム

アルゴリズムとデータ構造(岩波講座 ソフトウェア科学 3)

石畑清
岩波書店

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

  1. アルゴリズムとは何か
  2. アルゴリズムの正しさ
  3. アルゴリズムの証明の方法

1.2 アルゴリズムの計算量

  1. 計算量
  2. 例題
  3. 計算量の漸近的な評価
  4. O記法
  5. 漸近的計算量の重要性
  6. 計算量の各種の定義
  7. データ構造
  8. 計算のメカニズム
  9. 問題の大きさの限界
  10. アルゴリズムの選択

1.3 基本的データ構造

  1. 配列
  2. リスト
  3. 配列とリストの比較
  4. ポインターの添字表現
  5. 記憶域の割当て
  6. 各種のリスト
  7. スタック
  8. 待ち行列
  9. 木の表現法
  10. 木の走査

第1章のまとめ・演習問題1

2 探索
2.1 探索とそのアルゴリズム

  1. 用語の定義
  2. 探索アルゴリズムの計算量

2.2 線形探索

  1. 配列上の線形探索
  2. 番兵
  3. リストの線形探索
  4. 自己再構成リスト

2.3 2分探索

  1. 2分探索の原理
  2. 第1の方式
  3. 第2の方式
  4. 挿入と削除

2.4 2分探索木

  1. 2分探索木
  2. 2分探索木の挿入
  3. 計算量
  4. 2分探索木からの削除
  5. 末尾再帰呼出しの除法

2.5 平衡木

  1. AVL木
  2. AVL木の挿入
  3. プログラムとしての実現
  4. AVL木からの削除
  5. AVL木の評価
  6. AVL木以外の平衡木

2.6 B木

  1. B木の定義
  2. B木の探索
  3. B木への挿入
  4. プログラムとしての実現
  5. B木からの削除
  6. B木の効率と改良案
  7. 2次記憶装置上でのB木
  8. 2-3木

2.7 ハッシュ法

  1. ハッシュ法の考え方
  2. チェイン法
  3. ハッシュ関数
  4. チェイン法の計算量
  5. 開番地法、特に線形走査法
  6. その他の開番地法
  7. データの削除
  8. 開番地法の効率
  9. ハッシュ法の評価

2.8 その他の探索アルゴリズムと集合操作

  1. トライ
  2. 自己再構成木
  3. 集合操作

第2章のまとめ・演習問題2

3 整列
3.1 整列アルゴリズムの基礎

  1. 問題の定義
  2. 最も単純な整列アルゴリズム
  3. 選択法
  4. 挿入法
  5. 整列の計算量に関する理論的考察

3.2 シェルソート

  1. シェルソートの原理
  2. シェルソートの計算量

3.3 クイックソート

  1. クイックソートの原理
  2. クイックソートの簡単な実現法
  3. クイックソートの計算量
  4. 補助記憶域の大きさ
  5. 分割の高速化
  6. 誤ったプログラムの例
  7. 分割の別法
  8. 基準値の選び方
  9. 挿入法の併用
  10. 再帰呼出しの除去
  11. 決定版

3.4 ヒープソート

  1. マージ
  2. 単純マージソート
  3. トップダウン法
  4. 自然マージソート
  5. リストのマージソート
  6. 2次記憶上のデータの整列
  7. マージの各種の方法

3.6 比較以外の方法による整列

  1. ビンソート
  2. 基底法

第3章のまとめ・演習問題3

4 グラフのアルゴリズム
4.1 グラフとは何か

  1. 用語の定義
  2. グラフアルゴリズムの計算量

4.2 グラフの表現法

  1. 行列表現
  2. リスト表現
  3. 二つの表現法の比較

4.3 グラフの探索

  1. 深さ優先探索
  2. 無向グラフの場合
  3. 有向グラフの場合
  4. トポロジカルソート
  5. 幅優先探索
  6. 一般的な探索アルゴリズム

4.4 各種の連結性の判定

  1. 2重連結性
  2. 関節点検出のアルゴリズム
  3. 強連結性
  4. 強連結成分への分割アルゴリズム

4.5 最短路の問題

  1. 単一出発点の問題
  2. Dijkstraのアルゴリズムの単純な実現法
  3. ヒープを使ったDijkstraのアルゴリズムの実現法
  4. 全頂点間の問題
  5. 最短路問題の各種の解法
  6. グラフの推移的閉法

4.6 最小木の問題

  1. Primのアルゴリズム
  2. Kruskalのアルゴリズム
  3. 同値類の問題
  4. 同値類アルゴリズムの効率化
  5. 最小木アルゴリズムの計算量

4.7 グラフに関するその他のアルゴリズム

  1. 最大流問題
  2. グラフの平面性の判定
  3. グラフの同形性の判定
  4. グラフのマッチング

第4章のまとめ・演習問題4

5 文字列のアルゴリズム
5.1 文字列の照合

  1. 問題の定義
  2. 素朴なアルゴリズム
  3. Knuth-Morris-Prattのアルゴリズム
  4. Boyer-Mooreのアルゴリズム
  5. 作戦1
  6. 作戦2
  7. 表nextの簡単な計算法
  8. 表nextの高速計算法
  9. 作戦1と作戦2の統合

5.2 正規表現とのパターン照合

  1. 正規表現
  2. 問題の定義
  3. 有限オートマトン
  4. 決定性オートマトンと非決定性オートマトン
  5. 非決定性オートマトンによるパターン照合
  6. 非決定性オートマトンから決定性オートマトンへの変換
  7. 非決定性オートマトンと決定性オートマトンの比較
  8. 型や変数の宣言
  9. 正規表現の構文解析
  10. 非決定性オートマトンの生成
  11. 決定性オートマトンの生成
  12. テキストの照合
  13. プログラムの改良

第5章のまとめ・演習問題5

6 難しい問題
6.1 バックトラック法

  1. n女王問題
  2. バックトラック法
  3. バックトラック法の効率の改善
  4. 双方向リストを使った順列の生成

6.2 幅優先探索

  1. 8パズル
  2. 幅優先探索の手順
  3. 幅優先探索の所要記憶量
  4. 8パズルのプログラム

6.3 ゲームの木の探索

  1. ゲームの木
  2. ミニマックス法
  3. 評価関数
  4. α-β法

6.4 NP完全問題

  1. やさしい問題と難しい問題
  2. クラスPとNP
  3. NP完全問題

6.5 最適化問題の解法

  1. NP完全問題の厳密解法
  2. 分岐限定法
  3. ナップザック問題の分岐限定法による解法
  4. 動的計画法

6.6 近似アルゴリズム

  1. Euclid的巡回セールスマン問題
  2. 単純貪欲法
  3. 大局的貪欲法
  4. 挿入法
  5. 最小木法
  6. 局所探索法

第6章のまとめ・演習問題6

7 さまざまなアルゴリズム
7.1 アルゴリズムの設計技法

  1. 分割統治法
  2. 貪欲戦略
  3. ボトムアップかトップダウンか
  4. 動的計画法
  5. 表計算法
  6. 発見的方法

7.2 さまざまなアルゴリズム

  1. 並列アルゴリズム
  2. 確率アルゴリズム
  3. 記憶域の割当て
  4. 計算量の理論
  5. 諸分野のアルゴリズム

第7章のまとめ・演習問題7

付録 CとLispによるプログラム
演習問題の解答
参考書
事項索引
手続き名索引
プログラム一覧