アルゴリズム設計マニュアル 原書3版 上

発売日 : 2024年01月30日

著者／編集 : Steven S. Skiana/平田　富夫

出版社 : 丸善出版

発行形態 : 単行本

ページ数 : 608p

アルゴリズム設計の技法は計算機科学の中心にある実際的な技術である．本書は学生とコンピュータ技術者の両方に，組合せアルゴリズムの技術に触れてもらいアルゴリズム設計のマニュアルとなることを意図している．本書は技法とリソースの2部構成になっている．前者はコンピュータアルゴリズムの設計と解析への一般的な入門書であり，後者は，適宜拾い読みされ参照されることを目指しており，アルゴリズム資源のカタログと実装プログラム，広範にわたる参考文献からなる．上巻にあたる第I部では，ハッシング，ランダム化アルゴリズム，分割統治法，近似アルゴリズム，量子計算のような重要な話題を紹介する．本書ではアルゴリズムの数学的な解析は強調せず解析はインフォーマルな議論にとどめている．本マニュアルの目的は読者を正しい方向へとできるだけ敏速に導くことであり，詳細な議論が必要な時はプログラムや参考文献を調べられるよう引用している．

序文目次第I部　実用的なアルゴリズムの設計第1章　アルゴリズム設計への導入1.1 ロボット経路の最適化1.2 適切な仕事の選択1.3 正しさの論証1.4 帰納法と再帰1.5 問題のモデル化1.6 背理法による証明1.7 設計奮戦記について1.8 設計奮戦記：超能力のモデル化1.9 推定1.10 演習問題第2章　アルゴリズム解析2.1 計算のRAMモデル2.2 ビッグオー記法2.3 増加率と支配関係2.4 ビッグオーを使いこなす2.5 効率に関する議論2.6 総和2.7 対数とその応用2.8 対数の性質2.9 設計奮戦記：ピラミッドの謎2.10 高度な解析2.11 演習問題第3章　データ構造3.1 連続構造と連結構造3.2 コンテナ：スタックとキュー3.3 辞書3.4 2分探索木3.5 優先順位付きキュー3.6 設計奮戦記：三角形を連ねる3.7 ハッシング3.8 特定目的のデータ構造3.9 設計奮戦記：数珠つなぎ3.10 演習問題第4章　ソート4.1 ソートの応用4.2 ソートの実際4.3 ヒープソート：データ構造による高速ソート4.4 設計奮戦記：飛行機のチケットをくれないか4.5 マージソート：分割統治法によるソート4.6 クイックソート：ランダム化によるソート4.7 分配ソート：バケットを用いたソート4.8 設計奮戦記：スキーナの抗弁4.9 演習問題第5章　分割統治法5.1 2分探索と関連アルゴリズム5.2 設計奮戦記：バグの中にバグを見つける5.3 再帰式5.4 分割統治法の再帰式を解く5.5 高速乗算5.6 最大部分範囲と最接近ペア5.7 並列アルゴリズム5.8 設計奮戦記：速くたってどうしようもない5.9 たたみ込み5.10 演習問題第6章　ハッシングとランダム化アルゴリズム6.1 確率論の復習6.2 ボールとビン問題を理解する6.3 ハッシングはなぜンダム化アルゴリズムなのか？6.4 ブルームフィルタ6.5 誕生日パラドックスと完全ハッシング6.6 Minwiseハッシング6.7 効率的な文字列マッチング6.8 素数判定6.9 クヌースにミドルイニシャルを伝える6.10 乱数はどこから来るか6.11 演習問題第7章　グラフの横断7.1 グラフの特徴7.2 グラフのデータ構造7.3 設計奮戦記：私はムーアの法則の犠牲者だった7.4 設計奮戦記：グラフを手に入れる7.5 グラフの横断7.6 幅優先探索7.7 幅優先探索の応用7.8 深さ優先探索7.9 深さ優先探索の応用7.10 有向グラフでの深さ優先探索7.11 演習問題第8章　重み付きグラフのアルゴリズム8.1 最小スパニング木8.2 設計奮戦記：ネットさえあればよい8.3 最短経路8.4 設計奮戦記：電話で文書をつくる8.5 ネットワークフローと2部マッチング8.6 ランダム化最小カット8.7 アルゴリズムではなくグラフの設計8.8 演習問題第9章　組合せ的探索9.1 バックトラック法9.2 バックトラック法の例9.3 探索の枝刈り9.4 数独9.5 設計奮戦記：チェスボードを被覆する9.6 最良優先探索9.7 A*ヒューリスティック9.8 演習問題第10章　動的計画法10.1 キャッシング 対 計算10.2 近似文字列マッチング10.3 最長増加部分列10.4 設計奮戦記：バーコードのためのテキスト圧縮10.5 順序なし分割または部分和問題10.6 設計奮戦記：電力バランス10.7 順序付き分割問題10.8 文脈自由文法の構文解析10.9 動的計画法の限界：TSP10.10 設計奮戦記：過去はただの序章10.11 演習問題第11章　NP完全性11.1 問題と帰着11.2 アルゴリズムのための帰着11.3 初等的な困難性の帰着11.4 充足可能性問題11.5 SATからの創造的な帰着11.6 困難性証明のコツ11.7 設計奮戦記：時間との困難な戦い11.8 設計奮戦記：その後の失敗11.9 P対NP11.10 演習問題第12章　困難問題への対処12.1 近似アルゴリズム12.2 頂点被覆の近似12.3 ユークリッド巡回セールスマン12.4 平均が十分によい場合12.5 集合被覆12.6 ヒューリスティックな探索法12.7 設計奮戦記：ラジオでないだけ12.8 設計奮戦記：配列のアニーリング12.9 遺伝アルゴリズムと他のヒューリスティック探索法12.10 量子計算12.11 演習問題第13章　いかにしてアルゴリズムを設計するか13.1 テック企業の面接への準備索引

Steven S. Skiana

平田　富夫