扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
全国计算机等级考试最新真考题库模拟考场及详解·二级MSOffice高级应用
-
>
决战行测5000题(言语理解与表达)
-
>
软件性能测试.分析与调优实践之路
-
>
第一行代码Android
-
>
C Primer Plus 第6版 中文版
-
>
深度学习
-
>
MATLAB计算机视觉与深度学习实战-赠在线交流卡和本书源码
计算复杂性理论导引 版权信息
- ISBN：9787560659299
- 条形码：9787560659299 ; 978-7-5606-5929-9
- 装帧：一般胶版纸
- 册数：暂无
- 重量：暂无
- 所属分类：>
计算复杂性理论导引 内容简介
本书介绍了计算复杂性理论的一些基础知识，如计算模型Turing 机、复杂性的度量与本质关系、P等不等于NP问题、空间复杂性等，还选择了一些适合密码学及信息安全专业学习的高级专题，如随机化算法、电路复杂性、交互式证明等进行了介绍。 本书的编写尽量少使用计算机专业术语，涉及的计算问题相对集中，避免学生因相关数学知识储备不够而造成困惑。对较难的定理证明，给出直观分析以增进学生的理解和消化。设置了合适数量和难度的习题，习题中的知识点也非常重要，通过给出适当提示，引导学生完成。 本书可作为密码学、信息安全及相关专业的“计算复杂性理论”课程的教材。
计算复杂性理论导引 目录
绪论 计算复杂性理论简介 1
0.1 计算复杂性理论的首要问题 1
0.2 计算复杂性理论与算法理论的区别 1
0.3 计算理论及其组成 1
0.4 计算复杂性理论与密码学的关系 2
第1章 计算模型——Turing机 3
1.1 常用术语和记号 3
1.2 Turing机 4
1.2.1 Turing机的基本模型 4
1.2.2 TM的形式化定义 5
1.2.3 TM的格局 5
1.2.4 TM举例 6
1.2.5 描述TM的不同方式 7
1.3 TM的稳健性 8
1.4 ChurchTuring命题 9
1.5 非确定性TM 10
1.6 通用TM 12
习题 12
第2章 计算任务与复杂性 13
2.1 关心的计算任务：判定语言 13
2.2 复杂性的度量 14
2.2.1 大O小o记号 15
2.2.2 时间/空间复杂性的定义 15
2.2.3 两个事实 17
2.2.4 采用大O记号的合理性——带压缩定理和线性加速定理 17
2.2.5 带数目的减少对时间复杂度和空间复杂度的影响 19
2.2.6 DTM与NDTM的时间复杂性关系 20
2.3 复杂性类 20
2.3.1 复杂性类的概念 20
2.3.2 TIME和SPACE之间的平凡(trivial)关系 21
习题 21
第3章 P与NP 23
3.1 P 类 23
3.1.1 P的定义 23
3.1.2 P的重要性 23
3.1.3 P中的问题 24
3.2 NP 类 25
3.2.1 NP的定义 25
3.2.2 NP中的问题 26
3.2.3 世纪难题 P =? NP 27
3.2.4 NP的等价定义 28
3.3 coNP与coNP=? NP 29
习题 31
第4章 归约与NP完全性 32
4.1 历史背景 32
4.2 归约 32
4.2.1 Cook归约 32
4.2.2 Karp归约 33
4.2.3 Levin归约 34
4.3 NP完全性 35
4.4 CookLevin定理 36
4.5 更多NP完全问题 40
4.6 其他NPC问题 43
习题 44
第5章 关于P和NP的更多知识 46
5.1 查找与判定：NPC问题的自归约特性 46
5.1.1 SAT的自归约特性 46
5.1.2 CLIQUE的自归约特性 47
5.1.3 NPC问题都满足自归约特性 48
5.2 NPI语言 49
5.3 P vs NP 50
5.3.1 哈密尔顿回路vs 欧拉回路 50
5.3.2 三色vs四色 51
5.3.3 3SAT vs 2SAT 51
5.4 Oracle TM——相对化 54
习题 56
第6章 对角化方法 57
6.1 对角化方法与不可判定问题的存在性 57
6.1.1 可数集与对角化方法 57
6.1.2 不可判定问题的存在性 58
6.1.3 停机问题不可判定 60
6.2 分层定理 62
6.2.1 空间、时间可构造函数 62
6.2.2 分层定理 63
6.2.3 非确定性时间分层定理 66
6.3 定理A的证明 67
6.4 Ladner定理的证明 69
6.5 复杂性理论常用证明方法总结 70
习题 70
第7章 空间复杂性 72
7.1 PSPACE类 72
7.1.1 Savitch定理 72
7.1.2 PSPACE完全性 74
7.1.3 定理B的证明 76
7.2 L和NL类 77
7.2.1 空间有界的TM 77
7.2.2 L和NL 78
7.2.3 NL完全性 80
7.2.4 NL=coNL 83
习题 85
第8章 随机化算法与随机化复杂性类 87
8.1 随机化算法实例 87
8.1.1 通信复杂性 87
8.1.2 多项式恒等测试 89
8.2 概率图灵机 91
8.3 随机化复杂性类 92
8.3.1 单边错复杂性类：RP和coRP 92
8.3.2 双边错复杂性类：BPP 94
8.3.3 零边错复杂性类：ZPP 96
8.3.4 PP 97
8.4 随机化复杂性类与其他复杂性类之间的关系 99
8.5 素数问题PRIME 101
8.5.1 PRIME∈NP 102
8.5.2 PRIME∈coRP 104
8.5.3 PRIME∈P 105
习题 106
第9章 密码学与复杂性理论 107
9.1 单向函数 107
9.2 伪随机发生器 109
9.3 信息论安全与计算安全 110
第10章 电路复杂性 111
10.1 布尔电路 111
10.2 电路复杂性与P/poly复杂性类 113
10.3 P/poly复杂性类 115
10.4 一致布尔电路 117
10.5 并行计算与Nick复杂性类 118
10.6 BPPP/poly 120
习题 121
第11章 多项式分层 123
11.1 定义与实例 123
11.2 PH的内部结构 124
11.3 交错式TM与PH的等价定义 125
11.4 PH坍塌 127
习题 129
第12章 交互式证明 130
12.1 IP 131
12.2 公开/保密的随机性 133
12.3 IP=PSPACE 135
12.4 零知识证明 141
12.5 概率可验证明(PCP) 143
参考文献 145
展开全部
书友推荐
- >
巴金－再思录
巴金－再思录
¥33.1¥46.0 - >
名家带你读鲁迅:朝花夕拾
名家带你读鲁迅:朝花夕拾
¥10.5¥21.0 - >
李白与唐代文化
李白与唐代文化
¥9.9¥29.8 - >
经典常谈
经典常谈
¥17.1¥39.8 - >
新文学天穹两巨星--鲁迅与胡适/红烛学术丛书(红烛学术丛书)
新文学天穹两巨星--鲁迅与胡适/红烛学术丛书(红烛学术丛书)
¥11.0¥23.0 - >
诗经-先民的歌唱
诗经-先民的歌唱
¥15.1¥39.8 - >
中国人在乌苏里边疆区:历史与人类学概述
中国人在乌苏里边疆区:历史与人类学概述
¥24.0¥48.0 - >
伊索寓言-世界文学名著典藏-全译本
伊索寓言-世界文学名著典藏-全译本
¥6.1¥19.0
本类畅销
-
数学之美
¥48.3¥69 -
浪潮之巅-下册-第二版
¥22.1¥45 -
挑战程序设计竞赛(第2版)
¥55.3¥79 -
算法竞赛入门经典-(第2版)
¥34.9¥49.8 -
2022图书×抽奖盲袋
¥9.9¥25 -
2023读书月阅读盲盒——天黑，闭眼，刀谁？
¥42.3¥158
