アクセスランキング

01位
Rプログラミング本格入門―達人データサイエンティストへの道― 
02位
統計的自然言語処理の基礎
03位
カメムシの母が子に伝える共生細菌―必須相利共生の多様性と進化― 
04位
速習 強化学習―基礎理論とアルゴリズム― 
05位
グラフ理論とフレームワークの幾何
  • ニュースメール
  • アフターサービス
  • 教科書献本のご案内
  • facebook
  • 構造計画研究所

アルゴリズムデザイン

書籍情報
ISBN978-4-320-12217-8
判型B5 
ページ数830ページ
発行年月2008年07月
本体価格15,000円
アルゴリズムデザイン 書影
アルゴリズムデザイン

 本翻訳書は,Jon Kleinbergと Éva Tardosの著書“Algorithm Design”の全訳である。訳者が原書の翻訳に至ったのは,2005年5月にボルチモアで開催されたACMのSTOC(Symposiumon
Theory of Computing)の国際会議において,Addison-Wesley社のブースで原書を手に取ったときの新鮮な感銘からである。組合せ最適化の分野の著名な賞であるファルカーソン賞を受賞した Éva 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章 永遠に動作するアルゴリズム

参考文献
人名索引
問題索引
アルゴリズム索引
用語和(英)索引
用語英(和)索引