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