アルゴリズムの基礎
アルゴリズムの設計と効率解析の基本的な技法を系統的に学ぶための教科書。アルゴリズム設計の基本的な考え方と技法について丁寧な説明を行い，定理や補題にはきちんとした証明を与えた。また，再帰方程式の解法を詳しく説明した。
- ジャンル
- 発行年月日
- 1997/10/15
- 判型
- A5 上製
- ページ数
- 258ページ
- ISBN
- 978-4-339-02348-0
- 内容紹介
- 目次
アルゴリズムの設計と効率解析の基本的な技法を系統的に学ぶための教科書。アルゴリズム設計の基本的な考え方と技法について丁寧な説明を行い，定理や補題にはきちんとした証明を与えた。また，再帰方程式の解法を詳しく説明した。
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
参考文献
演習問題の解答
索引
