本书研究大数据的计算理论基础，重点讲述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.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 网络重构的预测
- 后记
