隨機算法

內(nèi)容概要

本書是斯坦福一劍橋項目(Stanford-Cambridge Program)之一。    對于許多應(yīng)用，隨機算法是最簡單可行的，或者是最快的，或者兩者兼得。本書由該領(lǐng)域兩位著名專家寫成，給出了隨機算法設(shè)計和分析的基本概念，適用于接近研究生開始階段的水平。    本書的第一部分介紹了概率論的基本工具，以及在算法應(yīng)用中經(jīng)常使用的概率分析。為了說明每個工具的作用，在具體設(shè)置給出了一些算法示例。本書的第二部分為算法的應(yīng)用，共包括七章，每一章集中在隨機算法應(yīng)用的一個重要領(lǐng)域，如數(shù)據(jù)結(jié)構(gòu)、幾何算法、圖算法、數(shù)論、計數(shù)、并行算法及在線算法等。對于每個領(lǐng)域中的算法，做了全面并且具有代表性的選擇。    盡管本書基本按照教材寫成，也可作為一本有價值的參考書供專業(yè)人員和研究者使用。

書籍目錄

序言第一部分  工具與技巧　第1章  概述　  §1.1  最小切算法　  §1.2  Las Vegas和Monte Carlo　  §1.3  二分平面劃分　  §1.4  概率遞歸　  §1.5  計算模型和復(fù)雜性類 　 注釋  　問題　第2章  博弈論技術(shù)　  §2.1  博弈樹估值　  §2.2  最小化最大原則　  §2.3  隨機性與非均勻性 　 注釋  　問題　第3章  矩和偏差　  §3.1  占有問題　  §3.2  Markov和Chebyshev不等式　  §3.3  隨機選擇　  §3.4  兩點采樣　  §3.5  穩(wěn)定婚姻問題　  §3.6  優(yōu)惠券收集者問題 　 注釋  　問題　第4章  尾不等式　  §4.1  Chernoff界　  §4.2  并行計算機中的路由　  §4.3  布線問題　  §4.4  鞅(Martingale) 　 注釋  　問題　第5章  概率法　  §5.1  概率法概論　  §5.2  最大可滿足性　  §5.3  擴展圖　  §5.4  重審遺忘路由　  §5.5  Lovasz局部引理　  §5.6  條件概率法 　 注釋  　問題　第6章  Markov鏈和隨機游動　  §6.1  2-SAT問題　  §6.2  Markov鏈　  §6.3  圖上的隨機游動　  §6.4  電路網(wǎng)絡(luò)　  §6.5  覆蓋時間　  §6.6  圖的連通性　  §6.7  擴展以及快速混合隨機游動　  §6.8  擴展上的隨機游動得到概率放大 　 注釋  　問題　第7章  代數(shù)技術(shù)　  §7.1  指紋和Freivalds技術(shù)　  §7.2  驗證多項式　  §7.3  圖的完美匹配　  §7.4  驗證串的相等　  §7.5  指紋技術(shù)的比較　  §7.6  模式識別　  §7.7  交互證明系統(tǒng)　  §7.8  PCP和有效證明驗證 　 注釋  　問題第二部分  應(yīng)用　第8章  數(shù)據(jù)結(jié)構(gòu)　  §8.1  基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)問題　  §8.2  隨機Treap　  §8.3  跳表　  §8.4  哈希表　  §8.5  O(1)搜索時間的哈希 　 注釋  　問題　第9章  幾何算法與線性規(guī)劃　  §9.1  隨機增量構(gòu)造　  §9.2  平面上的凸包　  §9.3 幾何對偶　  §9.4  半空間的交　  §9.5  Delaunary三角劃分　  §9.6  梯形分解　  §9.7  二分空間劃分　  §9.8  點集合的直徑　  §9.9  隨機抽樣　  §9.1  0線性規(guī)劃 　 注釋  　問題　第10章  圖算法　  §10.1  所有點對之間的最短路徑問題　  §10.2  最小切問題　  §10.3  最小生成樹 　 注釋  　問題　第11章  近似計數(shù)　  §11.1  隨機近似方案　  §11.2  DNF計數(shù)問題　  §11.3  近似積和式　  §11.4  體積估計 　 注釋  　問題　第12章  并行分布式算法　  §12.1  PRAM模型　  §12.2  PRAM上的排序　  §12.3  極大獨立集　  §12.4  完美匹配　  §12.5  選擇協(xié)調(diào)問題　  §12.6  拜占庭協(xié)議 　 注釋  　問題　第13章  在線算法　  §13.1  在線頁面管理問題　  §13.2  對手模型　  §13.3  針對不經(jīng)意對手的頁面管理　  §13.4  對手間的相關(guān)性　  §13.5  適應(yīng)性在線對手　  §13.6  k-服務(wù)器問題 　 注釋  　問題　第14章  數(shù)論與代數(shù)　  §14.1  準(zhǔn)備知識　  §14.2  群和域　  §14.3  二次余數(shù)　  §14.4  RSA加密　  §14.5  多項式根及因式　  §14.6  素數(shù)檢測 　 注釋  　問題附錄A  符號索引附錄B  數(shù)學(xué)背景附錄C  基本概率論參考文獻索引

編輯推薦

　　《隨機算法》基本按照教材寫成，也可作為一本有價值的參考書供專業(yè)人員和研究者使用。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    隨機算法 PDF格式下載

---