隨機(jī)算法

內(nèi)容概要

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

書(shū)籍目錄

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

編輯推薦

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    隨機(jī)算法 PDF格式下載

---