乱択アルゴリズム

アルゴリズムの振舞いを乱数に依存させる乱択アルゴリズムが流用されており、単にアルゴリズムといえば、今日では乱択アルゴリズムを含んでいると考えるのが普通である。しかし、実用アルゴリズムの世界では、乱択アルゴリズムの効果と価値が十分に認識されているとは言い難い。この状況を改善するには、アルゴリズム教育において乱択アルゴリズムに正当な地位を与える必要があろう。全体として、さまざまな分野の乱択アルゴリズムを網羅することは考えず、少数の乱択アルゴリズムを例として基本的な考え方のパターンを掘り下げる方針を採った。本書のレベルはやや高度であり、大学院あるいは学部の高学年でアルゴリズム理論とその基礎になる数学的素養を既に身につけた人、あるいはこの分野でこれから研究を始めようとする研究者を主な対象としている。 第 1 章 導入 1.1 乱択アルゴリズムの基本的な考え方 1.2 乱数の効用 1.3 乱択アルゴリズムの分類 1.4 数学とアルゴリズムの基礎 1.5 確率的解析のための準備 第 2 章 平均化効果を利用する乱択アルゴリズム 2.1 クィックソート 2.2 乱択逐次構成法:2 次元の凸包 2.3 低次元の線形計画法 2.4 LP 型問題 第 3 章 標本乱択を利用するアルゴリズム 3.1 部分集合の大きさ 3.2 κ 番目の値 3.3 ε標本とε網 3.4 最小全域木問題の線形時間アルゴリズム 3.5 標本乱択を利用した近似アルゴリズム:密なグラフの最大カット 第 4 章 くじ引き型のアルゴリズム 4.1 素数性判定の乱択アルゴリズム 4.2 関数の同一性の検証 4.3 成功確率の増幅 第 5 章 その他の種類の乱択アルゴリズム 5.1 制約のランダムな充足を図るアルゴリズム 5.2 乱歩を利用するアルゴリズム 第 6 章 マルコフ連鎖を用いた標本乱択 6.1 計数問題の近似アルゴリズム:標本乱択の応用 6.2 マルコフ連鎖の基礎 6.3 標本乱択のためのマルコフ連鎖の設計 6.4 定常分布への収束の速さ 6.5 厳密な標本乱択 第 7 章 脱乱択化 7.1 条件付き確率の方法 7.2 確率空間の縮小