| 內容介紹 | |
開本：16開 紙張：膠版紙 包裝：平裝-膠訂 是否套裝：否 國際標準書號ISBN：9787111644118 作者：（美）邁克爾·米森馬徹（Michael 出版社：機械工業出版社 出版時間：2020年01月
"編輯推薦 本書是概率論與計算機科學相結合的完美教材。它繫統地介紹了概率論、隨機過程及樣本復雜度、VC 維度和拉德馬赫復雜度等理論知識，並介紹了使用本章理論去解決一些實際問題的算法設計技巧。 其目的在於幫助讀者學會如何利用概率論理論及計算機求解實際問題。本書覆蓋的知識面很廣，全書共分為兩部分，第壹部分介紹了隨機抽樣、期望、馬爾可夫不等式、切比雪夫不等式、切爾諾夫界、球和箱子模型、概率技術和馬爾可夫鏈等核心內容。第二部分主要研究連續概率、有限獨立性的應用、熵、馬爾可夫鏈蒙特卡羅方法、耦合、鞅及平衡配置等比較高深的內容。
本書可作為高年級本科生或低年級研究生的教材及教學參考書。
本書特色：
• 本書內容全面，結構嚴謹，幾乎所有定理都給出了詳細證明。
•本書所選例題和現實中的問題緊密相關，且大部分案例都是目前相關學科（如計算機網絡、圖論、機器學習等）的熱點問題。
• 許多案例常常給出多種求解方案，並分析比較這些方案的時間效率和空間效率。
• 本書的每一章都包含大量習題，且一些算法練習有可操作性的引導。
內容簡介 本書詳細地介紹了概率技術以及在概率算法與分析發展中使用過的範例。本書分兩部分，第壹部分介紹了隨機抽樣、期望、馬爾可夫不等式、切比雪夫不等式、切爾諾夫界、球和箱子模型、概率技術和馬爾可夫鏈等核心內容。第二部分主要研究連續概率、有限獨立性的應用、熵、馬爾可夫鏈蒙特卡羅方法、耦合、鞅和平衡配置等比較高深的課題。
本書適合作為高等院校計算機科學和應用數學專業高年級本科生與低年級研究生的教材，也適合作為數學工作者和科技人員的參考書。 作者簡介 邁克爾·米森馬徹（Michael Mitzenmacher）是哈佛大學的計算機科學教授，他於1996年在加州大學伯克利分校獲得博士學位。在1999年進入哈佛大學之前，他是PaloAlto數字繫統研究實驗室的研究員。他獲得了NSF職業獎和艾爾弗雷德·P·斯隆研究獎學金。2002年，他因在糾錯碼方面的工作而獲得IEEE信息理論學會“*佳論文”獎。
Eli Upfal是布朗大學計算機科學繫的教授、繫主任。他在以色列耶路撒冷的希伯來大學獲得了博士學位，在1997年進入布朗大學之前，他是IBM研究部的研究員，以色列魏茲曼科學研究所的教授。 他的主要研究興趣是隨機計算與算法的概率分析及其在優化算法中的應用， 通信網絡，並行和分布式計算，以及計算生物學等。
目錄 譯者序
第2版前言
第1版前言
第1章事件與概率1
1.1應用：驗證多項式恆等式1
1.2概率論公理2
1.3應用：驗證矩陣乘法6
1.4應用：樸素貝葉斯分類器9
1.5應用：小割隨機化算法11
1.6練習13
第2章離散型隨機變量與期望17
2.1隨機變量與期望17
2.1.1期望的線性性18
2.1.2詹森不等式19譯者序
第2版前言
第1版前言
第1章事件與概率1
1.1應用：驗證多項式恆等式1
1.2概率論公理2
1.3應用：驗證矩陣乘法6
1.4應用：樸素貝葉斯分類器9
1.5應用：小割隨機化算法11
1.6練習13
第2章離散型隨機變量與期望17
2.1隨機變量與期望17
2.1.1期望的線性性18
2.1.2詹森不等式19
2.2伯努利隨機變量和二項隨機變量20
2.3條件期望21
2.4幾何分布24
2.5應用：快速排序的期望運行時間27
2.6練習29
第3章矩與離差33
3.1馬爾可夫不等式33
3.2隨機變量的方差和矩33
3.3切比雪夫不等式36
3.4中位數和平均值38
3.5應用：計算中位數的隨機化算法40
3.5.1算法40
3.5.2算法分析41
3.6練習44
第4章切爾諾夫界與霍夫丁界46
4.1矩母函數46
4.2切爾諾夫界的導出和應用47
4.2.1泊松試驗和的切爾諾夫界47
4.2.2例：投擲硬幣50
4.2.3應用：估計參數50
4.3某些特殊情況下更好的界51
4.4應用：集合的均衡53
4.5霍夫丁界54
*4.6應用：稀疏網絡中的數據包路由選擇56
4.6.1超立方體網絡上排列的路由選擇56
4.6.2蝶形網絡上排列的路由選擇61
4.7練習65
第5章球、箱子和隨機圖69
5.1例：生日悖論69
5.2球放進箱子70
5.2.1球和箱子模型70
5.2.2應用：桶排序71
5.3泊松分布72
5.4泊松近似75
5.5應用：散列法81
5.5.1鏈散列81
5.5.2散列：二進制數字串82
5.5.3Bloom過濾器83
5.5.4放棄對稱性85
5.6隨機圖85
5.6.1隨機圖模型85
5.6.2應用：隨機圖中的哈密頓圈87
5.7練習92
5.8探索性作業95
第6章概率方法97
6.1基本計數論證97
6.2期望論證99
6.2.1應用：求割99
6.2.2應用：可滿足性100
6.3利用條件期望消除隨機化101
6.4抽樣和修改102
6.4.1應用：獨立集合102
6.4.2應用：有較大圍長的圖103
6.5二階矩方法103
6.6條件期望不等式105
6.7洛瓦茲局部引理107
6.7.1應用：邊不相交的路徑109
6.7.2應用：可滿足性109
*6.8利用洛瓦茲局部引理的顯式構造110
6.9洛瓦茲局部引理：一般情況113
*6.10洛瓦茲算法局部引理114
6.11練習118
第7章馬爾可夫鏈及隨機遊動122
7.1馬爾可夫鏈：定義及表示122
7.1.1應用：2可滿足性的隨機化算法124
7.1.2應用：3可滿足性的隨機化算法127
7.2狀態分類130
7.3平穩分布133
7.4無向圖上的隨機遊動138
7.5Parrondo悖論141
7.6練習144
第8章連續分布與泊松過程149
8.1連續隨機變量149
8.1.1R中的概率分布149
8.1.2聯合分布與條件概率150
8.2均勻分布152
8.3指數分布155
8.3.1指數分布的其他性質155
*8.3.2例：有反饋的球和箱子157
8.4泊松過程159
8.4.1到達間隔分布161
8.4.2組合與分解泊松過程162
8.4.3條件到達時間分布163
8.5連續時間馬爾可夫過程165
8.6例：馬爾可夫排隊論167
8.6.1均衡的M/M/1排隊167
8.6.2均衡的M/M/1/K排隊169
8.6.3M/M/∞排隊中的顧客數170
8.7練習171
第9章正態分布176
9.1正態分布176
9.1.1標準正態分布176
9.1.2一般單變量正態分布177
9.1.3矩母函數179
*9.2二項分布的極限180
9.3中心極限定理182
*9.4多維正態分布184
9.5應用：生成正態分布的隨機值187
9.6似然點估計189
9.7應用：針對混合高斯分布的EM算法192
9.8練習195
第10章熵、隨機性和信息198
10.1熵函數198
10.2熵和二項式繫數200
10.3熵：隨機性的測度201
10.4壓縮205
*10.5編碼：香農定理207
10.6練習213
第11章蒙特卡羅方法218
11.1蒙特卡羅方法218
11.2應用：DNF計數問題219
11.2.1樸素算法220
11.2.2DNF計數問題的完全多項式隨機方案221
11.3從近似抽樣到近似計數223
11.4馬爾可夫鏈蒙特卡羅方法226
11.5練習229
11.6小支撐樹的探索作業231
*第12章馬爾可夫鏈的耦合232
12.1變異距離和混合時間232
12.2耦合234
12.2.1例：洗牌235
12.2.2例:超立方體上的隨機遊動235
12.2.3例：固定大小的獨立集合236
12.3應用：變異距離是不增的237
12.4幾何收斂239
12.5應用：正常著色法的近似抽樣240
12.6路徑耦合243
12.7練習246
第13章鞅250
13.1鞅250
13.2停時251
13.3瓦爾德等式254
13.4鞅的尾部不等式256
13.5Azuma-Hoeffding不等式的應用257
13.5.1一般形式257
13.5.2應用：模式匹配259
13.5.3應用：球和箱子260
13.5.4應用：色數260
13.6練習260
第14章樣本復雜度、VC維度以及拉德馬赫復雜度264
14.1“學習”問題265
14.2VC維度266
14.2.1VC維度的其他例子267
14.2.2增長函數268
14.2.3VC維度的合成界269
14.2.4ε-網和ε-樣本270
14.3ε-網定理271
14.4應用：PAC學習274
14.5ε-樣本定理276
14.5.1應用：不可知學習279
14.5.2應用：數據挖掘279
14.6拉德馬赫復雜度281
14.6.1拉德馬赫復雜度和樣本錯誤283
14.6.2估計拉德馬赫復雜度284
14.6.3應用：二值分類的不可知學習285
14.7練習286
第15章兩兩獨立及通用散列函數288
15.1兩兩獨立288
15.1.1例：兩兩獨立的二進制數字的構造288
15.1.2應用：消去割算法的隨機性289
15.1.3例：構造關於一個素數模的兩兩獨立的值290
15.2兩兩獨立變量的切比雪夫不等式291
15.3通用散列函數族293
15.3.1例：一個2維通用散列函數族295
15.3.2例：強2維通用散列函數族295
15.3.3應用：完美散列297
15.4應用：在數據流中尋找重量級的源終點299
15.5練習302
第16章冪律及相關的分布305
16.1冪律分布：基本定義和性質305
16.2語言中的冪律307
16.2.1Zipf定律和其他例子307
16.2.2語言優化307
16.2.3猴子隨意打字308
16.3偏好鏈接309
16.4冪律在算法分析中的應用312
16.5其他相關的分布314
16.5.1對數正態分布314
16.5.2具有指數截斷的冪律315
16.6練習315
第17章平衡分配和布谷鳥散列318
17.1兩種選擇的影響力318
17.2兩種選擇：下界322
17.3兩種選擇影響力的應用324
17.3.1散列法324
17.3.2動態資源分配325
17.4布谷鳥散列325
17.5布谷鳥散列的擴展332
17.5.1帶刪除的布谷鳥散列332
17.5.2處理故障333
17.5.3更多的選擇和更大的箱子334
17.6練習335
延伸閱讀339 前言 第2版前言
本書的初版已經過了10年，隨著大數據分析、機器學習和數據挖掘的重要性越來越突出，概率方法對於計算機科學來說也變得越來越核心．許多相關領域的應用成果，其算法和思路都是建立在對概率與統計的成熟理解基礎之上的，要想正確地使用這些工具，對於這些數學概念的透徹理解是必不可少的．而第2版新增的主要內容就是著重於這些概念的介紹．
近年來，諸如萬維網、社交網絡、基因數據等使得我們能夠產生、收集和存儲大量的樣本數據集，這對我們建立模型和分析這些數據的結構提出了新的挑戰．熟練掌握一些標準的分布可以給建立和分析模型打下一個好的基礎，新增的第9章包含了絕大多數常見的統計分布，同時也像之前一樣，會強調這些分布在計算機科學中如何應用，比如確定分布的尾界等．然而，諸如萬維網和社交網絡等現代數據集有著一個奇妙的現像，在其中我們往往見不到正態分布，取而代之的是一種有著非常不同性質的、很少見的、特征明顯的重尾分布．例如，在萬維網中，一些頁面經常會有大量的網頁鏈接它們，其被鏈接的數量要高過平均水平一個數量級．第2版新增的第16章將包含對於建模和理解這種現代數據集來說非常重要的那些特殊分布．第2版前言
本書的初版已經過了10年，隨著大數據分析、機器學習和數據挖掘的重要性越來越突出，概率方法對於計算機科學來說也變得越來越核心．許多相關領域的應用成果，其算法和思路都是建立在對概率與統計的成熟理解基礎之上的，要想正確地使用這些工具，對於這些數學概念的透徹理解是必不可少的．而第2版新增的主要內容就是著重於這些概念的介紹．
近年來，諸如萬維網、社交網絡、基因數據等使得我們能夠產生、收集和存儲大量的樣本數據集，這對我們建立模型和分析這些數據的結構提出了新的挑戰．熟練掌握一些標準的分布可以給建立和分析模型打下一個好的基礎，新增的第9章包含了絕大多數常見的統計分布，同時也像之前一樣，會強調這些分布在計算機科學中如何應用，比如確定分布的尾界等．然而，諸如萬維網和社交網絡等現代數據集有著一個奇妙的現像，在其中我們往往見不到正態分布，取而代之的是一種有著非常不同性質的、很少見的、特征明顯的重尾分布．例如，在萬維網中，一些頁面經常會有大量的網頁鏈接它們，其被鏈接的數量要高過平均水平一個數量級．第2版新增的第16章將包含對於建模和理解這種現代數據集來說非常重要的那些特殊分布．
機器學習是近年來計算機科學領域的重大成果之一，它提供了許多高效的工具來建模、理解和預測大數據．但是預測的準確性，特別是準確性和樣本容量的關繫這一點卻常常被人忽略．第2版中新增的第14章將會對這些重要的內容進行詳細的介紹．
在新版中，我們也對之前的部分內容進行了充實和更新．例如，我們介紹了重要的洛瓦茲局部引理的算法變化的一些新進展，也新增了一小節用來介紹布谷鳥散列這種享譽盛名且越來越實用的散列法．後，除了這些新增內容，新版也包括了修正、勘誤和許多新習題．
我們對幾年來向我們發送了諸多勘誤的讀者表示由衷的感謝，可惜人數過於眾多，我們在此不一一列出了，還望海涵．
第1版前言
為什麼要研究隨機性
計算機科學家為什麼要研究和使用隨機性呢?這是因為計算機出現了太多不可預見的狀況!加入隨機性似乎是一個缺點,它使得有效地使用計算機這種已經具有挑戰性的工作變得更加復雜．
從20世紀開始,科學研究已經將隨機性視為建模和分析中的基本組成部分．例如,在物理學上,牛頓定律使人們相信宇宙的位置是確定的:如果有一個足夠大的計算工具和合適的初始條件,人們可以確定若干年後行星的位置．然而量子理論的發展卻提出了不同的觀點:宇宙仍舊按照自然法則運轉,但是這些自然法則的核心是隨機性的．“上帝不會同宇宙玩骰子”，這是愛因斯坦用來反駁現代量子力學的一句名言．然而,當代亞微粒子物理學的主要理論仍然是建立在隨機現像和統計規律基礎之上的,並且在從生物學的遺傳與進化到自由市場經濟的價格波動模型等幾乎所有其他科學領域中,隨機性都起著非常重要的作用．
計算機科學也不例外，從一些概率定理證明的高深理論到個人計算機以太網卡的實用性設計,隨機性和概率方法在現代計算機科學中都扮演了關鍵角色．過去20年以來,概率論在計算中的應用得到了巨大的發展,越來越高級、越來越復雜的概率技術已經被應用於更加廣泛和更富挑戰性的計算機科學應用中．在本書中,我們主要研究隨機性應用於計算機科學的基本方法:隨機化算法和算法的概率分析．
隨機化算法:隨機化算法是執行過程中要求作隨機選擇的算法．實際上,隨機化程序會使用由隨機數發生器產生的數值,從若干執行分支中決定下一步執行哪個分支．例如,以太網卡協議用隨機數決定何時試圖訪問共享的以太網通信介質．隨機性在打破對稱性、防止不同的以太網卡同時重復訪問介質方面是非常有用的．隨機化算法的其他常見應用還包括蒙特卡羅模擬和密碼學中的初始檢驗．在這些以及其他重要應用中,隨機化算法比有名的確定性方法更有效,並且在大多數情況下更簡單,更容易編寫程序．
當然，這些優點也是需要付出一定代價的,問題的答案在一定的概率下是不正確的,或者隻以某個概率保證有效．雖然設計一個有可能錯誤的算法似乎有點奇怪,但是如果錯誤發生的概率很小,那麼提高運行速度和減少占用的內存是有價值的．
算法的概率分析:復雜性理論根據計算的復雜性對問題進行分類,尤其是區分簡單問題和有難度的問題．例如,復雜性理論認為流動推銷員問題是一個NP難題．如果城市數量以次指數增長,那麼不可能存在可以解決流動推銷員問題的任何一個實用的算法．對於經典的壞情況復雜性理論,一個令人困惑的現像是,在分類上屬於有難度的計算問題,實際上卻很容易解決，概率分析對這種現像給出了理論上的解釋．雖然對某些不合理的輸入數據,問題難以解決,但對大多數輸入(尤其是在日常的應用中),這些問題實際上卻容易解決．更確切地說,如果我們認為輸入是隨機選擇的結果,而隨機選擇是根據所有可能輸入數據集上的某個概率分布作出的,就很有可能得到一個易於解答的問題實例,而這些實例不能求解的概率是相對較小的．算法的概率分析是研究當輸入來自某一適當定義的概率空間時算法如何運行的一種方法．書中我們將會看到,即使是NP難題,也會有對於幾乎所有輸入都極其有效的算法．
關於本書
本書可以
| | |
|
