第一章 绪论 1
1.1 大数据介绍 1
1.1.1 大数据浪潮汹涌澎湃 2
1.1.2 什么是大数据 3
1.1.3 大数据引领社会、经济和科技的发展 7
1.2 计算理论简介 9
1.2.1 可计算理论 9
1.2.2 计算复杂性度量 11
1.2.3 计算复杂类问题 12
1.3 大数据计算框架 13
1.3.1 大数据的泛构 13
1.3.2 大数据划分原理 14
1.3.3 大数据计算 14
第二章 图灵机与复杂度分类 17
2.1 确定型图灵机 17
2.2 非确定型图灵机 19
2.3 可计算性 21
2.3.1 可计算性定义与特性 21
2.3.2 可计算性理论的发展与意义 22
2.3.3 丘奇-图灵论题 22
2.3.4 不可计算性 24
2.4 计算复杂性理论 25
2.4.1 计算复杂性的发展 26
2.4.2 计算复杂性 27
2.4.3 形式语言 28
2.4.4 时间复杂度 30
2.4.5 空间复杂度 33
2.4.6 复杂度的分层 36
2.5 问题复杂性 38
2.5.1 问题的形式化描述 38
2.5.2 P类和NP类 43
2.5.3 NP完全问题 45
第三章 大数据泛构 61
3.1 大数据泛构的基本概念 62
3.1.1 应用软件获取高性价比的关键 62
3.1.2 大数据的度量空间表示 65
3.1.3 度量空间数据处理的基本法则 68
3.2 支撑点空间模型 70
3.2.1 支撑点空间 70
3.2.2 完全支撑点空间 74
3.2.3 采用欧几里得距离时的距离伸缩情况 76
3.3 大数据基于距离的划分 77
3.3.1 超平面划分 78
3.3.2 球形划分 80
3.3.3 划分方法的统一 81
第四章 大数据P类计算问题 90
4.1 大数据的并行NC计算 90
4.1.1 并行复杂性理论 90
4.1.2 NC计算和LNC计算 104
4.1.3 NC计算实例 112
4.2 P类问题快速近似计算 123
4.3 P类问题近似计算实例 127
第五章 大数据NP类计算问题 152
5.1 NP复杂类近似计算 153
5.2 近似归约 155
5.2.1 精确归约 155
5.2.2 近似归约 157
5.3 交互式证明系统与交互式计算 158
5.3.1 交互式证明系统 158
5.3.2 交互式计算 161
5.3.3 参数形式的交互式计算模型 166
5.4 交互式计算实例 176
第六章 大数据价值初探 192
6.1 大数据认知 193
6.2 数据价值 196
6.3 大数据价值定理 200
6.4 传播下的信息价值递减 205
6.4.1 传播模型的介绍(广告模型) 206
6.4.2 信息传播的构建 207
6.4.3 信息网络的模拟及评价 208
6.4.4 网络重构的预测 211
后记 216