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

発売日 : 2024年01月30日

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

出版社 : 丸善出版

発行形態 : 単行本

ページ数 : 480p

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

目次第II部　ヒッチハイカーのためのアルゴリズム案内第14章　アルゴリズム問題のカタログ第15章　データ構造15.1 辞書15.2 優先順位付きキュー15.3 サフィックス木とサフィックス配列15.4 グラフのデータ構造15.5 集合のデータ構造15.6 kd木第16章　数値問題16.1 線形方程式を解く16.2 バンド幅の削減16.3 行列の乗算16.4 行列式とパーマネント16.5 制約付きおよび制約なし最適化問題16.6 線形計画問題16.7 乱数の生成16.8 因数分解と素数判定16.9 任意精度の算術演算16.10 ナップザック問題16.11 離散フーリエ変換第17章　組合せ問題17.1 ソート17.2 探索17.3 中央値と選択17.4 順列の生成17.5 部分集合の生成17.6 分割の生成17.7 グラフの生成17.8 カレンダーの計算17.9 ジョブスケジューリング17.10 充足可能性第18章　グラフ問題：多項式時間18.1 連結成分18.2 位相的ソート18.3 最小スパニング木18.4 最短経路18.5 推移的閉包と推移的簡約18.6 マッチング18.7 オイラー閉路/中国人郵便配達18.8 辺連結度と点連結度18.9 ネットワークフロー18.10 グラフをうまく描く18.11 木を描画する18.12 平面性の判定と埋め込み第19章　グラフ問題：NP困難19.1 クリーク19.2 独立集合19.3 頂点被覆19.4 巡回セールスマン問題19.5 ハミルトン閉路19.6 グラフ分割19.7 頂点彩色19.8 辺彩色19.9 グラフ同型19.10 シュタイナー木19.11 帰還辺/帰還点集合第20章　計算幾何学20.1 頑健な幾何的基本計算20.2 凸包20.3 三角分割20.4 ボロノイ図20.5 最近接点探索20.6 領域探索20.7 点位置決定20.8 交差検出20.9 ビンパッキング20.10 中心軸変換20.11 多角形分割20.12 多角形の簡約化20.13 形の類似性20.14 動作計画20.15 直線アレンジメントの管理20.16 ミンコフスキー和第21章　集合と文字列の問題21.1 集合被覆21.2 集合パッキング21.3 文字列マッチング21.4 近似文字列マッチング21.5 テキスト圧縮21.6 暗号21.7 有限状態機械の最小化21.8 最長共通部分文字列/部分列21.9 最短共通超文字列第22章　アルゴリズム資源22.1 アルゴリズムライブラリー22.2 データ資源22.3 オンライン参考文献22.4 プロによる相談参考文献訳者あとがき索引

Steven S. Skiana

平田　富夫