大数据计算理论基础：并行和交互式计算

　　《大数据计算理论基础：并行和交互式计算》研究大数据的计算理论基础，重点讲述P类和NP类问题的并行和交互式计算方法。即在大数据的场景下，对于P类问题，为了提高求解速度可以采用并行的方法；对于NP类问题，为了提高解的质量可以采用交互的方法。
　　《大数据计算理论基础：并行和交互式计算》内容包括大数据的泛构理论（第三章），并行NC类计算、LNC类以及LL类计算（第四章），IP类计算和NC类函数逼近方法（第五章），同时对于大数据价值问题（第六章）进行讨论，为了便于阅读和学习，提供了预备知识绪论（第一章）和图灵机及复杂类问题介绍（第二章）。
　　《大数据计算理论基础：并行和交互式计算》框架清晰，内容翔实，对于一些经典问题有详细的证明，可作为高等学校计算机、计算数学以及相关专业的本科高年级学生和研究生的教学用书，亦可供从事高性能并行计算相关工作的科技人员阅读参考。

第一章 绪论
1．1 大数据介绍
1．1．1 大数据浪潮汹涌澎湃
1．1．2 什么是大数据
1．1．3 大数据引领社会、经济和
1．2 计算理论简介
1．2．1 可计算理论
1．2．2 计算复杂性度量
1．2．3 计算复杂类问题
1．3 大数据计算框架
1．3．1 大数据的泛构
1．3．2 大数据划分原理
1．3．3 大数据计算

第二章 图灵机与复杂度分类
2．1 确定型图灵机
2．2 非确定型图灵机
2．3 可计算性
2．3．1 可计算性定义与特性
2．3．2 可计算性理论的发展与意义
2．3．3 丘奇-图灵论题
2．3．4 不可计算性
2．4 计算复杂性理论
2．4．1 计算复杂性的发展
2．4．2 计算复杂性
2．4．3 形式语言
2．4．4 时间复杂度
2．4．5 空间复杂度
2．4．6 复杂度的分层
2．5 问题复杂性
2．5．1 问题的形式化描述
2．5．2 P类和NP类
2．5．3 NP完全问题

第三章 大数据泛构
3．1 大数据泛构的基本概念
3．1．1 应用软件获取高性价比的关键
3．1．2 大数据的度量空间表示
3．1．3 度量空间数据处理的基本法则
3．2 支撑点空间模型
3．2．1 支撑点空间
3．2．2 完全支撑点空间
3．2．3 采用欧几里得距离时的距离伸缩情况
3．3 大数据基于距离的划分
3．3．1 超平面划分
3．3．2 球形划分
3．3．3 划分方法的统一

第四章 大数据P类计算问题
4．1 大数据的并行NC计算
4．1．1 并行复杂性理论
4．1．2 NC计算和LNC计算
4．1．3 NC计算实例
4．2 P类问题快速近似计算
4．3 P类问题近似计算实例

第五章 大数据NP类计算问题
5．1 NP复杂类近似计算
5．2 近似归约
5．2．1 精确归约
5．2．2 近似归约
5．3 交互式证明系统与交互式计算
5．3．1 交互式证明系统
5．3．2 交互式计算
5．3．3 参数形式的交互式计算模型
5．4 交互式计算实例

第六章 大数据价值初探
6．1 大数据认知
6．2 数据价值
6．3 大数据价值定理
6．4 传播下的信息价值递减
6．4．1 传播模型的介绍（广告模型）
6．4．2 信息传播的构建
6．4．3 信息网络的模拟及评价
6．4．4．网络重构的预测
后记

　　《大数据计算理论基础：并行和交互式计算》：
　　目前，并行计算机和相关的并行计算技术已得到了广泛的发展和应用。在问题求解算法的串行时间复杂度已接近或达到其理论下界时，并行计算是唯独能够保证准确求解且有效缩短求解时间的方法。然而，并非所有问题都可以通过并行计算方法快速求解，有些问题即使使用了相对多的处理器也似乎很难并行求解。因此，一种可行的方法是将问题按照可并行性进行分类，而可并行性通常有以下两种描述方式。
　　（1）对于一个问题，如果处理器个数p在一定范围内，例如1≤p≤a（n），这里a（n）是某个关于问题输入规模n的递增函数，该问题都可以较快地求解，则称该问题是易并行化的。这里所谓“较快地求解”，通常是指并行算法的执行速度达到最快串行算法的（p）倍，即达到线性加速比。
　　……