前辅文
第1章 计算理论概述
1.1 什么是计算理论
1.2 计算理论研究什么
1.3 为什么需要计算理论
1.4 怎么学习计算理论
第2章 计算模型
2.1 图灵是谁
2.2 中国的“图灵”
2.3 从算盘中抽象图灵机
2.4 形式化地表示图灵机
2.5 图灵机的运行
2.6 图灵机的格局
2.7 图灵机定义与每一次计算之间的关系
2.8 设计图灵机实体
2.9 怎样解决图灵机运行结果的错误
2.10 图灵机如何支持各种程序的运行
2.11 通用图灵机和专用图灵机的实现
2.12 图灵机与图灵机实现之间的对应关系
2.13 图灵机的运行
第3章 可计算性与计算复杂性概述
3.1 不同图灵机实现的计算能力有没有差异
3.2 如何衡量计算能力
3.3 为什么所有计算机的计算能力与图灵机相同
第4章 可计算性
4.1 图灵机是否会不停机
4.2 停机问题的解决
4.3 什么是可计算性
4.4 判定问题与计算问题的关系
4.5 一个问题是否可判定的证明
4.6 与停机问题等价的问题
4.7 可判定、半可判定、不可判定之间的关系
4.8 可判定、不可判定是否对应可计算、不可计算
4.9 可计算理论的意义
第5章 计算复杂性
5.1 什么是计算复杂性
5.2 为什么判定性问题的算法复杂性对计算性问题同样适用
5.3 如何衡量复杂程度
5.4 非确定型图灵机和确定型图灵机的区别
5.5 在多项式时间内猜出NP问题的解
5.6 如何不猜解求解NP问题
5.7 非确定型图灵机与确定型图灵机是否等价
5.8 P问题和NP问题的关系
5.9 P问题和NP问题对应的计算性问题
5.10 把可计算问题划分成P、指数型、NP、NPC、NPH问题
5.11 证明一个问题是NPC问题
5.12 定量地表示算法的时间复杂度
5.13 常见的算法时间复杂度
5.14 非多项式时间复杂度与多项式时间复杂度
5.15 多项式、非多项式时间复杂度与P、NP问题的关系
5.16 不同时间复杂度的比较
5.17 复杂度的形式化表示
5.18 算法复杂度的本质
5.19 时间复杂度和空间复杂度
5.20 关系复杂度
5.21 复杂算法的分解
5.22 确定问题的规模n
5.23 在规模相等的情况下的非多项式时间和多项式时间
5.24 降低算法的复杂度
5.25 问题复杂度和算法复杂度的区分
第6章 图灵机的大数据应用
6.1 大数据的特性
6.2 大数据应用对图灵机的需求
6.3 大数据应用图灵机
6.4 跳板大数据应用图灵机
6.5 耦合大数据应用图灵机
6.6 先验大数据应用图灵机
6.7 自适应大数据应用图灵机
6.8 增量大数据应用图灵机
6.9 自动大数据应用图灵机
6.10 分治大数据应用图灵机
6.11 冗余大数据应用图灵机
第7章 大数据图灵机
7.1 大数据图灵机的基本模型
7.2 大数据图灵机的可计算性
7.3 大数据的计算复杂度、存储复杂度和数据复杂度
7.4 数据计算复杂度的大O表示法
附录1 辩证发展科研创新法
附录2 习题
附录3 模拟题库
参考文献
