《概率與計算》詳細地介紹了概率技術(shù)以及在概率算法與分析發(fā)展中使用過的范例�！陡怕逝c計算》分兩部分，第一部分介紹了隨機抽樣、期望、馬爾可夫不等式、切比雪夫不等式、切爾諾夫界、球和箱子模型、概率技術(shù)和馬爾可夫鏈等核心內(nèi)容。第二部分主要研究連續(xù)概率、有限獨立性的應(yīng)用、熵、馬爾可夫鏈蒙特卡羅方法、耦合、鞅和平衡配置等比較高深的課題。《概率與計算》適合作為高等院校計算機科學(xué)和應(yīng)用數(shù)學(xué)專業(yè)高年級本科生與低年級研究生的教材，也適合作為數(shù)學(xué)工作者和科技人員的參考書。
作者簡介
Michael Mitzenmacher 1996年于加州大學(xué)伯克利分校獲得博士學(xué)位，現(xiàn)為哈佛大學(xué)計算機科學(xué)教授。在1999年進入哈佛大學(xué)之前，他是Palo Alto數(shù)字系統(tǒng)研究實驗室的研究人員。他曾獲美國科學(xué)基金（NSF）CAAREER獎和Alfred P. Sloan研究基金。2002年，由于在糾錯碼方面的出色工作，他獲得了IEEE信息論學(xué)會的“最佳論文”獎。
目錄
譯者序前言第1章 事件與概率 1.1 應(yīng)用：驗證多項式恒等式 1.2 概率論公理 1.3 應(yīng)用：驗證矩陣乘法 1.4 應(yīng)用：最小割隨機化算法 練習(xí)第2章 離散隨機變量與期望 2.1 隨機變量與期望 2.2 伯努利隨機變量和二項隨機變量 2.3 條件期望 2.4 幾何分布 2.5 應(yīng)用：快速排序的期望運行時間 練習(xí)第3章 矩與離差 3.1 馬爾可夫不等式 3.2 隨機變量的方差和矩 3.3 切比雪夫不等式 3.4 應(yīng)用：計算中位數(shù)的隨機化算法 練習(xí)第4章 切爾諾夫界 4.1 矩母函數(shù) 4.2 切爾諾夫界的導(dǎo)出和應(yīng)用 4.3 某些特殊情況下更好的界 4.4 應(yīng)用：集合的均衡 4.5 應(yīng)用：稀疏網(wǎng)絡(luò)中的數(shù)據(jù)包路由選擇 練習(xí)第5章 球、箱子和隨機圖 5.1 例：生日悖論 5.2 球和箱子模型 5.3 泊松分布 5.4 泊松近似 5.5 應(yīng)用：散列法 5.6 隨機圖 練習(xí) 探索性作業(yè)第6章 概率方法 6.1 基本計數(shù)論證 6.2 期望論證 6.3 利用條件期望消除隨機化 6.4 抽樣和修改 6.5 二階矩方法 6.6 條件期望不等式 6.7 洛瓦茲局部引理 6.8 利用洛瓦茲局部引理的顯式構(gòu)造 6.9 洛瓦茲局部引理：一般情況 練習(xí)第7章 馬爾可夫鏈及隨機游動 7.1 馬爾可夫鏈：定義及表示 7.2 狀態(tài)分類 7.3 平穩(wěn)分布 7.4 無向圖上的隨機游動 7.5 Parrondo悖論 練習(xí)第8章 連續(xù)分布與泊松過程 8.1 連續(xù)隨機變量 8.2 均勻分布 8.3 指數(shù)分布 8.4 泊松過程 8.5 連續(xù)時間馬爾可夫過程 8.6 例：馬爾可夫排隊論 練習(xí)第9章 熵、隨機性和信息 9.1 熵函數(shù) 9.2 熵和二項式系數(shù) 9.3 熵：隨機性的測度 9.4 壓縮 9.5 編碼：香農(nóng)定理 練習(xí)第10章 蒙特卡羅方法 10.1 蒙特卡羅方法 10.2 應(yīng)用：DNF計數(shù)問題 10.3 從近似抽樣到近似計數(shù) 10.4 馬爾可夫鏈蒙特卡羅方法 練習(xí) 最小支撐樹的探索性作業(yè)第11章 馬爾可夫鏈的耦合 11.1 變異距離和混合時間 11.2 耦合 11.3 應(yīng)用：變異距離是不增的 11.4 幾何收斂 11.5 應(yīng)用：正常著色法的近似抽樣 11.6 路徑耦合 練習(xí)第12章 鞅 12.1 鞅 12.2 停時 12.3 瓦爾德方程 12.4 鞅的尾部不等式 12.5 Azuma?Hoeffding不等式的應(yīng)用 練習(xí)第13章 兩兩獨立及通用散列函數(shù) 13.1 兩兩獨立 13.2 兩兩獨立變量的切比雪夫不等式 13.3 通用散列函數(shù)族 13.4 應(yīng)用：在數(shù)據(jù)流中尋找重量級的源終點 練習(xí)第14章 平衡配置 14.1 兩種選擇的影響力 14.2 兩種選擇：下界 14.3 兩種選擇影響力的應(yīng)用 練習(xí) 進一步閱讀材料索引
譯者序前言第1章 事件與概率 1.1 應(yīng)用：驗證多項式恒等式 1.2 概率論公理 1.3 應(yīng)用：驗證矩陣乘法 1.4 應(yīng)用：最小割隨機化算法 練習(xí)第2章 離散隨機變量與期望 2.1 隨機變量與期望 2.2 伯努利隨機變量和二項隨機變量 2.3 條件期望 2.4 幾何分布 2.5 應(yīng)用：快速排序的期望運行時間 練習(xí)第3章 矩與離差 3.1 馬爾可夫不等式 3.2 隨機變量的方差和矩 3.3 切比雪夫不等式 3.4 應(yīng)用：計算中位數(shù)的隨機化算法 練習(xí)第4章 切爾諾夫界 4.1 矩母函數(shù) 4.2 切爾諾夫界的導(dǎo)出和應(yīng)用 4.3 某些特殊情況下更好的界 4.4 應(yīng)用：集合的均衡 4.5 應(yīng)用：稀疏網(wǎng)絡(luò)中的數(shù)據(jù)包路由選擇 練習(xí)第5章 球、箱子和隨機圖 5.1 例：生日悖論 5.2 球和箱子模型 5.3 泊松分布 5.4 泊松近似 5.5 應(yīng)用：散列法 5.6 隨機圖 練習(xí) 探索性作業(yè)第6章 概率方法 6.1 基本計數(shù)論證 6.2 期望論證 6.3 利用條件期望消除隨機化 6.4 抽樣和修改 6.5 二階矩方法 6.6 條件期望不等式 6.7 洛瓦茲局部引理 6.8 利用洛瓦茲局部引理的顯式構(gòu)造 6.9 洛瓦茲局部引理：一般情況 練習(xí)第7章 馬爾可夫鏈及隨機游動 7.1 馬爾可夫鏈：定義及表示 7.2 狀態(tài)分類 7.3 平穩(wěn)分布 7.4 無向圖上的隨機游動 7.5 Parrondo悖論 練習(xí)第8章 連續(xù)分布與泊松過程 8.1 連續(xù)隨機變量 8.2 均勻分布 8.3 指數(shù)分布 8.4 泊松過程 8.5 連續(xù)時間馬爾可夫過程 8.6 例：馬爾可夫排隊論 練習(xí)第9章 熵、隨機性和信息 9.1 熵函數(shù) 9.2 熵和二項式系數(shù) 9.3 熵：隨機性的測度 9.4 壓縮 9.5 編碼：香農(nóng)定理 練習(xí)第10章 蒙特卡羅方法 10.1 蒙特卡羅方法 10.2 應(yīng)用：DNF計數(shù)問題 10.3 從近似抽樣到近似計數(shù) 10.4 馬爾可夫鏈蒙特卡羅方法 練習(xí) 最小支撐樹的探索性作業(yè)第11章 馬爾可夫鏈的耦合 11.1 變異距離和混合時間 11.2 耦合 11.3 應(yīng)用：變異距離是不增的 11.4 幾何收斂 11.5 應(yīng)用：正常著色法的近似抽樣 11.6 路徑耦合 練習(xí)第12章 鞅 12.1 鞅 12.2 停時 12.3 瓦爾德方程 12.4 鞅的尾部不等式 12.5 Azuma?Hoeffding不等式的應(yīng)用 練習(xí)第13章 兩兩獨立及通用散列函數(shù) 13.1 兩兩獨立 13.2 兩兩獨立變量的切比雪夫不等式 13.3 通用散列函數(shù)族 13.4 應(yīng)用：在數(shù)據(jù)流中尋找重量級的源終點 練習(xí)第14章 平衡配置 14.1 兩種選擇的影響力 14.2 兩種選擇：下界 14.3 兩種選擇影響力的應(yīng)用 練習(xí) 進一步閱讀材料索引
|
