出版社内容情報
●内容
アルゴリズムの振舞いを乱数に依存させる乱択アルゴリズムが流用されており，単にアルゴリズムといえば，今日では乱択アルゴリズムを含んでいると考えるのが普通である。しかし，実用アルゴリズムの世界では，乱択アルゴリズムの効果と価値が十分に認識されているとは言い難い。この状況を改善するには，アルゴリズム教育において乱択アルゴリズムに正当な地位を与える必要があろう。全体として，さまざまな分野の乱択アルゴリズムを網羅することは考えず，少数の乱択アルゴリズムを例として基本的な考え方のパターンを掘り下げる方針を採った。本書のレベルはやや高度であり，大学院あるいは学部の高学年でアルゴリズム理論とその基礎になる数学的素養を既に身につけた人，あるいはこの分野でこれから研究を始めようとする研究者を主な対象としている。
●目次
第1章 導入
1.1 乱択アルゴリズムの基本的な考え方
1.2 乱数の効用
1.3 乱択アルゴリズムの分類
1.4 数学とアルゴリズムの基礎
1.5 確率的解析のための準備
第2章 平均化効果を利用する乱択アルゴリズム
2.1 クィックソート
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 確率空間の縮小
目次
第１章 導入
第２章 平均化効果を利用する乱択アルゴリズム
第３章 標本乱択を利用するアルゴリズム
第４章 くじ引き型のアルゴリズム
第５章 その他の種類の乱択アルゴリズム
第６章 マルコフ連鎖を用いた標本乱択
第７章 脱乱択化
著者等紹介
玉木久夫［タマキヒサオ］
１９５２年東京都生まれ。１９７５年東京大学理学部物理学科卒業。１９７７年東京大学大学院理学系研究科物理学専攻修士課程修了。１９７７年～１９９０年茨城大学工学部情報工学科勤務。１９９３年トロント大学大学院計算機科学科博士課程修了。１９９３年～１９９４年ＩＢＭワトソン研究所数理科学ポストドクトラルフェロー。１９９４年～１９９７年ＩＢＭ東京基礎研究所勤務。１９９７年明治大学理工学部情報科学科・教授。Ｐｈ．Ｄ． ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ。専門は計算理論（本データはこの書籍が刊行された当時に掲載されていたものです）
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。
感想・レビュー
※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。
moaikids
