信息时代的计算机科学理论

第1章 引言

第2章 高维空间

2.1 高维空间的性质

2.2 高维球体

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

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

2.2.3 体积在赤道附近

2.2.4 体积在一个狭窄的环内

2.2.5 表面积在赤道附近

2.3 其他立方体的体积

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

2.5 高维中的高斯分布

2.6 尾概率的界限

2.7 随机投影和Johnson-Lindenstrauss定理

文献标记

练习

第3章 随机图

3.1 G（n，p）模型

3.1.1 度数分布

3.1.2 图G（n，d／n）中的三角形

3.2 相变

3.3 巨型分支

3.4 分支过程

3.5 回路和全连通

3.5.1 回路的出现

3.5.2 全连通性

3.5.3 直径O（lnn）的阈值

3.6 单调性的相变

3.7 CNF可满足性的相变

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

3.8.1 非均匀模型

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

3.9 增长模型

3.9.1 无优先连接的增长模型

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

3.1 0小世界效应图

文献标记

练习

第4章 奇异值分解（SVD）

4.1 奇异向量

4.2 奇异值分解（SVD）

4.3 最佳k阶逼近

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

4.5 奇异值分解的应用

4.5.1 主元分析

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

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

4.5.4 谱分解

4.5.5 奇异向量和文件评级

文献注记

练习

第5章 随机行走和Markov链

5.1 平稳分布

5.2 电路网络和随机行走

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

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

5.5 作为Markov链的万维网

5.6 Markov链MonteCarlo方法

5.6.1 Metropolis-Hastings算法

5.6.2 Gibbs取样

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

文献注记

练习

第6章 学习及VC维

6.1 学习

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

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

6.4 强与弱学习一推进

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

6.6 Vapnik-Chervonenkis（VC）维

6.6.1 集合系统及其VC维实例

6.6.2 粉碎函数

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

6.6.4 交集系统

6.7 VC定理

文献注记

练习

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

7.1 数据流的频数距

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

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

7.1.3 统计高频元素

7.1.4 二阶矩

7.2 大矩阵概要

7.2.1 利用抽样的矩阵乘法

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

7.3 文件概要

练习

第8章 聚类

8.1 若干聚类的例子

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

8.3 k均值聚类的Lloyd算法

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

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

8.6 核方法

8.7 凝聚聚类

8.8 社区，密集的子矩阵

8.9 流方法

8.10 线性规划

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

8.12聚类公理

8.12.1 不可能的结果

8.12.2 可满足集公理

练习

第9章 图模型和信念传播

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

9.2 马尔可夫随机场

9.3 因子图

9.4 树算法

9.5 消息传递算法

9.6 单环图

9.7 单回路网络的信念更新

9.8 最大权重匹配

9.9 警告传播

9.10 变量之间的相关性

练习

第10章 其他主题

10.1 排名

10.2 野兔投票系统

10.3 压缩传感和稀疏向量

10.3.1 稀疏向量的唯一重建

10.3.2 精确重建性

10.3.3 受限的等距属性

10.4 应用

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

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

10.4.3 生物

10.4.4 寻找重叠团或团体

10.4.5 低秩矩阵

练习

附录

附录1 渐近符号

附录2 有用的不等式

附录3 级数求和

附录4 概率

附录5 母函数

附录6 特征值与特征向量

附录7 其他内容

练习

参考文献

索引

《交大致远教材系列：信息时代的计算机科学理论》是上海交通大学致远教材系列之一，主要内容包括高维空间、随机图、奇异值分解、随机行走和马尔可夫链、学习算法和VC维、大规模数据问题的算法、聚类、图形模型和置信传播等，书后有附录及索引。《交大致远教材系列：信息时代的计算机科学理论》可作为计算机及相关专业高年级本科生或研究生的教材，也可供相关专业技术人员参考。