アルゴリズム

入門 データ構造とアルゴリズム

Narasimha Karumanchi
オライリー・ジャパン

格言(動機づけと啓発のため)
謝辞

1章 はじめに

  1. 変数
  2. データ型
  3. データ構造
  4. 抽出データ型(ADT)
  5. アルゴリズムとは
  6. なぜアルゴリズムの解析なのか
  7. 実行時解析とは
  8. どのようにアルゴリズムを比較するのか
  9. 増加率とは
  10. 一般に用いられている増加率
  11. 解析の種類
  12. 漸近表記法
  13. 0表記法
  14. Ω表記
  15. Θ表記
  16. なぜ漸近的解析と呼ぶのか
  17. 漸近的解析のガイドライン
  18. 表記の特性
  19. よく使われる対数と和
  20. 分割統治マスター定理
  21. 分割統治マスター定理の問題
  22. 減算統治再帰(Subtract and Conquer Recurrences)マスター定理
  23. 減算統治再帰マスター定理の変形
  24. ならし解析
  25. アルゴリズム解析の問題

2章 再帰と後戻り

  1. はじめに
  2. 再帰とは
  3. 再帰関数の形式
  4. 再帰とメモリ(可視化)
  5. 再帰と反復
  6. 再帰に関する注意
  7. 再帰アルゴリズムの例
  8. 再帰の問題
  9. 後戻りとは
  10. 後戻りの問題

3章 連結リスト

  1. 連結リストとは
  2. 連結リストADT
  3. 連結リストを使う自由
  4. 配列の概観
  5. 連結リストの配列や動的配列との比較
  6. 単一連結リスト
  7. 二重連結リスト
  8. 循環連結リスト
  9. メモリ効率二重連結リスト
  10. 連結リストの問題

4章 スタック

  1. スタックとは
  2. スタックはどのように使われるか?
  3. スタックADT
  4. 応用
  5. 実装
  6. 実装の比較
  7. スタックの問題

5章 キュー

  1. キューとは
  2. キューはどのように使われるか
  3. キューADT
  4. 例外
  5. 応用
  6. 実装
  7. キューの問題

6章 木

  1. 木とは
  2. 木の用語
  3. 二分木
  4. 二分木の型
  5. 二分木の性質
  6. 二分来横断
  7. 一般木(N分木)
  8. スレッド二分木横断(スタック/キュー不要横断)
  9. 式木
  10. XOR木
  11. 二分探索木(BST)
  12. 平衡二分探索木
  13. AVL木
  14. 木の他の形式

7章 優先度付きキューとヒープ

  1. 優先度付きキューとは
  2. 優先度付きキューADT
  3. 優先度付きキューの実装
  4. ヒープ
  5. 二分ヒープ
  6. 優先度付きキュー(ヒープ)の問題

8章 互いに素な集合ADT

  1. はじめに
  2. 同値関係と同値類
  3. 互いに素な集合ADT
  4. 互いに素な集合ADT実装のトレードオフ
  5. まとめ
  6. 互いに素な集合の問題

9章 グラフアルゴリズム

  1. はじめに
  2. グラフとは
  3. グラフの適用例
  4. グラフ表現
  5. グラフ横断
  6. トポロジカルソート
  7. 最短経路アルゴリズム
  8. 最小全域木
  9. グラフアルゴリズムの問題

10章 整列

  1. 整列とは
  2. 分類
  3. その他の分類
  4. バブルソート
  5. 選択ソート
  6. 挿入ソート
  7. シェルソート
  8. マージソート
  9. ヒープソート
  10. クイックソート
  11. ツリーソート
  12. 整列アルゴリズムの比較
  13. 線形整列アルゴリズム
  14. 数え上げソート
  15. バケツソート(ビンソート)
  16. 基数ソート
  17. トポロジカルソート
  18. 外部整列
  19. 整列の問題

11章 探索

  1. 探索とは
  2. なぜ探索を行うのか?
  3. 順不同線形探索
  4. 整列/順序線形探索
  5. 二分探索
  6. 探索の問題

12章 選択アルゴリズム[中央値]

  1. 選択アルゴリズムとは
  2. 選択アルゴリズム
  3. 選択アルゴリズムの問題

13章 記号表

  1. はじめに
  2. 記号表とは
  3. 記号表の実装

14章 ハッシュ

  1. ハッシュとは
  2. ハッシュ表ADT
  3. ハッシュを理解する
  4. ハッシュの構成要素
  5. 衝突解消手法の比較
  6. ハッシュはどのようにして計算量O(1)を実現するのか?
  7. ハッシュ手法
  8. ハッシュの問題

15章 文字列アルゴリズム

  1. はじめに
  2. 文字列照合アルゴリズム
  3. 力任せ法
  4. ラビン・カープ文字列照合アルゴリズム
  5. 有限オートマトンを使った文字列照合
  6. KMPアルゴリズム
  7. ボイヤー・ムーアアルゴリズム
  8. 文字列を格納するためのデータ構造
  9. 文字列のためのハッシュ表
  10. 文字列のための二分探索木
  11. トライ
  12. 三分探索木(TST)
  13. 二分探索木、トライ、三分探索木の比較
  14. 接尾辞木
  15. 文字列に関する問題

16章 アルゴリズム設計技法

  1. はじめに
  2. 分類
  3. 実装方法による分類
  4. 設計方法による分類
  5. その他の分類

17章 貪欲アルゴリズム

  1. はじめに
  2. ハフマン符号化アルゴリズム
  3. 貪欲アルゴリズムの問題

18章 分割統治アルゴリズム

  1. はじめに
  2. 分割統治法の可視化
  3. 分割統治法を理解する
  4. 分割統治法の利点
  5. 分割統治法の欠点
  6. マスター定理
  7. 分割統治法の問題

19章 動的プログラミング

  1. はじめに
  2. 動的プログラミングの方法
  3. 動的プログラミングの例
  4. 動的プログラミングの問題

20章 計算量クラス

  1. はじめに
  2. 計算量クラスの種類
  3. 帰着/簡約
  4. 計算量クラスの問題

21章 その他の各種概念

  1. はじめに
  2. ビット単位プログラミング
  3. その他のプログラミング問題

参考文献
訳者あとがき
索引