アルゴリズム設計とデータ構造
アルゴリズム設計とデータ構造 (ライブラリ情報学コア・テキスト)
サイエンス社
著者：平田富夫
まえがき
第1章 アルゴリズムの基本概念
1.1 ユークリッドの互除法
1.2 アルゴリズムの表現
1.2.1 簡易プログラミング言語
1.2.2 手続きと関数
1.2.3 再帰的手続き
1.3 アルゴリズムの例
1.4 計算時間の解析
1.4.1 実行ステップ数
1.4.2 アルゴリズムの計算量
1.5 グラフ
1.5.1 根付き木
1.6 基本データ構造
1.6.1 リスト
1.6.2 スタック
1.6.3 キュー
演習問題
第2章 ソーティング
2.1 バブルソート
2.2 挿入法とシェルソート
2.3 選択法とヒープソート
2.3.1 ヒープ
2.3.2 ヒープソート
2.3.3 入力配列のヒープ化
2.4 マージソート
2.4.1 マージ
2.4.2 再帰的アルゴリズムの構成
2.4.3 再帰的アルゴリズムの理解
2.4.4 マージソートの解析
2.5 クイックソート
2.5.1 クイックソートの原理
2.5.2 計算時間の解析
2.5.3 実用上有用な改良
2.5.4 平均解析
2.5.5 確率的アルゴリズム
2.5.6 プログラムヘの実装
2.5.7 使用記憶領域
2.6 ソーティング計算量の下界
2.7 バケットソート
2.7.1 辞書式順序によるソーティング
2.8 選択アルゴリズム
演習問題
第3章 データ探索
3.1 逐次探索
3.2 2分探索
3.3 2分探索木
3.3.1 2分木の平均解析
3.4 2色木
3.5 最適2分探索木
3.6 ハッシング
演習問題
第4章 文字列マッチング
4.1 ストリングマッチング
4.1.1 素朴なアルゴリズム
4.1.2 2DPDA
4.1.3 KMPアルゴリズム
4.2 マッチングオートマトン
4.3 最長共通部分列
演習問題
第5章 高速フーリエ変換アルゴリズム
5.1 離散フーリエ変換
5.2 たたみ込み
5.3 高速フーリエ変換のアルゴリズム
5.3.1 ビット反転順
5.3.2 逆離散フーリエ変換
演習問題
第6章 グラフアルゴリズム
6.1 グラフ表現のためのデータ構造
6.2 深さ優先探索と幅優先探索
6.3 木の探索
6.3.1 2分木の探索
6.3.2 -般の木の探索
6.4 最短路アルゴリズム
6.4.1 ダイクストラのアルゴリズム
6.4.2 全ペア最短路
6.5 最小スパニング木
6.5.1 Union-Find問題
6.6 2連結成分アルゴリズム
6.6.1 強連結成分
6.7 ネットワークフロー
6.7.1 2部グラフのマッチング
演習問題
第7章 アルゴリズムの設計法
7.1 分割統治法
7.2 動的計画法
7.3 グリーディ法
演習問題
第8章 NP完全問題
8.1 計算が困難な問題
8.2 計算が困難な問題の特徴
8.2.1 “yes"と"no"の非対象性
8.3 NP完全問題の定義
8.3.1 計算のモデル
8.3.2 クラスP
8.3.3 クラスNP
8.3.4 多項式時間帰着
8.4 SATのNP完全性
8.4.1 SATから3-SATへの変換
8.5 種々のNP完全問題
8.6 決定問題と最適化問題
8.7 NP完全問題への対応
演習問題
参考文献
索引