计算复杂性理论导引

图书标准信息

• 作者 陈原
• 出版社 西安电子科技大学出版社
• 出版时间 2021-07
• 版次 1
• ISBN 9787560659299
• 定价 24.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 156页
• 字数 224千字

【内容简介】

本书介绍了计算复杂性理论的一些基础知识，如计算模型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章 
...