从计算理论到大数据图灵机(精)/大数据科学丛书

第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 不同时间复杂度的比较