アルゴリズムとデータ構造 基礎のツールボックス
丸善出版
著者：K.メールホルン、P.サンダース
訳者：浅野哲夫
まえがき
目次
第1章 食前酒 – 整数計算
1.1 和
1.2 乗算 – 学校式の計算法
1.3 結果の検証
1.4 学校式の計算法の再帰版
1.5 カラツバ乗算法
1.6 アルゴリズム工学
1.7 プログラム
1.8 補題1.5と定理1.7の証明
1.9 実装に関する注意
1.10 歴史に関するノートとその後の発展
第2章 序論
2.1 漸近記法
2.2 マシンモデル
2.3 擬似プログラム
2.4 正しいアルゴリズムとプログラムの設計
2.5 例 – 2分探索
2.6 アルゴリズム解析の基礎
2.7 平均時の解析
2.8 乱択のアルゴリズム
2.9 グラフ
2.10 PとNP
2.11 実装に関する注意
2.12 歴史に関するノートとその後の発展
第3章 配列と連結リストによる列の表現
3.1 連結リスト
3.2 サイズ制限のない配列
3.3 ならし解析*
3.4 スタックとキュー
3.5 リスト対配列
3.6 実装に関する注意
3.7 歴史に関するノートとその後の発展
第4章 ハッシュ表と連想配列
4.1 チェイニングを用いたハッシュ法
4.2 万能ハッシュ法
4.3 線形探査を用いたハッシュ法
4.4 チェイニング法対線形探査法
4.5 完全ハッシュ法*
4.6 実装に関する注意
4.7 歴史に関するノートとその後の発展
第5章 ソーティングと選択問題
5.1 簡単なソート法
5.2 マージソート – O(n log n)のソーティング・アルゴリズム
5.3 下界
5.4 クイックソート
5.5 選択問題
5.6 下界を破る
5.7 外部ソーティング*
5.8 実装に関する注意
5.9 歴史に関するノートとその後の発展
第6章 優先順位付きキュー
6.1 2分ヒープ
6.2 アドレス可能な優先順位付きキュー
6.3 外部記憶*
6.4 実装に関する注意
6.5 歴史に関するノートとその後の発展
第7章 ソート列
7.1 2分探索木
7.2 (a,b) – 木と2色木
7.3 その他の操作
7.4 更新操作のならし解析
7.5 探索木の補強
7.6 実装に関する注意
7.7 歴史に関するノートとその後の発展
第8章 グラフの表現
8.1 辺の非順序列
8.2 隣接配列 – 静的グラフ
8.3 隣接リスト – 動的グラフ
8.4 隣接行列表現
8.5 暗黙の表現
8.6 実装に関する注意
8.7 歴史に関するノートとその後の発展
第9章 グラフの走査
9.1 幅優先探索
9.2 深さ優先探索
9.3 実装に関する注意
9.4 歴史に関するノートとその後の発展
第10章 最短経路
10.1 基本的な概念から汎用アルゴリズムへ
10.2 有効非巡回グラフ
10.3 辺コストが非負の場合(ダイクストラのアルゴリズム)
10.4 ダイクストラ法の平均時解析*
10.5 単調な整数優先順位付きキュー
10.6 辺コストが任意の場合(ベルマン – フォードのアルゴリズム)
10.7 全点対間最短経路と接点ポテンシャル
10.8 最短経路問合せ
10.9 実装に関する注意
10.10 歴史に関するノートとその後の発展
第11章 最小全域木
11.1 カット条件と閉路条件
11.2 ヤルニック – プリムのアルゴリズム
11.3 クラスカルのアルゴリズム
11.4 統合 – 検索のデータ構造
11.5 外部記憶*
11.6 応用
11.7 実装に関する注意
11.8 歴史に関するノートとその後の発展
第12章 最適化のための汎用的な手法
12.1 線形計画法 – ブラックボックスの問題ソルバー
12.2 貪欲法 – 決して後を振り向かない
12.3 動的計画法 – 徐々に組み立てていく方式
12.4 組織的な探索 – 疑わしいときは腕力を使うこと
12.5 局所探索 – 思考は大局的に、行動は局所的に
12.6 進化アルゴリズム
12.7 実装に関する注意
12.8 歴史に関するノートとその後の発展
第13章 付録
A.1 数学記号
A.2 数学的概念
A.3 基本的な確率論
A.4 役に立つ公式
参考文献
訳者あとがき
人名索引
事項索引