计算复杂理论 大中专理科计算机 傅育熙|责编:龙启铭 新华正版
￥ 49 6.2折 ￥ 79 全新
库存11件
河北保定
认证卖家担保交易快速发货售后保障
作者傅育熙|责编:龙启铭
出版社清华大学
ISBN9787302627982
出版时间2023-05
版次1
装帧平装
开本16
页数379页
字数0.53千字
定价79元
货号303_9787302627982
上书时间2024-07-23
- 在售商品 暂无
- 平均发货时间 25小时
- 好评率 暂无
- 最新上架
商品详情
- 品相描述：全新
- 正版特价新书
- 商品描述
-
主编：
本教材可作为以下课程的主参书：（1）面向高年级本科生、的“计算复杂理论导论”课程；（2）面向的“计算复杂理论高等议题”课章；（3）面向高年级本科生、的“高等算法”课程；（4）面向高年级本科生、的“计算理论”课程。
目录：
章 计算理论
1.1 图灵机
1.2 时间可构造
1.3 通用图灵机
1.4 对角线方法
1.5 丘奇-图灵论题
1.6 加速定理
1.7 时间复杂类
1.8 非确定图灵机
1.9 命题逻辑
1.10 谓词逻辑
1.11 计算的逻辑刻画
1.12 时间谱系定理
1.13 间隙定理
1.14 神谕图灵机
1.15 归约
1.16 空间复杂类
1.17 对数空间类
1.18 多项式空间类
1.19 对数空间的补封闭
1.20 time（t（n））=space（t（n））吗
章练
第2章 难解
2.1 可验证
2.2 np-接近
2.3 库克-莱文定理
2.4 拉德纳定理
2.5 贝克-吉尔-索罗维定理
2.6 多项式谱系
2.7 谱系的逻辑刻画
2.8 谱系的交替机刻画
2.9 无限谱系设
2.10 第二层中的接近问题
第2章练
第3章 电路复杂
3.1 电路谱系定理
3.2 一致电路
3.3 p/poly
3.4 并行计算
3.5 p-接近
3.6 哈斯塔德对换引理
第3章练
第4章 计算与去
4.1 算法
4.2 通用哈希函数族
4.3 概率图灵机
4.4 bpp与zpp
4.5 pp与#p
4.6 积和式计算
4.7 户田定理
4.8 游走
4.9 蒙特卡罗方法
4.9.1 近似采样
4.9.2 马尔可夫链蒙特卡罗方法
4.9.3 均混时间
4.10 扩张图与去
4.10.1 线代数相关知识
4.10.2 图的谱
4.10.3 扩张图
4.10.4 扩张图上的游走
4.11 扩张图的构造
4.11.1 扩张图的构造算子
4.11.2 固定大小扩张图构造
4.11.3 显式扩张图族
4.12 莱因戈尔德定理
第4章练
第5章 交互证明系统
5.1 私币交互证明
5.2 公币交互证明
5.3 ip=pace
5.4 两类系统的等价
5.5 多证明者交互证明系统
5.5.1 定义
5.5.2 nexp的多证明者协议
5.6 多线测试算法
5.7 并行重复定理
5.7.1 统计距离、詹森不等式、相对熵
5.7.2 变量的近似嵌入
5.7.3 博弈的近似生成
5.7.4 证明的后一步
5.8 单回合双证明者交互系统
第5章练
……
内容简介：
本书是一本介绍计算复杂理论的基础教材 内容包括时间复杂、空间复杂、np理论、多项式谱
系、电路复杂、计算及去、复杂、交互证明系统、pcp 定理、近似计算与不可近似。
本书的主要读者群是高年级本科生、硕士生、博士生，以及希望了解（更多）计算复杂理论的教师
和科研工作者。本书可用于以下课程：（1）面向高年级本科生、的“计算复杂理论导论”课程，
内容涵盖前3 章；（2）面向的“计算复杂理论高等议题”课程，内容涵盖后3 章；（3）面向高年
级本科生、的“算法理论”课程，涵盖第 4 章、第 6 章中有关算法和去、近似算法和不
可近似的内容；（4）面向高年级本科生、的“计算理论”课程，以 章的内容为核心，并根
据学分多少和授课对象不同做适当补充。
— 没有更多了 —
以下为对购买帮助不大的评价