概率與計算

內(nèi)容概要

　　本書詳細(xì)地介紹了概率技術(shù)以及在概率算法與分析發(fā)展中使用過的范例。本書分兩部分，第一部分介紹了隨機抽樣、期望、馬爾可夫不等式、切比雪夫不等式、切爾諾夫界、球和箱子模型、概率技術(shù)和馬爾可夫鏈等核心內(nèi)容。第二部分主要研究連續(xù)概率、有限獨立性的應(yīng)用、熵、馬爾可夫鏈蒙特卡羅方法、耦合、鞅和平衡配置等比較高深的課題。　　本書適合作為高等院校計算機科學(xué)和應(yīng)用數(shù)學(xué)專業(yè)高年級本科生與低年級研究生的教材，也適合作為數(shù)學(xué)工作者和科技人員的參考書。

作者簡介

　　Michael Mitzenmacher 1996年于加州大學(xué)伯克利分校獲得博士學(xué)位，現(xiàn)為哈佛大學(xué)計算機科學(xué)教授。在1999年進(jìn)入哈佛大學(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í)進(jìn)一步閱讀材料索引

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    概率與計算 PDF格式下載

---