計算困難問題に対するアルゴリズム理論
組合せ最適化,ランダマイゼーション,近似,ヒューリスティクス
J. ホロムコヴィッチ 著
和田 幸一/増澤 利光/元木 光雄 訳
 
アイ計算困難問題に対するアルゴリズム理論   B5変 並製 577頁 本体 7,500円+税  
ISBN 4-431-71182-1
CコードC3041
 

計算困難問題とは,解き方はわかっているが現在の計算機では計算に時間がかかり過ぎて解けないと思われている問題のことである.本書は,この計算困難問題に対するアルゴリズムの設計に焦点をしぼり,問題を攻略するための主要な可能性を系統的に説明し,結びつけ,かつ比較した教科書である.本書は,アーヘン工科大学で著者が行った講義をもと
にして著されたものであり,「単純さ」や「わかりやすさ」を信条として,できる限り単純な数学だけを用い,豊富な題材について具体的に記述している.

 

第1章 序論
  動機と目的
  学生と実際に計算機に携わる人に対して
  講義をする先生方へ
  本書の構成

第2章 初歩的な基礎
  序論
  数学の基礎
    線形代数
    組合せ,数え上げ,グラフ理論
    ブール関数とブール式
    代数と数論
    確率論
  アルゴリズム論の基礎
    アルファベット,語,言語
    アルゴリズム問題
    計算量理論
    アルゴリズム設計技法

第3章 決定性アプローチ
  序論
  擬多項式時間アルゴリズム
    基本概念
    動的計画法とナップサック問題
    最大フロー問題とFord-Fulkerson法
    適用可能性の限界
  パラメータ化計算量
    基本概念
    パラメータ化計算量の適用可能性
    関連する話題
  分枝限定法
    基本概念
    MAX-SATとTSPに対する適用例
     関連する話題
  指数時間の最悪計算量の低減
    基本概念
    計算量が 2n より小さい3SATの解法
  局所探索
    序論と基本概念
    近傍とKernighan-Linの深さ可変探索の例
    解の精度と計算量のトレードオフ
  線形計画法への緩和
    基本概念
    線形計画法による問題の記述
    シンプレックスアルゴリズム
    丸め,LP-双対法,プライマルデュアル法
  文献と関連する話題

第4章 近似アルゴリズム
  序論
  基礎
    近似アルゴリズムの概念
    最適化問題のクラス分け
    近似の安定性
    双対近似アルゴリズム
  アルゴリズムの設計
    序論
    被覆問題,貪欲法,線形計画法への緩和
    最大カット問題と局所探索
    ナップサック問題とPTAS
    巡回セールスマン問題と近似の安定性
    箱詰め問題,スケジューリング,双対近似アルゴリズム
  近似不可能性
    序論
    NP困難問題の帰着
    近似保存帰着
    確率的証明検査と近似不可能性
  文献と関連する話題

第5章 乱択アルゴリズム
  序論
  乱択アルゴリズムの分類と設計パラダイム
    基礎
    乱択アルゴリズムの分類
    乱択アルゴリズムの設計パラダイム
  乱択アルゴリズムの設計
    序論
    平方剰余---ランダムサンプリングとラスベガス法
    素数判定---豊富な証拠と片側誤りモンテカルロ法
    等価性判定---指紋法とモンテカルロ法
    MIN-CUT問題に対する乱択最適化アルゴリズム
    MAX-SAT問題とランダムサンプリング
    3SATと乱択多スタート局所探索
  デランダマイゼーション
    基本的なアイデア
    確率空間の縮小によるデランダマイゼーション
    確率空間の縮小とMAX-EkSAT
    条件付き期待値法によるデランダマイゼーション
    条件付き期待値法と充足可能性問題
  文献と関連する話題

第6章 ヒューリスティクス
  序論
  焼きなまし法
    基本概念
    理論と実験による考察
    乱択タブーサーチ
  遺伝アルゴリズム
    基本概念
    自由パラメータの調整
  文献と関連する話題

第7章 困難問題を解くためのガイド
  序論
  アルゴリズム的な仕事にとって代わるべきこと,コストに関して一言
  異なる概念と技法の融合
  異なるアプローチの比較
  並列化による高速化
  新しいテクノロジー
    序論
    DNA 計算
    量子計算
  基本的用語の辞書

参考文献
訳者あとがき
索 引

 

【著者】
J. ホロムコヴィッチ (Juraj Hromkovich)
  Swiss Federal Institute of Technology, ETH Zürich, Department of Computer Science,
  ETH Zentrum, CAB F16, Universit¨atstrasse 6, CH-8092 Zürich.
  1958 年,チェコスロヴァキアのブラティスラヴァに生まれる.1986 年,Comenius 大学でB.Rovan とE.Toman
  の指導を受け,博士号を取得.Comenius 大学,RWTH Aachen などで教授職を歴任し,
  現在,スイス連邦工科大学チューリッヒ校計算機科学科教授.著書として,本書の他に
  Design and Analysis of Randomized Algorithms Part I (Springer-Verlag, 2005),
  Dissemination of Information in Communication Networks(共著,Springer-Verlag, 2005)
  などがある.

【訳者】
和田 幸一 (わだ こういち)
  大阪大学大学院基礎工学研究科博士後期課程修了.
  名古屋工業大学大学院教授.工学博士.
  専門:計算機科学.
  著書に『IT テキスト アルゴリズム論』(共著,オーム社,2003 年),
  訳書に『アルゴリズムイントロダクション1, 2, 3』(共訳,近代科学社,1996 年)がある.

増澤 利光 (ますざわ としみつ)
  大阪大学大学院基礎工学研究科博士後期課程修了.
  大阪大学大学院情報科学研究科教授.工学博士.
  専門:分散アルゴリズム.
  著書に『IT テキスト アルゴリズム論』(共著,オーム社,2003 年)がある.

元木 光雄 (もとき みつお)
  東京工業大学大学院情報理工学研究科数理・計算科学専攻博士後期課程修了.
  北陸先端科学技術大学院大学助手.博士(理学).
  専門:計算量理論,アルゴリズム理論.
  著書に『ポストゲノム時代の遺伝統計学』(共著,羊土社,2001 年)がある.
  計算困難問題に対するアルゴリズム理論
  組合せ最適化,ランダマイゼーション,近似,ヒューリスティクス定価(本体7,500 円+税)

(所属は初刷出版時)



戻る