アルゴリズム設計マニュアル 上
| 原書名 | The Algorithm Design Maneal |
|---|---|
| 著者名 | 平田 富夫 訳 |
| 発行元 | 丸善出版 |
| 発行年月日 | 2012年01月 |
| 判型 | B5変 |
| ページ数 | 424ページ |
| ISBN | 978-4-621-08510-3 |
| Cコード | 3055 |
| NDCコード | 007 |
| ジャンル | 電気・電子・情報工学 > 情報・コンピュータ > アルゴリズム/データ構造 |
内容紹介
本書は２部構成で、前半部分（上巻）ではアルゴリズムの基本概念とテクニックを解説し、後半部分（下巻）は様々な種類のアルゴリズムを集めたアルゴリズム集。アルゴリズムを身近な実際の問題を解決するための技術であるという立場から書いているので、本書の知識は実際の場面で実践的に使用することができる。本文中には「設計奮戦記」というコーナーがあり、アルゴリズムを設計した際に起こった問題を実話で紹介。設計現場の生の体験に基づき、具体的に設計のコツなどを知ることができる。Ｃ言語で書かれたプログラムの入手先アドレスを紹介しているので、読者は既存のソースをＷｅｂから入手することができる。
目次
第I部 実用的なアルゴリズムの設計
第１章 アルゴリズム設計への導入
１．１ ロボットのツアーの最適化
１．２ 適切な仕事の選択
１．３ 正しさの論証
１．４ 問題のモデル化
１．５ 設計奮戦記について
１．６ ボクの設計奮戦記：超能力のモデル化
１．７ 演習問題
第２章 アルゴリズム解析
２．１ 計算のＲＡＭモデル
２．２ ビッグオー記法
２．３ 増加率と支配関係
２．４ ビッグオーを使いこなす
２．５ 効率に関する議論
２．６ 対数とその応用
２．７ 対数の性質
２．８ ボクの設計奮戦記：ピラミッドの謎
２．９ 高度な解析
２．10 演習問題
第３章 データ構造
３．１ 連続データ構造と連結データ構造
３．２ スタックとキュー
３．３ 辞書
３．４ ２分探索木
３．５ 優先順位付きキュー
３．６ ボクの設計奮戦記：三角形を連ねる
３．７ ハッシングと文字列
３．８ 特定目的のデータ構造
３．９ ボクの設計奮戦記：数珠つなぎ
３．10 演習問題
第４章 ソートと探索
４．１ ソートの応用
４．２ ソートの実際
４．３ ヒープソート：データ構造による高速ソート
４．４ ボクの設計奮戦記：飛行機のチケットをくれないか
４．５ マージソート：分割統治法によるソート
４．６ クイックソート：ランダム化によるソート
４．７ 分配ソート：バケットを用いたソート
４．８ ボクの設計奮戦記：スキーナの抗弁
４．９ ２分探索と関連アルゴリズム
４．10 分割統治法
４．11 演習問題
第５章 グラフ横断
５．１ グラフの特徴
５．２ グラフのデータ構造
５．３ ボクの設計奮戦記：ボクはムーアの法則の犠牲者だった
５．４ ボクの設計奮戦記：グラフを手に入れる
５．５ グラフの横断
５．６ 幅優先探索
５．７ 幅優先探索の応用
５．８ 深さ優先探索
５．９ 深さ優先探索の応用
５．10 有向グラフでの深さ優先探索
５．11 演習問題
第６章 重み付きグラフのアルゴリズム
６．１ 最小スパニング木
６．２ ボクの設計奮戦記：ネットさえあればよい
６．３ 最短経路
６．４ ボクの設計奮戦記：電話で文書を作る
６．５ ネットワークフローと２部マッチング
６．６ アルゴリズムではなくグラフの設計
６．７ 演習問題
第７章 組合せ探索とヒューリスティックな方法
７．１ バックトラック法
７．２ 探索の枝刈り
７．３ 数独
７．４ ボクの設計奮戦記：チェスボードを被覆する
７．５ ヒューリスティックな探索法
７．６ ボクの設計奮戦記：ラジでないだけ
７．７ ボクの設計奮戦記：配列のアニーリング
７．８ 他のヒューリスティックな探索法
７．９ 並列アルゴリズム
７．10 ボクの設計奮戦記：速くなくたってどうしようもない
７．11 演習問題
第８章 動的計画法
８．１ キャッシング 対 計算
８．２ 近似文字列マッチング
８．３ 最長増加列
８．４ ボクの設計奮戦記：ロブスターの進化
８．５ 分割問題
８．６ 文脈自由文法の構文解析
８．７ 動的計画法の限界：ＴＳＰ
８．８ ボクの設計奮戦記：過去はただのProlog
８．９ ボクの設計奮戦記：バーコードのためのテキスト圧縮
８．10 演習問題
第９章 手に負えない問題と近似アルゴリズム
９．１ 問題と帰着
９．２ アルゴリズムのための帰着
９．３ 初等的な困難性の帰着
９．４ 充足可能性問題
９．５ 創造的な帰着
９．６ 困難性証明のコツ
９．７ ボクの設計奮戦記：時計との困難な戦い
９．８ ボクの設計奮戦記：その後の失敗
９．９ Ｐ対ＮＰ
９．10 ＮＰ完全問題への対処
９．11 演習問題
第10章 どのようにしてアルゴリズムを設計するか
