孔夫子旧书网-网上买书卖书、古旧书收藏品交易平台 孔夫子旧书网-网上买书卖书、古旧书收藏品交易平台 占位居中 孔夫子旧书网-网上买书卖书、古旧书收藏品交易平台
商品
拍卖区
在售
已售
搜索历史
搜索
高级搜索

计算理论导引：第1版

计算理论导引：第1版
分享
扫描下方二维码分享到微信
打开微信，点击右上角”+“，
使用”扫一扫“即可将网页分享到朋友圈。
作者: [美]
出版社: 机械工业出版社
2000-02
版次: 1
ISBN: 9787111075745
定价: 30.00
装帧: 平装
开本: 其他
纸张: 胶版纸
页数: 273页
原版书名: Introduction to the Theory of Computation
分类: 教材教辅考试>教材>大学教材>工程技术
58人买过
  • 本书系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性和计算复杂性。绝大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容作了重点介绍。作者以清闲的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。 张立昂，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     天窗函数 

      练习

      问题

      参考文献

      索引
查看详情
其他版本 / 全部 (5)
相关图书 / 更多
计算理论导引：第1版
计算机基础与实训教程
顾玲芳 编
￥23.10 起
计算理论导引：第1版
计算机网络攻击与防护
刘念；陈雪松；谈洪磊
￥33.08 起
计算理论导引：第1版
计算机组成原理与汇编语言
田民格、秦彩杰、林观俊、田佳琪
￥54.06 起
计算理论导引：第1版
计算机网络技术（第5版）
徐立新 吕书波
￥35.16 起
计算理论导引：第1版
计算天文
冯毅
￥40.00 起
计算理论导引：第1版
计算思维培养与无人机创意编程
范谊 陈宇 张锦东
￥35.35 起
计算理论导引：第1版
计算机组成原理与系统结构（第3版）
冯建文 章复嘉 赵建勇 包健 编著
￥56.20 起
计算理论导引：第1版
计算小状元 小学数学 2年级上册 bs版 小学数学单元测试 新华
作者
￥6.09 起
计算理论导引：第1版
计算机应用基础
苗苗
￥18.60 起
计算理论导引：第1版
计算机系统原理（2023年版） 全国高等教育自学考试指导委员会
全国高等教育自学考试指导委员会
￥32.45 起
计算理论导引：第1版
计算机辅助翻译教程（）
赵秋荣
￥29.39 起
计算理论导引：第1版
计算机三维建模方法
易健宏 编著；李凤仙
￥21.30 起
您可能感兴趣 / 更多
计算理论导引：第1版
孩子，把你的手给我1：怎么说孩子才爱听，怎么教孩子才肯学？帮助每一位3-12岁孩子的父母结束与孩子的所有冲突！
[美]海姆·G.吉诺特
￥10.26 起
计算理论导引：第1版
怎样做成大事
[美]丹·加德纳（Dan Gardner） 著；贾拥民 译；湛庐文化 出品；[丹麦]傅以斌（Bent Flyvbjerg）
￥43.28 起
计算理论导引：第1版
1200年希腊罗马神话
[美]伊迪丝·汉密尔顿
￥78.96 起
计算理论导引：第1版
爱情心理学（新编本）
[美]罗伯特·J. 斯腾伯格 (美)凯琳·斯腾伯格 倪爱萍 译
￥39.30 起
计算理论导引：第1版
黄金圈法则
[美]西蒙·斯涅克 著；磨铁文化 出品
￥49.00 起
计算理论导引：第1版
汤姆·索亚历险记 彩图注音版 一二三四年级5-6-7-8-9岁小学生课外阅读经典 儿童文学无障碍有声伴读世界名著童话故事
[美]马克 吐温
￥5.51 起
计算理论导引：第1版
富兰克林自传 名家全译本 改变无数人命运的励志传奇 埃隆马斯克反复推荐 赠富兰克林签名照及精美插图
[美]本杰明·富兰克林 著；李自修 译
￥29.05 起
计算理论导引：第1版
意大利文艺复兴新艺术史
[美]迈克尔·韦恩·科尔 著；[美]斯蒂芬·J·坎贝尔；邵亦杨
￥345.17 起
计算理论导引：第1版
汤姆素亚历险记：中小学生课外阅读快乐读书吧 儿童文学无障碍有声伴读世界名著童话故事
[美]马克·吐温
￥7.77 起
计算理论导引：第1版
老人与海 彩图注音版 一二三四年级5-6-7-8-9岁小学生课外阅读经典 儿童文学无障碍有声伴读世界名著童话故事
[美]海明威
￥5.51 起
计算理论导引：第1版
养育的觉醒：全面激发孩子自驱力，教你如何心平气和做妈妈
[美]凯文·莱曼 著；唐晓璐 译；斯坦威 出品
￥17.40 起
计算理论导引：第1版
国际大奖图画书系列 共11册（小老鼠的恐惧的大书，大灰狼，红豆与菲比，别烦我，下雪了 ，穿靴子的猫 ，先有蛋，绿 ，特别快递，如果你想看鲸鱼 ，一个部落的孩子 ） 麦克米伦世纪
[美]莱恩·史密斯 (英)埃米莉·格雷维特 (美)劳拉·瓦卡罗·等/文 (英)埃米莉·格雷维特 等/图 彭懿 杨玲玲 阿甲 孙慧阳 白薇 译
￥5.00 起
© 2002-2024 Kongfz.com 孔夫子旧书网 版权所有
关于孔网 联系我们 帮助中心 版权隐私 广告业务 工作机会 移动版 图书目录 图书标签 热搜书籍 作家大全