アクセスランキング

01位
数学のための英語教本―読むことから始めよう― 
02位
入門計量経済学
03位
実用的でないPythonプログラミング―楽しくコードを書いて賢くなろう!― 
04位
サーストン万華鏡―人と数学の未来を見つめて― 
05位
ジオダイナミクス 原著第3版
  • ニュースメール
  • アフターサービス
  • facebook

乱択アルゴリズム

書籍情報
シリーズ名アルゴリズム・サイエンスシリーズ 数理技法編 【4】巻
ISBN978-4-320-12170-6
判型A5 
ページ数240ページ
発行年月2008年08月
本体価格3,000円
乱択アルゴリズム 書影
乱択アルゴリズム

アルゴリズムの振舞いを乱数に依存させる乱択アルゴリズムが流用されており,単にアルゴリズムといえば,今日では乱択アルゴリズムを含んでいると考えるのが普通である。しかし,実用アルゴリズムの世界では,乱択アルゴリズムの効果と価値が十分に認識されているとは言い難い。この状況を改善するには,アルゴリズム教育において乱択アルゴリズムに正当な地位を与える必要があろう。全体として,さまざまな分野の乱択アルゴリズムを網羅することは考えず,少数の乱択アルゴリズムを例として基本的な考え方のパターンを掘り下げる方針を採った。本書のレベルはやや高度であり,大学院あるいは学部の高学年でアルゴリズム理論とその基礎になる数学的素養を既に身につけた人,あるいはこの分野でこれから研究を始めようとする研究者を主な対象としている。

目次

第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 確率空間の縮小