概率與計算：算法與數(shù)據(jù)分析中的隨機化和概率技術(shù)（原書第2版）

譯者序
第2版前言
第1版前言
第1章 事件與概率
1．1 應(yīng)用：驗證多項式恒等式
1．2 概率論公理
1．3 應(yīng)用：驗證矩陣乘法
1．4 應(yīng)用：樸素貝葉斯分類器
1．5 應(yīng)用：最小割隨機化算法
1．6 練習(xí)
第2章 離散型隨機變量與期望
2．1 隨機變量與期望
2．1．1 期望的線性性
2．1．2 詹森不等式
2．2 伯努利隨機變量和二項隨機變量
2．3 條件期望
2．4 幾何分布
2．5 應(yīng)用：快速排序的期望運行時間
2．6 練習(xí)
第3章 矩與離差
3．1 馬爾可夫不等式
3．2 隨機變量的方差和矩
3．3 切比雪夫不等式
3．4 中位數(shù)和平均值
3．5 應(yīng)用：計算中位數(shù)的隨機化算法
3．5．1 算法
3．5．2 算法分析
3．6 練習(xí)
第4章 切爾諾夫界與霍夫丁界
4．1 矩母函數(shù)
4．2 切爾諾夫界的導(dǎo)出和應(yīng)用
4．2．1 泊松試驗和的切爾諾夫界
4．2．2 例：投擲硬幣
4．2．3 應(yīng)用：估計參數(shù)
4．3 某些特殊情況下更好的界
4．4 應(yīng)用：集合的均衡
4．5 霍夫丁界
*4．6 應(yīng)用：稀疏網(wǎng)絡(luò)中的數(shù)據(jù)包路由選擇
4．6．1 超立方體網(wǎng)絡(luò)上排列的路由選擇
4．6．2 蝶形網(wǎng)絡(luò)上排列的路由選擇
4．7 練習(xí)
第5章 球、箱子和隨機圖
5．1 例：生日悖論
5．2 球放進箱子
5．2．1 球和箱子模型
5．2．2 應(yīng)用：桶排序
5．3 泊松分布
5．4 泊松近似
5．5 應(yīng)用：散列法
5．5．1 鏈散列
5．5．2 散列：二進制數(shù)字串
5．5．3 Bloom過濾器
5．5．4 放棄對稱性
5．6 隨機圖
5．6．1 隨機圖模型
5．6．2 應(yīng)用：隨機圖中的哈密頓圈
5．7 練習(xí)
5．8 探索性作業(yè)
第6章 概率方法
6．1 基本計數(shù)論證
6．2 期望論證
6．2．1 應(yīng)用：求最大割
6．2．2 應(yīng)用：最大可滿足性
6．3 利用條件期望消除隨機化
6．4 抽樣和修改
6．4．1 應(yīng)用：獨立集合
6．4．2 應(yīng)用：有較大圍長的圖
6．5 二階矩方法
6．6 條件期望不等式
6．7 洛瓦茲局部引理
6．7．1 應(yīng)用：邊不相交的路徑
6．7．2 應(yīng)用：可滿足性
*6．8 利用洛瓦茲局部引理的顯式構(gòu)造
6．9 洛瓦茲局部引理：一般情況
*6．10 洛瓦茲算法局部引理
6．11 練習(xí)
……
第7章 馬爾可夫鏈及隨機游動
第8章 連續(xù)分布與泊松過程
第9章 正態(tài)分布
第10章 熵、隨機性和信息
第11章 蒙特卡羅方法
第12章 馬爾可夫鏈的耦合
第13章 鞅
第14章 樣本復(fù)雜度、VC維度以及拉德馬赫復(fù)雜度
第15章 兩兩獨立及通用散列函數(shù)
第16章 冪律及相關(guān)的分布
第17章 平衡分配和布谷鳥散列
延伸閱讀