内容紹介

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

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

第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 動的計画法の限界：TSP
10.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対NP
11.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 テック企業の面接への準備

索引

出版社からのメッセージ

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

関連商品

• 電子書籍

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