计算理论导引:第1版

计算理论导引
9.1
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者: [美]
出版社: 机械工业出版社
2000-02
版次: 1
ISBN: 9787111075745
定价: 30.00
装帧: 平装
开本: 其他
纸张: 胶版纸
页数: 273页
原版书名: Introduction to the Theory of Computation
  • 本书系统地介绍了计算理论的三个主要内容:自动机与语言、可计算性和计算复杂性。绝大部分内容是基本的,同时对可计算性和计算复杂性理论中的某些高级内容作了重点介绍。作者以清闲的笔触、生动的语言给出了宽泛的数学原理,而没有拘泥于某些低层次的细节。本书可作为计算机专业高年级本科生和研究生的教材,也可作为教师和研究人员的参考书。 张立昂,1941年2月出生,1965年毕业于北京大学数学力学系专业。现为北京大学计算机科学与技术系教授、博士生导师。主要研究方向:算法设计与分析、计算复杂性理论。著作有,可计算复杂性导引》等。          王捍贫,1964年7月出生,1993年毕业于北京师范大学数学 译者序

    前言

     第1章   导引

      1.1   自动机、可计算性与复杂性

       1.1.1   计算复杂性理论

       1.1.2   可计算性理论

       1.1.3    自动机理论

      1.2   数学概念和术语

       1.2.1   集合

       1.2.2   序列和多元组

       1.2.3   函数和关系

       1.2.4   图

       1.2.5   字符串和语言

       1.2.6   布尔逻辑

       1.2.7    数学名词汇总 

      1.3    定义、定理和证明

      1.4    证明的类型

       1.4.1    构造性证明

       1.4.2   反证法

       1.4.3   归纳法

      练习

      问题

    第一部分    自动机与语言

     第2 章   正则语言

      2.1   有穷自动机

       2.1.1    有穷自动机的形式定义

       2.1.2    有穷自动机举例

       2.1.3    计算的形式定义

       2.1.4   设计有穷自动机

       2.1.5   正则运算

      2.2   非确定性

       2.2.1   非确定型有穷自动机的形式定义

       2.2.2    NFA与DFA的等价性

       2.2.3    在正则运算下的封闭性 

      2.3    正则表达式

       2.3.1    正则表达式的形式定义

       2.3.2    与有穷自动机的等价性

      2.4    非正则语言

      练习

      问题

     第3章   上下文无关语言

      3.1    上下文无关文法

       3.1.1    上下文无关文法的形式定义

       3.1.2    上下文无关文法举例

       3.1.3    设计上下文无关文法

       3.1.4     歧义性

       3.1.5     乔姆斯基范式

      3.2    下推自动机

       3.2.1    下推自动机的形式定义

       3.2.2    下推自动机举例

       3.2.3     与上下文无关文法的等价性

      3.3     非上下文无关语言

      练习

      问题

    第二部分   可计算性理论

     第4章    丘奇—图灵论题

      4.1   图灵机

       4.1.1    图灵机的形式定义

       4.1.2    图灵机的例子

      4.2    图灵机的变形

       4.2.1    多带图灵机

       4.2.2     非确定型图灵机

       4.2.3     枚举器

       4.2.4    与其他模型的等价性

      4.3     算法的定义

       4.3.1    希尔伯特问题

       4.3.2    描述图灵机的术语

      练习

      问题

     第5章   可判定性

      5.1    可判定语言

       5.1.1     与正则语言相关的可判定性问题

       5.1.2    与上下文无关语言相关的可判定问题

      5.2    停机问题

       5.2.1    对角化方法

       5.2.2    停机问题是不可判定的

       5.2.3    一个图灵不可识别语言

      练习

      问题

     第6章    可归约性

      6.1    语言理论中的不可判定问题

      6.2     一个简单的不可判定问题

      6.3     映射可归约性

       6.3.1   可计算函数

       6.3.2    映射可归约性的形式定义

      练习

       问题

     第7 章    可计算性理论的高级专题

      7.1    递归定理 

       7.1.1    自引用

       7.1.2    应用递归定理的术语

       7.1.3   应用

      7.2    逻辑理论的可判定性

       7.2.1    一个可判定的理论

       7.2.2    一个不可判定的理论

      7.3     图灵可归约性

      7.4     信息的定义

       7.4.1    极小长度的描述

       7.4.2    定义的优化 

       7.4.3    不可压缩的串和随机性

      练习

      问题

    第三部分   复杂性理论 

     第8章   时间复杂性

      8.1    度量复杂性

       8.1.1    大O和小o记法

       8.1.2    分析算法

       8.1.3     模型间的复杂性关系

      8.2   P 类

       8.2.1   多项式时间

       8.2.2   P 中的问题举例

      8.3    NP类 

       8.3.1   NP中的问题举例

       8.3.2   P与NP问题

      8.4    NP完全性

       8.4.1     多项式时间可归约性

       8.4.2     NP完全性的定义

       8.4.3    库克—列文定理

      8.5    几个NP完全问题

       8.5.1    顶点覆盖问题

       8.5.2    哈密顿路径问题

       8.5.3    子集和问题

      练习

      问题

     第9章    空间复杂性

      9.1    萨维奇定理

      9.2    PSPACE类

      9.3   PSPACE完全性

       9.3.1     问题TQBF

       9.3.2    博奕的必胜策略

       9.3.3     广义地理学

      9.4     L类和NL学

      9.5    NL 完全性

      9.6    NL等于coNL

      练习

      问题

     第10章    难解性

      10.1   层次定理

      10.2    相对化

      10.3    电路复杂性 

      练习

      问题

     第 11章    复杂性理论中的高级专题

      11.1    近似算法

      11.2    概率算法

       11.2.1    BPP类

       11.2.2    素数性

       11.2.3    只读一次的分支程序

      11.3    交错式

       11.3.1    交错式时间与交错式空间

       11.3.2    多项式时间层次

      11.4     交互式证明系统

       11.4.1    图的非同构

       11.4.2    模型的定义

       11.4.3    IP=PSPACE

      11.5   并行计算

       11.5.1    一致布尔电路

       11.5.2    NC类

       11.5.3    P完全性

      11.6     密码学

       11.6.1     密钥

       11.6.2    公钥密码系统

       11.6.3    单向函数

       11.6.4     天窗函数 

      练习

      问题

      参考文献

      索引
  • 内容简介:
    本书系统地介绍了计算理论的三个主要内容:自动机与语言、可计算性和计算复杂性。绝大部分内容是基本的,同时对可计算性和计算复杂性理论中的某些高级内容作了重点介绍。作者以清闲的笔触、生动的语言给出了宽泛的数学原理,而没有拘泥于某些低层次的细节。本书可作为计算机专业高年级本科生和研究生的教材,也可作为教师和研究人员的参考书。
  • 作者简介:
    张立昂,1941年2月出生,1965年毕业于北京大学数学力学系专业。现为北京大学计算机科学与技术系教授、博士生导师。主要研究方向:算法设计与分析、计算复杂性理论。著作有,可计算复杂性导引》等。          王捍贫,1964年7月出生,1993年毕业于北京师范大学数学
  • 目录:
    译者序

    前言

     第1章   导引

      1.1   自动机、可计算性与复杂性

       1.1.1   计算复杂性理论

       1.1.2   可计算性理论

       1.1.3    自动机理论

      1.2   数学概念和术语

       1.2.1   集合

       1.2.2   序列和多元组

       1.2.3   函数和关系

       1.2.4   图

       1.2.5   字符串和语言

       1.2.6   布尔逻辑

       1.2.7    数学名词汇总 

      1.3    定义、定理和证明

      1.4    证明的类型

       1.4.1    构造性证明

       1.4.2   反证法

       1.4.3   归纳法

      练习

      问题

    第一部分    自动机与语言

     第2 章   正则语言

      2.1   有穷自动机

       2.1.1    有穷自动机的形式定义

       2.1.2    有穷自动机举例

       2.1.3    计算的形式定义

       2.1.4   设计有穷自动机

       2.1.5   正则运算

      2.2   非确定性

       2.2.1   非确定型有穷自动机的形式定义

       2.2.2    NFA与DFA的等价性

       2.2.3    在正则运算下的封闭性 

      2.3    正则表达式

       2.3.1    正则表达式的形式定义

       2.3.2    与有穷自动机的等价性

      2.4    非正则语言

      练习

      问题

     第3章   上下文无关语言

      3.1    上下文无关文法

       3.1.1    上下文无关文法的形式定义

       3.1.2    上下文无关文法举例

       3.1.3    设计上下文无关文法

       3.1.4     歧义性

       3.1.5     乔姆斯基范式

      3.2    下推自动机

       3.2.1    下推自动机的形式定义

       3.2.2    下推自动机举例

       3.2.3     与上下文无关文法的等价性

      3.3     非上下文无关语言

      练习

      问题

    第二部分   可计算性理论

     第4章    丘奇—图灵论题

      4.1   图灵机

       4.1.1    图灵机的形式定义

       4.1.2    图灵机的例子

      4.2    图灵机的变形

       4.2.1    多带图灵机

       4.2.2     非确定型图灵机

       4.2.3     枚举器

       4.2.4    与其他模型的等价性

      4.3     算法的定义

       4.3.1    希尔伯特问题

       4.3.2    描述图灵机的术语

      练习

      问题

     第5章   可判定性

      5.1    可判定语言

       5.1.1     与正则语言相关的可判定性问题

       5.1.2    与上下文无关语言相关的可判定问题

      5.2    停机问题

       5.2.1    对角化方法

       5.2.2    停机问题是不可判定的

       5.2.3    一个图灵不可识别语言

      练习

      问题

     第6章    可归约性

      6.1    语言理论中的不可判定问题

      6.2     一个简单的不可判定问题

      6.3     映射可归约性

       6.3.1   可计算函数

       6.3.2    映射可归约性的形式定义

      练习

       问题

     第7 章    可计算性理论的高级专题

      7.1    递归定理 

       7.1.1    自引用

       7.1.2    应用递归定理的术语

       7.1.3   应用

      7.2    逻辑理论的可判定性

       7.2.1    一个可判定的理论

       7.2.2    一个不可判定的理论

      7.3     图灵可归约性

      7.4     信息的定义

       7.4.1    极小长度的描述

       7.4.2    定义的优化 

       7.4.3    不可压缩的串和随机性

      练习

      问题

    第三部分   复杂性理论 

     第8章   时间复杂性

      8.1    度量复杂性

       8.1.1    大O和小o记法

       8.1.2    分析算法

       8.1.3     模型间的复杂性关系

      8.2   P 类

       8.2.1   多项式时间

       8.2.2   P 中的问题举例

      8.3    NP类 

       8.3.1   NP中的问题举例

       8.3.2   P与NP问题

      8.4    NP完全性

       8.4.1     多项式时间可归约性

       8.4.2     NP完全性的定义

       8.4.3    库克—列文定理

      8.5    几个NP完全问题

       8.5.1    顶点覆盖问题

       8.5.2    哈密顿路径问题

       8.5.3    子集和问题

      练习

      问题

     第9章    空间复杂性

      9.1    萨维奇定理

      9.2    PSPACE类

      9.3   PSPACE完全性

       9.3.1     问题TQBF

       9.3.2    博奕的必胜策略

       9.3.3     广义地理学

      9.4     L类和NL学

      9.5    NL 完全性

      9.6    NL等于coNL

      练习

      问题

     第10章    难解性

      10.1   层次定理

      10.2    相对化

      10.3    电路复杂性 

      练习

      问题

     第 11章    复杂性理论中的高级专题

      11.1    近似算法

      11.2    概率算法

       11.2.1    BPP类

       11.2.2    素数性

       11.2.3    只读一次的分支程序

      11.3    交错式

       11.3.1    交错式时间与交错式空间

       11.3.2    多项式时间层次

      11.4     交互式证明系统

       11.4.1    图的非同构

       11.4.2    模型的定义

       11.4.3    IP=PSPACE

      11.5   并行计算

       11.5.1    一致布尔电路

       11.5.2    NC类

       11.5.3    P完全性

      11.6     密码学

       11.6.1     密钥

       11.6.2    公钥密码系统

       11.6.3    单向函数

       11.6.4     天窗函数 

      练习

      问题

      参考文献

      索引
