内容紹介

アルゴリズム設計の技法は計算機科学の中心にある実践的な技術である．本書は学生とコンピュータ技術者がよいアルゴリズムを設計するためのマニュアルとなることを意図しているが，技術系企業の採用面接の準備に役立つことからも人気を博している．

本書は技法とリソースの二部からなり，前者はコンピュータアルゴリズムの設計と解析への一般的な入門であり，後者は適宜拾い読みされ参照されることを意図したアルゴリズムのカタログと広範にわたる参考文献からなる．

第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 プロによる相談

参考文献
訳者あとがき
索引

出版社からのメッセージ

本書は『アルゴリズム設計マニュアル 下』（2012年1月刊）の改訂版です。

関連商品

• 電子書籍

  
  アルゴリズム設計マニュアル 原書3版 上 平田　富夫 訳
  
• 
  アルゴリズム設計マニュアル 原書3版 下 平田　富夫 訳