隨機演演算法
隨機演演算法
§1.1 §1.2 §1.3
作 者：（美）莫特瓦尼，（美）拉格哈文 著，孫廣中，黃宇，李世勝 譯
隨機演演算法
出 版 社：高等教育出版社
出版時間：2008-10-1
版 次：1
頁 數：452
字 數：550000
印刷時間：2008-10-1
開 本：16開
紙 張：膠版紙
印 次：1
I S B N：9787040237238
包 裝：平裝
本書是斯坦福一劍橋項目(Stanford-Cambridge Program)之一。
對於許多應用，隨機演演算法是最簡單可行的，或者是最快的，或者兩者兼得。本書由該領域兩位著名專家寫成，給出了隨機演演算法設計和分析的基本概念，適用於接近研究生開始階段的水平。
本書的第一部分介紹了概率論的基本工具，以及在演演算法應用中經常使用的概率分析。為了說明每個工具的作用，在具體設置給出了一些演演算法示例。本書的第二部分為演演算法的應用，共包括七章，每一章集中在隨機演演算法應用的一個重要領域，如數據結構、幾何演演算法、圖演演算法、數論、計數、并行演演算法及在線演演算法等。對於每個領域中的演演算法，做了全面並且具有代表性的選擇。
儘管本書基本按照教材寫成，也可作為一本有價值的參考書供專業人員和研究者使用。
序言
第一部分 工具與技巧
第1章 概述
§1.1 最小切演演算法
§1.2 Las Vegas和Monte Carlo
§1.3 二分平面劃分
§1.4 概率遞歸
§1.5 計算模型和複雜性類
註釋
問題
第2章 博弈論技術
§2.1 博弈樹估值
§2.2 最小化最大原則
§2.3 隨機性與非均勻性
註釋
問題
第3章 矩和偏差
§3.1 佔有問題
§3.2 Markov和Chebyshev不等式
§3.3 隨機選擇
§3.4 兩點採樣
§3.5 穩定婚姻問題
§3.6 優惠券收集者問題
註釋
問題
第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 電路網路
§6.5 覆蓋時間
§6.6 圖的連通性
§6.7 擴展以及快速混合隨機遊動
§6.8 擴展上的隨機遊動得到概率放大
註釋
問題
第7章 代數技術
§7.1 指紋和Freivalds技術
§7.2 驗證多項式
§7.3 圖的完美匹配
§7.4 驗證串的相等
§7.5 指紋技術的比較
§7.6 模式識別
§7.7 交互證明系統
§7.8 PCP和有效證明驗證
註釋
問題
第二部分 應用
第8章 數據結構
§8.1 基礎數據結構問題
§8.2 隨機Treap
§8.3 跳錶
§8.4 哈希表
§8.5 O(1)搜索時間的哈希
註釋
問題
第9章 幾何演演算法與線性規劃
§9.1 隨機增量構造
§9.2 平面上的凸包
§9.3 幾何對偶
§9.4 半空間的交
§9.5 Delaunary三角劃分
§9.6 梯形分解
§9.7 二分空間劃分
§9.8 點集合的直徑
§9.9 隨機抽樣
§9.1 0線性規劃
註釋
問題
第10章 圖演演算法
§10.1 所有點對之間的最短路徑問題
§10.2 最小切問題
§10.3 最小生成樹
註釋
問題
第11章 近似計數
§11.1 隨機近似方案
§11.2 DNF計數問題
§11.3 近似積和式
§11.4 體積估計
註釋
問題
第12章 并行分散式演演算法
§12.1 PRAM模型
§12.2 pram上的排序
§12.3 極大獨立集
§12.4 完美匹配
§12.5 選擇協調問題
§12.6 拜占庭協議
註釋
問題
第13章 在線演演算法
§13.1 在線頁面管理問題
§13.2 對手模型
§13.3 針對不經意對手的頁面管理
§13.4 對手間的相關性
§13.5 適應性在線對手
§13.6 k-伺服器問題
註釋
問題
第14章 數論與代數
§14.1 準備知識
§14.2 群和域
§14.3 二次餘數
§14.4 RSA加密
§14.5 多項式根及因式
§14.6 素數檢測
註釋
問題
附錄A 符號索引
附錄B 數學背景
附錄C 基本概率論