查看详情
好书推荐 / 更多
计算理论导引
荷马史诗中的生与死
[英]加斯帕·格里芬、Jasper、Griffin 著
计算理论导引
票证里的中国
李三台 著
计算理论导引
圣天秤星
彼得·汉密尔顿(Peter F.Hamilton)、段宗忱 译
计算理论导引
追寻记忆的痕迹:新心智科学的开创历程(诺贝尔奖得主埃里克·坎德尔作品)
[美]埃里克·坎德尔 著;喻柏雅 译
计算理论导引
创世:梵蒂冈博物馆全品珍藏(修订升级版)
[德]安雅·格雷贝 著;郑柯 译
计算理论导引
白鹭
德里克·沃尔科特(Derck Walcott) 著;程一身 译
计算理论导引
东京城市更新经验:城市再开发重大案例研究
同济大学建筑与城市空间研究所、株式会社日本设计 著
计算理论导引
黎曼猜想漫谈
卢昌海 著
计算理论导引
鸟的魔力:一部绚烂的鸟类文化史
[英]西莉亚·费希尔 著;王晨 译
计算理论导引
隐身大师
[法]萨拉·卡明斯基 著;廖晓玮 译
计算理论导引
莫奈手稿
[法]克劳德·莫奈
计算理论导引
无止境的逃离
[土耳其]哈坎·甘迪