信息时代的计算机科学理论PDF电子书下载

第1章 引言 1

第2章 高维空间 3

2.1 高维空间的性质 6

2.2 高维球体 6

2.2.1 高维空间的球体和立方体 7

2.2.2 单位球体的体积和表面积 8

2.2.3 体积在赤道附近 11

2.2.4 体积在一个狭窄的环内 14

2.2.5 表面积在赤道附近 14

2.3 其他立方体的体积 16

2.4 在球体表面随机生成均匀分布的点 17

2.5 高维中的高斯分布 18

2.6 尾概率的界限 25

2.7 随机投影和Johnson-Lindenstrauss定理 27

文献标记 30

练习 31

第3章 随机图 38

3.1 G（n,p）模型 38

3.1.1 度数分布 40

3.1.2 图G（n,d/n）中的三角形 44

3.2 相变 46

3.3 巨型分支 53

3.4 分支过程 60

3.5 回路和全连通 66

3.5.1 回路的出现 66

3.5.2 全连通性 67

3.5.3 直径O（ln n）的阈值 69

3.6 单调性的相变 71

3.7 CNF可满足性的相变 73

3.8 随机图的非均匀模型和成长模型 78

3.8.1 非均匀模型 78

3.8.2 给定度数分布的随机图中的巨型分支 78

3.9 增长模型 80

3.9.1 无优先连接的增长模型 80

3.9.2 具有优先连接的增长模型 88

3.10 小世界效应图 89

文献标记 93

练习 93

第4章 奇异值分解（SVD） 103

4.1 奇异向量 104

4.2 奇异值分解（SVD） 108

4.3 最佳k阶逼近 110

4.4 计算奇异值分解的幂方法 112

4.5 奇异值分解的应用 116

4.5.1 主元分析 116

4.5.2 球形正态混合的聚类分析 117

4.5.3 应用SVD于一个离散优化问题 122

4.5.4 谱分解 125

4.5.5 奇异向量和文件评级 125

文献注记 126

练习 127

第5章 随机行走和Markov链 134

5.1 平稳分布 137

5.2 电路网络和随机行走 139

5.3 具有单位边权重的无向图上的随机行走 144

5.4 欧几里得空间中的随机行走 151

5.5 作为Markov链的万维网 154

5.6 Markov链Monte Carlo方法 158

5.6.1 Metropolis-Hastings算法 162

5.6.2 Gibbs取样 163

5.7 无向图上随机行走的收敛性 165

文献注记 173

练习 173

第6章 学习及VC维 182

6.1 学习 182

6.2 线性分类器、感知器算法、边缘 184

6.3 非线性分类器、支持向量机、核 189

6.4 强与弱学习-推进 194

6.5 预测中所需样本个数：VC维 196

6.6 Vapnik-Chervonenkis（VC）维 199

6.6.1 集合系统及其VC维实例 199

6.6.2 粉碎函数 202

6.6.3 有界VC维集合系统的粉碎函数 203

6.6.4 交集系统 205

6.7 VC定理 206

文献注记 210

练习 210

第7章 海量数据问题的算法 216

7.1 数据流的频数距 216

7.1.1 在一个数据流中不同元素的个数 217

7.1.2 计算给定元素出现的次数 222

7.1.3 统计高频元素 222

7.1.4 二阶矩 224

7.2 大矩阵概要 228

7.2.1 利用抽样的矩阵乘法 229

7.2.2 利用行和列的取样近似矩阵 232

7.3 文件概要 234

练习 236

第8章 聚类 240

8.1 若干聚类的例子 240

8.2 一个简单的k聚类贪婪算法 242

8.3 k均值聚类的Lloyd算法 243

8.4 通过奇异值分解的有意义聚类 246

8.5 基于稀疏削减的递归聚类 251

8.6 核方法 255

8.7 凝聚聚类 257

8.8 社区，密集的子矩阵 259

8.9 流方法 262

8.10 线性规划 265

8.11 不检查全图地寻找本地群集 266

8.12 聚类公理 271

8.12.1 不可能的结果 272

8.12.2 可满足集公理 277

练习 279

第9章 图模型和信念传播 283

9.1 贝叶斯网络（信念网络） 284

9.2 马尔可夫随机场 285

9.3 因子图 286

9.4 树算法 286

9.5 消息传递算法 289

9.6 单环图 290

9.7 单回路网络的信念更新 291

9.8 最大权重匹配 293

9.9 警告传播 296

9.10 变量之间的相关性 297

练习 301

第10章 其他主题 302

10.1 排名 302

10.2 野兔投票系统 305

10.3 压缩传感和稀疏向量 306

10.3.1 稀疏向量的唯一重建 307

10.3.2 精确重建性 308

10.3.3 受限的等距属性 309

10.4 应用 312

10.4.1 在一些坐标基下的稀疏向量 312

10.4.2 一种表示方法不可能在时域和频域上同时稀疏 312

10.4.3 生物 315

10.4.4 寻找重叠团或团体 316

10.4.5 低秩矩阵 316

练习 317

附录 320

附录1 渐近符号 320

附录2 有用的不等式 321

附录3 级数求和 328

附录4 概率 333

附录5 母函数 350

附录6 特征值与特征向量 356

附录7 其他内容 371

练习 376

参考文献 382

索引 386