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

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