contents memorandum はてな

目次とメモを置いとく場

『アルゴリズムクイックリファレンス 第2版』(George T. Heineman, Gary Pollice, Stanley Selkow[著] 黒川利明, 黒川洋[訳] オライリージャパン 2016//2016)

原題:Algorithms in a Nutshell, Second Edition. (O'Reilly)
著者:George T. Heineman 計算機科学。ソフトウェア工学
著者:Gary F. Pollice ソフトウェア工学
著者:Stanley M. Selkow 計算機科学(グラフ理論アルゴリズム設計)。
訳者:黒川 利明(1948-)
訳者:黒川 洋
件名:アルゴリズム
NDLC:M159
NDC:007.64 情報科学
備考:本文に例示されるコードは、Javaのほか、C言語、Pyhton、疑似言語で書かれている。


O'Reilly Japan - アルゴリズムクイックリファレンス


【目次】
コロフォン [iv]
第2版日本語版へ寄せて(2016年11月 George T. Heineman Gary Pollice Stanley Selkow) [v-vi]
第2版まえがき [vii-xi]
  第2版の変更点
  対象読者
  本書で使用する記法
  コード例の使用について
  コメントや質問
  謝辞
目次 [xiii-xxi]


1章 アルゴリズムで考える
  1.1 問題を理解する 001
  1.2 素朴解 003
  1.3 賢い方式 003
    1.3.1 貪欲法
    1.3.2 分割統治法
    1.3.3 並列法
    1.3.4 近似法
    1.3.5 一般化
  1.4 まとめ 007
  1.5 参考文献 008


2章 アルゴリズムの数学
  2.1 問題インスタンスのサイズ 009
  2.2 関数の成長率 010
  2.3 最良、平均、最悪時の分析 015
    2.3.1 最悪時
    2.3.2 平均時
    2.3.3 最良時
    2.3.4 下限と上限
  2.4 性能分類 020
    2.4.1 定数的振る舞い
    2.4.2 対数的振る舞い
    2.4.3 d<1に対する下位線形 O(n^d)の振る舞い
    2.4.4 線形性能
    2.4.5 線形対数(nlog n)の性能
    2.4.6 二乗の性能
    2.4.7 あまり明白でない性能を示す計算
    2.4.8 指数性能
    2.4.9 漸近的成長のまとめ
  2.5 ベンチマーク演算 033
  2.6 参考文献 035


3章 アルゴリズムの構成要素
  3.1 アルゴリズムテンプレートの形式 038
  3.2 疑似コードのテンプレート形式 039
  3.3 評価実験の形式 040
  3.4 浮動小数点計算 040
    3.4.1 性能
    3.4.2 丸め誤差
    3.4.3 浮動小数点数値の比較
    3.4.4 特殊な値
  3.5 アルゴリズム例 044
    3.5.1 名前と概要
    3.5.2 入出力
    3.5.3 文脈
    3.5.4 解
    3.5.5 分析
  3.6 一般的なアプローチ 049
    3.6.1 貪欲法
    3.6.2 分割統治
    3.6.3 動的計画法
  3.7 参考文献 056


4章 整列アルゴリズム
    4.0.1 用語
    4.0.2 表現
    4.0.3 比較可能な要素
    4.0.4 安定整列
    4.0.5 整列アルゴリズムの選択基準
  4.1 転置ソート 061
    4.1.1 挿入ソート
    4.1.2 文脈
    4.1.3 解
    4.1.4 分析
  4.2 選択ソート 066
  4.3 ヒープソート 067
    4.3.1 文脈
    4.3.2 解
    4.3.3 分析
    4.3.4 変形
  4.4 分割ベースのソート 074
    4.4.1 文脈
    4.4.2 解
    4.4.3 分析
    4.4.4 変形
      4.4.4.1 ピボット選択
      4.4.4.2 分割処理
      4.4.4.3 部分配列の処理
      4.4.4.4 小さな部分配列には、より単純な挿入ソート技法を用いる
      4.4.4.5 イントロソート
  4.5 比較なしの整列 082
  4.6 バケツソート[Bucket Sort] 082
    4.6.1 解
    4.6.2 分析
    4.6.3 変形
  4.7 外部ストレージのある整列 089
    4.7.1 マージソート
    4.7.2 入出力
    4.7.3 解
    4.7.4 分析
    4.7.5 変形
  4.8 整列ベンチマーク結果 094
  4.9 分析技法 096
  4.10 参考文献 098


5章 探索
  5.1 逐次探索 102
    5.1.1 入出力
    5.1.2 文脈
    5.1.3 解
    5.1.4 分析
  5.2 二分探索 106
    5.2.1 入出力
    5.2.2 文脈
    5.2.3 解
    5.2.4 分析
    5.2.5 変形
  5.3 ハッシュに基づいた探索 111
    5.3.1 入出力
    5.3.2 文脈
    5.3.3 解
    5.3.4 分析
    5.3.5 変形
  5.4 ブルームフィルタ 127
    5.4.1 入出力
    5.4.2 文脈
    5.4.3 解
    5.4.4 分析
  5.5 二分探索木 132
    5.5.1 入出力
    5.5.2 文脈
    5.5.3 解
    5.5.4 分析
    5.5.5 変形
  5.6 参考文献 146


6章 グラフアルゴリズム
  6.1 グラフ 151
    6.1.1 データ構造の設計
  6.2 深さ優先探索 154
    6.2.1 入出力
    6.2.2 文脈
    6.2.3 解
    6.2.4 分析
    6.2.5 変形
  6.3 幅優先探索 160
    6.3.1 入出力
    6.3.2 文脈
    6.3.3 解
    6.3.4 分析
  6.4 単一始点最短経路 165
    6.4.1 入出力
    6.4.2 解
    6.4.3 分析
  6.5 密グラフ用ダイクストラ法 170
    6.5.1 変形
  6.6 単一始点最短経路選択肢の比較 177
    6.6.1 ベンチマークデータ
    6.6.2 密グラフ
    6.6.3 疎グラフ
  6.7 全対最短経路 179
    6.7.1 入出力
    6.7.2 解
    6.7.3 分析
  6.8 最小被覆木アルゴリズム 184
    6.8.1 入出力
    6.8.2 解
    6.8.3 分析
    6.8.4 変形
  6.9 グラフについての考察 188
    6.9.1 ストレージの問題
    6.9.2 グラフ分析
  6.10 参考文献 190


7章 AIにおける経路探索
  7.1 ゲーム木 192
    7.1.1 静的評価関数
  7.2 経路探索の概念 196
    7.2.1 状態の表現
    7.2.2 可能な手の計算
    7.2.3 拡張深さの限度
  7.3 ミニマックス 198
    7.3.1 入出力
    7.3.2 文脈
    7.3.3 解
    7.3.4 分析
  7.4 ネグマックス 204
    7.4.1 解
    7.4.2 分析
  7.5 アルファベータ法 208
    7.5.1 解
    7.5.2 分析
  7.6 探索木 216
    7.6.1 経路長のヒューリスティック関数
  7.7 深さ優先探索 220
    7.7.1 入出力
    7.7.2 文脈
    7.7.3 解
    7.7.4 分析
  7.8 幅優先探索 226
    7.8.1 入出力
    7.8.2 文脈
    7.8.3 解
    7.8.4 分析
  7.9  A*探索 229
    7.9.1 入出力
    7.9.2 文脈
    7.9.3 解
    7.9.4 分析
    7.9.5 変形
  7.10 探索木アルゴリズムの比較 240
  7.11 参考文献 243


8章 ネットワークフローアルゴリズム
  8.1 ネットワークフロー 248
  8.2 最大フロー 251
    8.2.1 入出力
    8.2.2 解
    8.2.3 分析
    8.2.4 最適化
    8.2.5 関連アルゴリズム
  8.3 二部マッチング 263
    8.3.1 入出力
    8.3.2 解
    8.3.3 分析
  8.4 増加道についての考察 267
  8.5 最小コストフロー 271
  8.6 積み替え 273
    8.6.1 解
  8.7 輸送 275
    8.7.1 解
  8.8 割り当て 276
    8.8.1 解
  8.9 線形計画法 276
  8.10 参考文献 277


9章 計算幾何学
  9.1 問題の分類 280
    9.1.1 入力データ
    9.1.2 計算
    9.1.3 タスクの性質
    9.1.4 仮定
  9.2 凸包 283
  9.3 凸包走査 284
    9.3.1 入出力
    9.3.2 文脈
    9.3.3 解
    9.3.4 分析
    9.3.5 変形
  9.4 線分交差を計算する 293
  9.5 線分走査法 294
    9.5.1 入出力
    9.5.2 文脈
    9.5.3 解
    9.5.4 分析
    9.5.5 変形
  9.6 ボロノイ図 304
    9.6.1 入出力
    9.6.2 解
    9.6.3 分析
  9.7 参考文献 317


10章 空間木構造
  10.1 最近傍クエリ 320
  10.2 範囲クエリ 321
  10.3 交差クエリ 321
  10.4 空間木構造 322
    10.4.1 k-d木
    10.4.2 四分木
    10.4.3 R木
  10.5 最近傍法 325
    10.5.1 入出力
    10.5.2 文脈
    10.5.3 解
    10.5.4 分析
    10.5.5 変形
  10.6 範囲クエリ 336
    10.6.1 入出力
    10.6.2 文脈
    10.6.3 解
    10.6.4 分析
  10.7 四分木 343
    10.7.1 入出力
    10.7.2 解
    10.7.3 分析
    10.7.4 変形
    10.8.1 入出力
    10.8.2 文脈
    10.8.3 解
    10.8.4 分析
  10.9 参考文献 362


11章 新たな分類のアルゴリズム
  11.1 方式の種類 363
  11.2 近似アルゴリズム 364
    11.2.1 入出力
    11.2.2 文脈
    11.2.3 解
    11.2.4 分析
  11.3 並列アルゴリズム 370
  11.4 確率的アルゴリズム 375
    11.4.1 集合のサイズを推定する
    11.4.2 探索木のサイズを推定する
  11.5 参考文献 383


12章 結び:アルゴリズムの諸原則
  12.1 汝のデータを知れ 385
  12.2 問題を小さく分割せよ 386
  12.3 正しいデータ構造を選べ 387
  12.4 空間と時間のトレードオフを使え 389
  12.5 探索を構築せよ 390
  12.6 問題を別の問題に帰着させよ 390
  12.7 アルゴリズムを書くのは難しい、アルゴリズムをテストするのはさらに難しい 391
  12.8 可能なら近似解を受け入れよ 392
  12.9 性能を上げるために並列性を加えよ 393


付録A ベンチマーク
  A.1 統計の基礎 395
  A.2 例 397
    A.2.1 Javaベンチマーク
    A.2.2 Linuxベンチマーク
    A.2.3 Pythonベンチマーク
  A.3 報告 404
  A.4 精度 405


訳者あとがき [407-408]
索引 [409-415]
著訳者紹介 [416-417]