出版社内容情報
●内容
本翻訳書は，Jon Kleinbergと ´Eva Tardosの著書"Algorithm Design"の全訳である。訳者が原書の翻訳に至ったのは，2005年5月にボルチモアで開催されたACMのSTOC（Symposiumon Theory of Computing）の国際会議において，Addison-Wesley社のブースで原書を手に取ったときの新鮮な感銘からである。組合せ最適化の分野の著名な賞であるファルカーソン賞を受賞した ´Eva Tardos教授と翌2006年にチューリング賞と並ぶ情報科学のネバンリンナ賞を受賞したJon Kleinberg教授の初めての本であるということもさることながら，アルゴリズムデザインに対する著者の世界観が具現されていて，これまでに類のない画期的な本に仕上がっているという強い印象を受けたからである。そして，是非とも日本の多くの学生や研究者に，著者のアルゴリズムデザインの世界観を紹介したい，むしろ，しなければならない，という気持ちで，日本語訳の許可を著者に依頼して快諾されたのである。
著者の序文にもあるように，著者のアルゴリズムデザインの世界観は以下のとおりである。アルゴリズム的な考え方は，情報科学分野はもちろん，実社会の様々な分野に広く浸透してきている。実際，伝統的な旧来の分野にとどまらず，インターネットのルーティングプロトコル，ゲノムインフォマティクス，組合せ的オークション，Web広告バナーの提示，等の新規分野の至るところでアルゴリズムが利用されている。しかし一方で，現実に起こる問題が，きれいに定式化された数学的な形式の問題として現れることは極めてまれである。むしろ，煩雑な細部が大量に付随しているのが普通であり，その中には本質的なものも余分なものもあったりする。したがって，アルゴリズムデザインの実際的な作業は，問題の中の，数学的な核となる部分を見出す仕事と，問題の構造に基づいた適切なアルゴリズムデザイン技法を見極める仕事という，二つの基本的な構成要素からなっている。これら二つの構成要素は相互に関連し合っている。すなわち，様々なアルゴリズムデザイン技法に習熟すればするほど，問題に潜んでいる煩雑な情報からきれいな定式化を導き出すことができるようになる。さらに，アルゴリズム的な考え方により，通常では見えなかったものまでが見えてくるようになる。潜んでいる問題を明快に表現する言語を習得でき，そしてそれを用いて，さらなる展開への扉が開けるという点に，アルゴリズム的な考え方の最大の効用がある。
著者はこのようなアルゴリズムデザインの世界観に基づいて，原書の目標を以下のように設定している。すなわち，様々な分野で生じる複雑な形式の問題から明快な定式化を発見する方法と，その定式化に基づいて実際の問題に対する効率的なアルゴリズムをデザインする方法をわかりやすく提供することが原書の目標であるとしている。
従来のアルゴリズムの書籍では，この観点が取り上げられることはほとんどなかった。すなわち，効率的なアルゴリズムだけをトップダウン方式で提示するものが多かったのである。しかし，アルゴリズムの有用性と可能性を真に理解し，様々な現実の問題に応用できるような実力を養成するためには，そこで生じる複雑な形式の問題から明快な定式化を発見する方法が極めて重要なのである。アルゴリズムデザインの世界におけるこの目標設定と，それを達成するための工夫が，原書の画期的な特徴となっている。
より具体的には，以下のとおりである。原書では，情報科学や関係する分野の応用から生じた重要な問題を題材として取り上げている。それらの問題に対して，まず問題の背景を入念に説明し，定式化を導き出すためのアイデアを読者が自然と獲得できるように記述している。そして，その定式化に基づいて，その問題に対するアルゴリズムのデザイン法を解説し，その後にそのアルゴリズムの解析にも力点を置いて記述している。さらに，本文で学んだ方法論をより確実にして展開できるようにするための演習問題にも特徴がある。演習問題は，Cornell大学の授業の一環として，実際にレポート課題や試験問題として取り上げられたものであるので，原書の全体構想に極めて適合する問題となっている。すなわち，最初に問題の本質を抽出して必要な記法を用いて数学的に定式化し，次にアルゴリズムをデザインし，そして最後に，そのアルゴリズムの解析を行って正当性を証明する訓練ができるようになっている。また，"解答付き演習問題"を各章で取り上げ，演習問題に対する解答の書き方についても学べるものになっている。
（訳者序文より抜粋）
●目次
詳細な解説付き問題の一覧
詳細な解説付きアルゴリズムの一覧
序文
第 1 章 はじめに：いくつかの代表的問題
1.1 最初の問題：安定マッチング
1.2 五つの代表的な問題
解答付き演習問題
演習問題
ノートと発展文献
第 2 章 アルゴリズム解析の基礎事項
2.1 計算容易性
2.2 増加の漸近的オーダー
2.3 リストと配列による安定マッチングアルゴリズムの実装
2.4 よく現れる計算時間の復習
2.5 より複雑なデータ構造：優先順位付きキュー
解答付き演習問題
演習問題
ノートと発展文献
第 3 章 グラフ
3.1 基本的定義と応用
3.2 グラフの連結性とグラフ走査
3.3 キューとスタックを用いたグラフ走査
3.4 二部グラフ性の判定：幅優先探索の応用
3.5 有向グラフの連結性
3.6 有向無閉路グラフとトポロジカル順序付け
解答付き演習問題
演習問題
ノートと発展文献
第 4 章 グリーディアルゴリズム
4.1 区間スケジューリング：グリーディアルゴリズムの先進性
4.2 遅延最小化スケジューリング：交換議論
4.3 最適キャッシング：より複雑な交換議論
4.4 グラフにおける最短パス
4.5 最小全点木問題
4.6 Kruskalのアルゴリズムの実装：Union-Findデータ構造
4.7 クラスタリング
4.8 Huffman符号とデータ圧縮
4.9 最小コスト有向木：多フェーズグリーディアルゴリズム
解答付き演習問題
演習問題
ノートと発展文献
第 5 章 分割統治法
5.1 最初の漸化式：マージソートアルゴリズム
5.2 さらなる漸化式
5.3 反転数の数え上げ
5.4 最近点対の発見
5.5 整数の積の計算
5.6 畳込みと高速フーリエ変換
解答付き演習問題
演習問題
ノートと発展文献
第 6 章 動的計画法
6.1 重み付き区間スケジューリング：再帰的手続き
6.2 動的計画法の原理：部分問題上での記憶化と反復
6.3 区分最小二乗法：多肢選択
6.4 部分集合和とナップサック：変数の追加
6.5 RNA二次構造：区間上での動的計画法
6.6 系列アライメント
6.7 分割統治法による線形の領域の系列アライメント
6.8 グラフの最短パス
6.9 最短パスと距離ベクトルプロトコル
6.10 グラフの負閉路
解答付き演習問題
演習問題
ノートと発展文献
第 7 章 ネットワークフロー
7.1 最大フロー問題とFord-Fulkersonアルゴリズム
7.2 ネットワークの最大フローと最小カット
7.3 良い増加パスの選択
7.4 プリフロープッシュ最大フローアルゴリズム
7.5 最初の応用：二部グラフのマッチング問題
7.6 有向グラフと無向グラフにおける素パス
7.7 最大フロー問題の拡張版
7.8 市場調査デザイン
7.9 航空スケジューリング
7.10 画像分割
7.11 プロジェクト選択
7.12 野球ペナントレースの優勝の可能性の消去
7.13 発展：辺にコストの付随するマッチング問題
解答付き演習問題
演習問題
ノートと発展文献
第 8 章 NPと計算困難性
8.1 多項式時間リダクション
8.2 "ガジェット"を用いたリダクション：充足可能性問題
8.3 効率的な証明とNPの定義
8.4 NP-完全問題
8.5 系列化問題
8.6 分割問題
8.7 グラフ彩色問題
8.8 数値問題
8.9 co-NPとNPの非対称性
8.10 計算困難な問題の部分的な分類
解答付き演習問題
演習問題
ノートと発展文献
第 9 章 PSPACE：クラスNPを超える問題のクラス
9.1 クラスPSPACE
9.2 PSPACEに属する困難な問題
9.3 限量化問題とゲームの多項式領域解法
9.4 計画問題の多項式領域解法
9.5 PSPACE-完全性の証明
解答付き演習問題
演習問題
ノートと発展文献
第10章 計算容易性の拡大
10.1 小さい点カバーの発見
10.2 木におけるNP-困難問題の解法
10.3 円弧集合の彩色
10.4 グラフの木分解
10.5 木分解の構成
解答付き演習問題
演習問題
ノートと発展文献
第11章 近似アルゴリズム
11.1 グリーディアルゴリズムと最適解に対する近似解の上界：負荷均等化問題への適用
11.2 センター選択問題
11.3 集合カバー：一般的なグリーディヒューリスティック
11.4 価格付け法：点カバーへの適用
11.5 価格付け法による最大化：素パス問題
11.6 線形計画法とラウンディング：点カバーへの適用
11.7 負荷均等化問題（再考）：より高度な LPの応用
11.8 究極の近似保証：ナップサック問題
解答付き演習問題
演習問題
ノートと発展文献
第12章 局所探索
12.1 最適化問題の景観図
12.2 Metropolisアルゴリズムとシミュレーテッドアニーリング
12.3 Hopfieldニューラルネットワークへの局所探索の応用
12.4 局所探索による最大カットの近似
12.5 近傍関係の選択
12.6 局所探索による分類
12.7 最善反応行動と Nash均衡
解答付き演習問題
演習問題
ノートと発展文献
第13章 乱択アルゴリズム
13.1 第一の応用：競合の解消
13.2 大域的最小カットの発見
13.3 ランダム変数と期待値
13.4 MAX3-SATに対する乱択近似アルゴリズム
13.5 乱択分割統治法：中央値発見とクイックソート
13.6 ハッシング：辞書の乱択実装
13.7 最近点対を求める乱択アプローチ
13.8 乱択キャッシング
13.9 Chernoff限界
13.10 負荷均等化
13.11 パケットルーティング
13.12 背景：いくつかの基本的な確率の定義
解答付き演習問題
演習問題
ノートと発展文献
第14章 永遠に動作するアルゴリズム
参考文献
人名索引
問題索引
アルゴリズム索引
用語和（英）索引
用語英（和）索引
目次
はじめに：いくつかの代表的問題
アルゴリズム解析の基礎事項
グラフ
グリーディアルゴリズム
分割統治法
動的計画法
ネットワークフロー
ＮＰと計算困難性
ＰＳＰＡＣＥ：クラスＮＰを超える問題のクラス
計算容易性の拡大
近似アルゴリズム
局所探索
乱択アルゴリズム
著者等紹介
クラインバーグ，ジョン［クラインバーグ，ジョン］［Ｋｌｅｉｎｂｅｒｇ，Ｊｏｎ］
コーネル（Ｃｏｒｎｅｌｌ）大学情報学科の教授。１９９６年にＭＩＴからＰｈ．Ｄ．の学位を獲得している。ＮＳＦ Ｃａｒｅｅｒ Ａｗａｒｄ、ＯＮＲ Ｙｏｕｎｇ Ｉｎｖｅｓｔｉｇａｔｏｒ Ａｗａｒｄ、ＩＢＭ Ｏｕｔｓｔａｎｄｉｎｇ Ｉｎｎｏｖａｔｉｏｎ Ａｗａｒｄなど多くの賞も受賞。専門分野は、アルゴリズムに関する研究で、具体的には、ネットワーク構造と情報の構造の分野と、情報科学、最哲化、データマイニング、計算生物学への応用の分野に興味をもっている。ハブとオーソリティを用いたネットワーク解析の仕事は、現在のインターネットサーチエンジンの発明の基礎となっている。２００６年にこれらの業績で国際数学連合（ＩＭＵ）から理論情報科学の優れた研究を成し遂げた研究者に贈られるネバンリンナ（Ｎｅｖａｎｌｉｎｎａ）賞を受賞している
タルドシュ，エーバ［タルドシュ，エーバ］［Ｔａｒｄｏｓ，´Ｅｖａ］
コーネル（Ｃｏｒｎｅｌｌ）大学情報学科の教授。１９８４年にハンガリーのブタペストのＥ¨ｏｔｖ¨ｏｓ大学からＰｈ．Ｄ．の学位を獲得している。Ａｍｅｒｉｃａｎ Ａｃａｄｅｍｙ ｏｆ Ａｒｔｓ ａｎｄ Ｓｃｉｅｎｃｅｓのメンバーであり、ＡＣＭフェローでもある。以下の賞も受賞している。ＮＳＦ Ｐｒｅｓｉｄｅｎｔｉａｌ Ｙｏｕｎｇ Ｉｎｖｅｓｔｉｇａｔｏｒ Ａｗａｒｄ、Ｆｕｌｋｅｒｓｏｎ Ｐｒｉｚｅ、ｒｅｓｅａｒｃｈ ｆｅｌｌｏｗｓｈｉｐｓ ｆｒｏｍ ｔｈｅ Ｇｕｇｇｅｎｈｅｉｍ，Ｐａｃｋａｒｄ，ａｎｄ ｓｌｏａｎ Ｆｏｕｎｄａｔｉｏｎｓ，ｔｅａｃｈｉｎｇ ａｗａｒｄｓ ｆｒｏｍ ｔｈｅ Ｃｏｒｎｅｌｌ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｌｌｅｇｅ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｄｅｐａｔｍｅｎｔ。研究の関心は、グラフとネットワークに対するアルゴリズムの設計と解析が主となっており、ネットワークフローアルゴリズムとネットワーク問題に対する近似アルゴリズムの研究で最もよく知られている
浅野孝夫［アサノタカオ］
中央大学理工学部情報工学科教授。１９７７年東北大学にて工学博士取得。１９８７年日本ＩＢＭ科学賞（情報科学部門）受賞
浅野泰仁［アサノヤスヒト］
京都大学情報学研究科ＧＣＯＥ助教。２００３年東京大学にて理学博士（情報科学）取得。以降、Ｗｅｂ上の情報発見手法の研究に従事
小野孝男［オノタカオ］
名古屋大学大学院情報科学研究科助教。１９９９年名古屋大学にて博士（工学）取得。以降、アルゴリズムの研究に従事（本データはこの書籍が刊行された当時に掲載されていたものです）
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。
感想・レビュー
※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。
H Umeda
-
- 和書
- 生体機能関連化学実験法
