アルゴリズムデザイン [単行本]

アルゴリズムデザイン [単行本] の 商品概要

• 目次

  詳細な解説付き問題の一覧
  
  詳細な解説付きアルゴリズムの一覧
  
  序文
  
  第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章　永遠に動作するアルゴリズム
  
  参考文献
  人名索引
  問題索引
  アルゴリズム索引
  用語和（英）索引
  用語英（和）索引

• 出版社からのコメント

  200以上の演習問題を載せた標準的教科書

• 内容紹介

  　本翻訳書は、Jon Kleinbergと Éva Tardosの著書“Algorithm Design”の全訳である。訳者が原書の翻訳に至ったのは、2005年5月にボルチモアで開催されたACMのSTOC（Symposiumon
  Theory of Computing）の国際会議において、Addison-Wesley社のブースで原書を手に取ったときの新鮮な感銘からである。組合せ最適化の分野の著名な賞であるファルカーソン賞を受賞した Éva Tardos教授と翌2006年にチューリング賞と並ぶ情報科学のネバンリンナ賞を受賞したJon Kleinberg教授の初めての本であるということもさることながら、アルゴリズムデザインに対する著者の世界観が具現されていて、これまでに類のない画期的な本に仕上がっているという強い印象を受けたからである。そして、是非とも日本の多くの学生や研究者に、著者のアルゴリズムデザインの世界観を紹介したい、むしろ、しなければならない、という気持ちで、日本語訳の許可を著者に依頼して快諾されたのである。
  
  　著者の序文にもあるように、著者のアルゴリズムデザインの世界観は以下のとおりである。アルゴリズム的な考え方は、情報科学分野はもちろん、実社会の様々な分野に広く浸透してきている。実際、伝統的な旧来の分野にとどまらず、インターネットのルーティングプロトコル、ゲノムインフォマティクス、組合せ的オークション、Web広告バナーの提示、等の新規分野の至るところでアルゴリズムが利用されている。しかし一方で、現実に起こる問題が、きれいに定式化された数学的な形式の問題として現れることは極めてまれである。むしろ、煩雑な細部が大量に付随しているのが普通であり、その中には本質的なものも余分なものもあったりする。したがって、アルゴリズムデザインの実際的な作業は、問題の中の、数学的な核となる部分を見出す仕事と、問題の構造に基づいた適切なアルゴリズムデザイン技法を見極める仕事という、二つの基本的な構成要素からなっている。これら二つの構成要素は相互に関連し合っている。すなわち、様々なアルゴリズムデザイン技法に習熟すればするほど、問題に潜んでいる煩雑な情報からきれいな定式化を導き出すことができるようになる。さらに、アルゴリズム的な考え方により、通常では見えなかったものまでが見えてくるようになる。潜んでいる問題を明快に表現する言語を習得でき、そしてそれを用いて、さらなる展開への扉が開けるという点に、アルゴリズム的な考え方の最大の効用がある。

• 著者紹介（「BOOK著者紹介情報」より）（本データはこの書籍が刊行された当時に掲載されていたものです）

  クラインバーグ,ジョン(クラインバーグ,ジョン／Kleinberg,Jon)
  コーネル（Ｃｏｒｎｅｌｌ）大学情報学科の教授。１９９６年にＭＩＴからＰｈ．Ｄ．の学位を獲得している。ＮＳＦ　Ｃａｒｅｅｒ　Ａｗａｒｄ、ＯＮＲ　Ｙｏｕｎｇ　Ｉｎｖｅｓｔｉｇａｔｏｒ　Ａｗａｒｄ、ＩＢＭ　Ｏｕｔｓｔａｎｄｉｎｇ　Ｉｎｎｏｖａｔｉｏｎ　Ａｗａｒｄなど多くの賞も受賞。専門分野は、アルゴリズムに関する研究で、具体的には、ネットワーク構造と情報の構造の分野と、情報科学、最哲化、データマイニング、計算生物学への応用の分野に興味をもっている。ハブとオーソリティを用いたネットワーク解析の仕事は、現在のインターネットサーチエンジンの発明の基礎となっている。２００６年にこれらの業績で国際数学連合（ＩＭＵ）から理論情報科学の優れた研究を成し遂げた研究者に贈られるネバンリンナ（Ｎｅｖａｎｌｉｎｎａ）賞を受賞している
  
  タルドシュ,エーバ(タルドシュ,エーバ／Tardos,´Eva)
  コーネル（Ｃｏｒｎｅｌｌ）大学情報学科の教授。１９８４年にハンガリーのブタペストのＥ¨ｏｔｖ¨ｏｓ大学からＰｈ．Ｄ．の学位を獲得している。Ａｍｅｒｉｃａｎ　Ａｃａｄｅｍｙ　ｏｆ　Ａｒｔｓ　ａｎｄ　Ｓｃｉｅｎｃｅｓのメンバーであり、ＡＣＭフェローでもある。以下の賞も受賞している。ＮＳＦ　Ｐｒｅｓｉｄｅｎｔｉａｌ　Ｙｏｕｎｇ　Ｉｎｖｅｓｔｉｇａｔｏｒ　Ａｗａｒｄ、Ｆｕｌｋｅｒｓｏｎ　Ｐｒｉｚｅ、ｒｅｓｅａｒｃｈ　ｆｅｌｌｏｗｓｈｉｐｓ　ｆｒｏｍ　ｔｈｅ　Ｇｕｇｇｅｎｈｅｉｍ，Ｐａｃｋａｒｄ，ａｎｄ　ｓｌｏａｎ　Ｆｏｕｎｄａｔｉｏｎｓ，ｔｅａｃｈｉｎｇ　ａｗａｒｄｓ　ｆｒｏｍ　ｔｈｅ　Ｃｏｒｎｅｌｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｃｏｌｌｅｇｅ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　Ｄｅｐａｔｍｅｎｔ。研究の関心は、グラフとネットワークに対するアルゴリズムの設計と解析が主となっており、ネットワークフローアルゴリズムとネットワーク問題に対する近似アルゴリズムの研究で最もよく知られている
  
  浅野 孝夫(アサノ タカオ)
  中央大学理工学部情報工学科教授。１９７７年東北大学にて工学博士取得。１９８７年日本ＩＢＭ科学賞（情報科学部門）受賞
  
  浅野 泰仁(アサノ ヤスヒト)
  京都大学情報学研究科ＧＣＯＥ助教。２００３年東京大学にて理学博士（情報科学）取得。以降、Ｗｅｂ上の情報発見手法の研究に従事
  
  小野 孝男(オノ タカオ)
  名古屋大学大学院情報科学研究科助教。１９９９年名古屋大学にて博士（工学）取得。以降、アルゴリズムの研究に従事

アルゴリズムデザイン [単行本] の商品スペック