アルゴリズム

アルゴリズムとデータ構造 (基礎のツールボックス)

K. メールホルン
S. サンダース
丸善出版

第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 役に立つ公式

参考文献
訳者あとがき
人名索引
事項索引