隨機算法

序言
第一部分 工具與技巧
　第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 基本概率論
參考文獻
索引