| 書誌種別 |
図書 |
| タイトル |
確率と計算 |
| サブタイトル |
乱択アルゴリズムと確率的解析 |
| タイトルヨミ |
カクリツ ト ケイサン |
| サブタイトルヨミ |
ランタク アルゴリズム ト カクリツテキ カイセキ |
| 人名 |
Michael Mitzenmacher／著
Eli Upfal／著
小柴 健史／訳
河内 亮周／訳
|
| 人名ヨミ |
Michael Mitzenmacher Eli Upfal コシバ タケシ カワチ アキノリ |
| 人名ヨミ |
|
| 出版者・発行者 |
共立出版
|
| 出版者・発行者等ヨミ |
キョウリツ シュッパン |
| 出版地・発行地 |
東京 |
| 出版・発行年月 |
2009.4 |
| ページ数または枚数・巻数 |
18,493p |
| 大きさ |
22cm |
| 価格 |
￥６２００ |
| ISBN |
978-4-320-12229-1 |
| ISBN |
4-320-12229-1 |
| 注記 |
原タイトル:Probability and computing |
| 注記 |
文献:p487〜488 |
| 分類記号 |
417.1
|
| 件名 |
確率論
／
アルゴリズム
|
| 内容紹介 |
計算機科学に関連するランダム性の基本的手法である乱択アルゴリズムや、アルゴリズムの確率的解析について解説する。ブラウン大学およびハーバード大学での講義「計算機科学における確率的手法」を発展させ書籍化。 |
| 言語区分 |
jpn |
| タイトルコード |
1009811181441 |
| 目次 |
第1章 事象と確率 |
|
1.1 応用:多項式の等価性検算／1.2 確率論の公理／1.3 応用:行列積の検算／1.4 応用:乱択最小カットアルゴリズム／1.5 練習問題 |
|
第2章 離散確率変数と期待値 |
|
2.1 確率変数と期待値／2.2 Bernoulli確率変数と二項確率変数／2.3 条件付き期待値／2.4 幾何分布／2.5 応用:クィックソートの実行時間の期待値／2.6 練習問題 |
|
第3章 積率と偏差 |
|
3.l Markovの不等式／3.2 分散と確率変数の積率／3.3 Chebyshevの不等式／3.4 応用:中央値を計算するための乱択アルゴリズム／3.5 練習問題 |
|
第4章 Chernoff上界 |
|
4.1 積率母関数／4.2 Chernoff上界の導出と適用／4.3 特殊な場合の上界の改善／4.4 応用:集合均等化／4.5 応用:疎ネットワークにおけるパケット配送／4.6 練習問題 |
|
第5章 ボール,ビン,ランダムグラフ |
|
5.1 事例:誕生日の逆理／5.2 ボールをビンへ／5.3 Poisson分布／5.4 Poisson近似／5.5 応用:ハッシュ法／5.6 ランダムグラフ／5.7 練習問題／5.8 探究的課題 |
|
第6章 確率的手法 |
|
6.1 基本的な数え上げ法／6.2 期待値法／6.3 条件付き期待値を用いた脱乱択化／6.4 標本抽出修正法／6.5 二次積率法／6.6 条件付き期待値の不等式／6.7 Lovaszの局所補題／6.8 局所補題を利用した具体的構成法／6.9 Lovaszの局所補題:一般の場合／6.10 練習問題 |
|
第7章 Markov連鎖と乱歩 |
|
7.1 Markov連鎖:定義と表現／7.2 状態の分類／7.3 定常分布／7.4 無向グラフ上の乱歩／7.5 Parrondoの逆理／7.6 練習問題 |
|
第8章 連続分布とPoisson過程 |
|
8.1 連続確率変数／8.2 一様分布／8.3 指数分布／8.4 Poisson過程／8.5 連続時間Markov過程／8.6 事例:Markov待ち行列／8.7 練習問題 |
|
第9章 エントロピー,ランダム性,情報 |
|
9.1 エントロピー関数／9.2 エントロピーと二項係数／9.3 エントロピー:ランダム性の尺度／9.4 圧縮／9.5 符号化:Shannonの定理／9.6 練習問題 |
|
第10章 モンテカルロ法 |
|
10.1 モンテカルロ法／10.2 応用:DNF数え上げ問題／10.3 近似標本抽出から近似数え上げへ／10.4 Markov連鎖モンテカルロ法／l0.5 練習問題／10.6 最小全域木についての探究的課題 |
|
第11章 Markov連鎖のカップリング法 |
|
11.1 変動距離と混合時間／11.2 カップリング法／11.3 応用:変動距離の非増加性／11.4 等比級数的収束／11.5 応用:真の彩色の近似標本抽出／11.6 経路カップリング法／11.7 練習問題 |
|
第12章 マルチンゲール |
|
12.1 マルチンゲール／12.2 停止時間／12.3 Waldの等式／12.4 マルチンゲールの裾確率／12.5 Azuma-Hoeffdingの不等式の応用／12.6 練習問題 |
|
第13章 対独立性と汎用ハッシュ関数 |
|
13.1 対独立性／13.2 対独立な変数に対するChebyshevの不等式／13.3 汎用ハッシュ関数族／13.4 応用:データ流の超過利用対の探索／13.5 練習問題 |
|
第14章 均等配分 |
|
14.1 二者択一の能力／14.2 二者択一の下界／14.3 二者択一の能力の応用／14.4 練習問題 |
