交大致远教材系列：信息时代的计算机科学理论

图书标准信息

• 作者 [美]约翰·霍普克罗夫特、[美]拉文德兰·坎南 著；阮娜、龙宇、刘卫东 译
• 出版社 上海交通大学出版社
• 出版时间 2014-06
• 版次 1
• ISBN 9787313111098
• 定价 60.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 388页
• 字数 445千字
• 正文语种 简体中文
• 丛书 交大致远教材系列

【内容简介】

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

【目录】

第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.1G（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.7CNF可满足性的相变
3.8随机图的非均匀模型和成长模型
3.8.1非均匀模型
3.8.2给定度数分布的随机图中的巨型分支
3.9增长模型
3.9.1无优先连接的增长模型
3.9.2具有优先连接的增长模型
3.10小世界效应图
文献标记
练习

第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.6Markov链MonteCarlo方法
5.6.1Metropolis-Hastings算法
5.6.2Gibbs取样
5.7无向图上随机行走的收敛性
文献注记
练习

第6章学习及VC维
6.1学习
6.2线性分类器、感知器算法、边缘
6.3非线性分类器、支持向量机、核
6.4强与弱学习一推进
6.5预测中所需样本个数VC维
6.6Vapnik-Chervonenkis（VC）维
6.6.1集合系统及其VC维实例
6.6.2粉碎函数
6.6.3有界VC维集合系统的粉碎函数
6.6.4交集系统
6.7VC定理
文献注记
练习

第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.3k均值聚类的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其他内容
练习
参考文献
索引