アルゴリズムの基礎とデータ構造 数理とCプログラム
近代科学社
著者：浅野孝夫
はじめに
第1章 アルゴリズムの基礎概念
1.1 アルゴリズムの計算量
1.1.1 多項式の値の計算
1.1.2 ソーティング
1.1.3 最大計算量
1.2 漸近計算量Ｏ-,Ω-,Θ-記法
1.2.1 漸近計算量の妥当性
1.3 素朴なアルゴリズムの計算量
1.3.1 多項式の積
1.3.2 行列の積
1.4 難しい問題
1.4.1 部分集合和問題とナップザック問題
1.4.2 巡回セールスマン問題
1.5 解答付き演習問題
1.6 演習問題
第2章 根付き木と再帰法
2.1 グラフと木
2.1.1 グラフの基礎概念
2.1.2 根付き木
2.2 再帰法
2.2.1 非負整数a,bの最大公約数GCD(a,b)の計算
2.2.2 ユークリッド互除法のプログラム例
2.2.3 フィボナッチ数の計算
2.3 根付き木のラベリング
2.4 発展：拡張ユークリッド互除法
2.4.1 拡張ユークリッド互除法のプログラム例
2.5 演習問題
第3章 ソーティング
3.1 ソーティングアルゴリズム
3.2 マージソート
3.2.1 マージソートの定期用例
3.2.2 マージソートの計算量解析
3.2.3 マージソートのプログラム例
3.3 クイックソート
3.3.1 クイックソートの適用例
3.3.2 クイックソートの計算量解析
3.3.3 クイックソートの実際的工夫
3.3.4クイックソートのプログラム例
3.4 基数ソート(ラディックスソート)
3.4.1 基数ソートの正当性と計算量
3.4.2 基数ソートのプログラム例
3.5 ソーティングの計算量の下界
3.6 解答付き演習問題
3.7 演習問題
第4章 基本データ構造1：配列とヒープ
4.1 辞書と優先度付きキュー
4.2 優先度付きキューとヒープ
4.3 ヒープ構成の計算量
4.4 ヒープソート
4.5 ヒープソートのプログラム例
4.6 解答付き演習問題
4.7 演習問題
第5章 基本データ構造2：配列とリスト
5.1 辞書
5.2 二分探索と2倍探索
5.2.1 二分探索
5.2.2 2倍探索
5.3 辞書とリスト
5.4 リストの変種
5.4.1 スタックとキュー
5.4.2 スタックとキューの配列による実現
5.4.3 スタックの応用：逆ポーランド記法の式の計算
5.4.4 スタックとキューの応用：順序木のラベリング
5.5 リストの配列による実現
5.6 配列の領域管理を用いたリストの実現
5.6.1 実行例
5.7 リストのプログラム例
5.8 根付き木表現のデータ構造
5.9 先行順・後行順・幅優先順ラベリングのプログラム例
5.10 解答付き演習問題
5.11 演習問題
第6章 基本データ構造3：配列と二分探索木
6.1 二分探索木
6.1.1 二分探索木と対称順
6.1.2 二分探索木と更新例
6.2 二分探索木の平均的振舞い
6.3 二分探索木のプログラム例
6.4 演習問題
第7章 高速データ構造：配列と二色木
7.1 平衡探索木
7.2 二色木
7.2.1 二色木における挿入
7.2.2 二色木における削除
7.2.3 二色木の更新例
7.3 二色木のプログラム例
7.4 演習問題
第8章 基本データ構造4：配列とハッシング
8.1 ハッシング
8.2 チェーン法によるハッシング
8.3 普遍ハッシング：乱択化技法の応用
8.3.1 ハッシュ関数に要求される性質
8.3.2 要求される性質を満たすハッシュ関数のクラスℋ
8.3.3 ハッシュ関数のクラスℋの普遍的の証明
8.3.4 クラスℋを用いた普遍ハッシング
8.3.4 普遍ハッシングのプログラム例
8.4 演習問題
第9章 基本データ構造5：配列と集合ユニオン・ファインド森
9.1 集合ユニオン・ファインドデータ構造
9.2 単純な集合ユニオン・ファインドデータ構造
9.3 集合ユニオン・ファインド森
9.4 さらなる改善：パス圧縮
9.4.1 アッカーマン関数とその逆関数
9.4.2 集合ユニオン・ファインド森のならし計算
9.5 集合ユニオン・ファインド森のプログラム例
9.6 演習問題
第10章 データ構造の応用1：凸包
10.1 凸包の定義
10.2 点のx座標のソートに基づく凸包アルゴリズム
10.3 1点の回りでの偏角順に基づく凸包アルゴリズム
10.4 Grahamの凸包アルゴリズムのプログラム例
10.5 演習問題
第11章 データ構造の応用2：交差線分対列挙
11.1 平面走査法
11.2 一直線上の線分の交差線分対列挙
11.3 水平線分・垂直線分の交差線分対列挙
11.4 水平線分・垂直線分の交差線分対列挙のプログラム例
11.5 演習問題
第12章 データ構造の応用3：最小全点木
12.1 最小全点木を求めるKruskalのアルゴリズム
12.2 Kuruskalのアルゴリズムのプログラム例
12.3 演習問題
演習問題解答
参考文献
索引