扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
中医基础理论
-
>
高校军事课教程
-
>
思想道德与法治(2021年版)
-
>
毛泽东思想和中国特色社会主义理论体系概论(2021年版)
-
>
中医内科学·全国中医药行业高等教育“十四五”规划教材
-
>
中医诊断学--新世纪第五版
-
>
中药学·全国中医药行业高等教育“十四五”规划教材
计算复杂性理论 版权信息
- ISBN：9787302627982
- 条形码：9787302627982 ; 978-7-302-62798-2
- 装帧：平装-胶订
- 册数：暂无
- 重量：暂无
- 所属分类：>>
计算复杂性理论 本书特色
本教材可作为以下课程的主参考书：（1）面向高年级本科生、研究生的“计算复杂性理论导论”课程；（2）面向研究生的“计算复杂性理论高等议题”课章；（3）面向高年级本科生、研究生的“高等算法”课程；（4）面向高年级本科生、研究生的“计算理论”课程。
计算复杂性理论 内容简介
本书是一本介绍计算复杂性理论的基础教材, 内容包括时间复杂性、空间复杂性、NP-理论、多项式谱 系、电路复杂性、随机计算及去随机、计数复杂性、交互证明系统、PCP 定理、近似计算与不可近似性。 本书的主要读者群是高年级本科生、硕士生、博士生，以及希望了解（更多）计算复杂性理论的教师 和科研工作者。本书可用于以下课程：（1）面向高年级本科生、研究生的“计算复杂性理论导论”课程， 内容涵盖前3 章；（2）面向研究生的“计算复杂性理论高等议题”课程，内容涵盖后3 章；（3）面向高年 级本科生、研究生的“算法理论”课程，涵盖第 4 章、第 6 章中有关随机算法和去随机、近似算法和不 可近似性的内容；（4）面向高年级本科生、研究生的“计算理论”课程，以第 1 章的内容为核心，并根 据学分多少和授课对象不同做适当补充。
计算复杂性理论 目录
第 1 章 计算理论 1
1.1 图灵机 5
1.2 时间可构造性 9
1.3 通用图灵机 10
1.4 对角线方法 15
1.5 丘奇-图灵论题 17
1.6 加速定理 21
1.7 时间复杂性类 24
1.8 非确定图灵机 26
1.9 命题逻辑 29
1.10 谓词逻辑 32
1.11 计算的逻辑刻画 34
1.12 时间谱系定理 37
1.13 间隙定理 41
1.14 神谕图灵机 42
1.15 归约 43
1.16 空间复杂性类 45
1.17 对数空间类 49
1.18 多项式空间类 52
1.19 对数空间的补封闭性 55
1.20 TIME(T(n))=SPACE(T(n)) 吗 58
第 1 章练习 63
第 2 章 难解性 65
2.1 可验证性 66
2.2 NP-完全性 68
2.3 库克-莱文定理 69
2.4 拉德纳定理 73
2.5 贝克-吉尔-索罗维定理 76
2.6 多项式谱系 78
2.7 谱系的逻辑刻画 80
2.8 谱系的交替机刻画 82
2.9 无限谱系假设 86
2.10 第二层中的完全问题 87
第 2 章练习 91
第 3 章 电路复杂性 93
3.1 电路谱系定理 96
3.2 一致电路 101
3.3 P/poly 103
3.4 并行计算 105
3.5 P-完全性 109
3.6 哈斯塔德对换引理 111
第 3 章练习 117
第 4 章 随机计算与去随机 119
4.1 随机算法 121
4.2 通用哈希函数族 136
4.3 概率图灵机 139
4.4 BPP 与 ZPP 141
4.5 PP 与 #P 146
4.6 积和式计算 151
4.7 户田定理 155
4.8 随机游走 159
4.9 蒙特卡罗方法 172
4.9.1 近似采样 175
4.9.2 马尔可夫链蒙特卡罗方法 185
4.9.3 均混时间 188
4.10 扩张图与去随机 195
4.10.1 线性代数相关知识 196
4.10.2 图的谱 200
4.10.3 扩张图 207
4.10.4 扩张图上的随机游走 215
4.11 扩张图的构造 219
4.11.1 扩张图的构造算子 220
4.11.2 固定大小扩张图构造 226
4.11.3 显式扩张图族 228
4.12 莱因戈尔德定理 231
第 4 章练习 234
第 5 章 交互证明系统 236
5.1 私币交互证明 239
5.2 公币交互证明 244
5.3 IP = PSPACE 252
5.4 两类系统的等价性 257
5.5 多证明者交互证明系统 262
5.5.1 定义 263
5.5.2 NEXP 的多证明者协议 268
5.6 多线性性测试算法 273
5.7 并行重复定理 279
5.7.1 统计距离、詹森不等式、相对熵 282
5.7.2 随机变量的近似嵌入 289
5.7.3 博弈的近似生成 293
5.7.4 证明的后一步 297
5.8 单回合双证明者交互系统 298
第 5 章练习 302
第 6 章 近似计算与不可近似性 304
6.1 近似算法 307
6.2 不可近似性 324
6.3 局部可验证性与不可近似性 327
6.4 错误放大 331
6.5 证明思想 334
6.6 线性增强 339
6.7 线性归减 343
6.8 PCP 定理的证明 345
6.9 布尔函数的分析技术 346
6.9.1 傅里叶展开式 348
6.9.2 卷积定理 350
6.9.3 BLR-测试 351
6.9.4 长码 353
6.10 哈斯塔德 3-比特 PCP-定理 357
6.10.1 哈斯塔德验证器 359
6.10.2 哈斯塔德算法的可靠性 361
6.11 阈值定理 364
第 6 章练习 369
参考文献 370
定理索引 371
图索引 373
术语索引 374
1.1 图灵机 5
1.2 时间可构造性 9
1.3 通用图灵机 10
1.4 对角线方法 15
1.5 丘奇-图灵论题 17
1.6 加速定理 21
1.7 时间复杂性类 24
1.8 非确定图灵机 26
1.9 命题逻辑 29
1.10 谓词逻辑 32
1.11 计算的逻辑刻画 34
1.12 时间谱系定理 37
1.13 间隙定理 41
1.14 神谕图灵机 42
1.15 归约 43
1.16 空间复杂性类 45
1.17 对数空间类 49
1.18 多项式空间类 52
1.19 对数空间的补封闭性 55
1.20 TIME(T(n))=SPACE(T(n)) 吗 58
第 1 章练习 63
第 2 章 难解性 65
2.1 可验证性 66
2.2 NP-完全性 68
2.3 库克-莱文定理 69
2.4 拉德纳定理 73
2.5 贝克-吉尔-索罗维定理 76
2.6 多项式谱系 78
2.7 谱系的逻辑刻画 80
2.8 谱系的交替机刻画 82
2.9 无限谱系假设 86
2.10 第二层中的完全问题 87
第 2 章练习 91
第 3 章 电路复杂性 93
3.1 电路谱系定理 96
3.2 一致电路 101
3.3 P/poly 103
3.4 并行计算 105
3.5 P-完全性 109
3.6 哈斯塔德对换引理 111
第 3 章练习 117
第 4 章 随机计算与去随机 119
4.1 随机算法 121
4.2 通用哈希函数族 136
4.3 概率图灵机 139
4.4 BPP 与 ZPP 141
4.5 PP 与 #P 146
4.6 积和式计算 151
4.7 户田定理 155
4.8 随机游走 159
4.9 蒙特卡罗方法 172
4.9.1 近似采样 175
4.9.2 马尔可夫链蒙特卡罗方法 185
4.9.3 均混时间 188
4.10 扩张图与去随机 195
4.10.1 线性代数相关知识 196
4.10.2 图的谱 200
4.10.3 扩张图 207
4.10.4 扩张图上的随机游走 215
4.11 扩张图的构造 219
4.11.1 扩张图的构造算子 220
4.11.2 固定大小扩张图构造 226
4.11.3 显式扩张图族 228
4.12 莱因戈尔德定理 231
第 4 章练习 234
第 5 章 交互证明系统 236
5.1 私币交互证明 239
5.2 公币交互证明 244
5.3 IP = PSPACE 252
5.4 两类系统的等价性 257
5.5 多证明者交互证明系统 262
5.5.1 定义 263
5.5.2 NEXP 的多证明者协议 268
5.6 多线性性测试算法 273
5.7 并行重复定理 279
5.7.1 统计距离、詹森不等式、相对熵 282
5.7.2 随机变量的近似嵌入 289
5.7.3 博弈的近似生成 293
5.7.4 证明的后一步 297
5.8 单回合双证明者交互系统 298
第 5 章练习 302
第 6 章 近似计算与不可近似性 304
6.1 近似算法 307
6.2 不可近似性 324
6.3 局部可验证性与不可近似性 327
6.4 错误放大 331
6.5 证明思想 334
6.6 线性增强 339
6.7 线性归减 343
6.8 PCP 定理的证明 345
6.9 布尔函数的分析技术 346
6.9.1 傅里叶展开式 348
6.9.2 卷积定理 350
6.9.3 BLR-测试 351
6.9.4 长码 353
6.10 哈斯塔德 3-比特 PCP-定理 357
6.10.1 哈斯塔德验证器 359
6.10.2 哈斯塔德算法的可靠性 361
6.11 阈值定理 364
第 6 章练习 369
参考文献 370
定理索引 371
图索引 373
术语索引 374
展开全部
计算复杂性理论 作者简介
傅育熙，1992年获英国曼彻斯特大学计算机博士学位，1994年起任职于上海交通大学计算机系，现为上海交通大学特聘教授，研究领域为理论计算机科学，是国家杰出青年基金获得者、上海市优秀学科带头人、Mathematical Structures in Computer Science的编委。曾任上海交通大学计算机系主任（2000-2009）、软件学院院长（2001-2013）、国务院学位委员会第六届学科评议组成员（2010-2014）、上海市计算机学会理事长（2015-2018）、教育部计算机类专业教学指导委员会副主任（2013-2022）。讲授的“计算复杂性理论”课程获得“2019年度高校计算机专业优秀教师奖励计划”。
书友推荐
- >
巴金－再思录
巴金－再思录
¥14.7¥46.0 - >
唐代进士录
唐代进士录
¥15.1¥39.8 - >
龙榆生：词曲概论/大家小书
龙榆生：词曲概论/大家小书
¥7.7¥24.0 - >
伊索寓言-世界文学名著典藏-全译本
伊索寓言-世界文学名著典藏-全译本
¥9.3¥19.0 - >
罗曼·罗兰读书随笔-精装
罗曼·罗兰读书随笔-精装
¥17.4¥58.0 - >
经典常谈
经典常谈
¥16.3¥39.8 - >
人文阅读与收藏·良友文学丛书:一天的工作
人文阅读与收藏·良友文学丛书:一天的工作
¥14.7¥45.8 - >
自卑与超越
自卑与超越
¥13.5¥39.8
本类畅销
-
食品添加剂
¥33.5¥45 -
VB语言程序设计
¥29.9¥39.8 -
C语言程序设计习题与实验指导
¥9.1¥18 -
地下建筑结构-(第三版)-(赠课件)
¥49.4¥55 -
模具制图
¥37.8¥49 -
工程机械结构认知
¥10.5¥22
