| 失效链接处理 |
|
计算理论导引 原书第3版 PDF 下载
本站整理下载：
版权归出版社和原作者所有，链接已删除，请购买正版
用户下载说明：
电子版仅供预览，下载后24小时内务必删除，支持正版，喜欢的请购买正版书籍：
http://product.dangdang.com/600223244.html
相关截图：
 资料简介： 本书由计算理论领域的知名权威MichaelSipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书 资料目录： 出版者的话 译者序 第3版前言 第2版前言 第1版前言 第0章绪论 01自动机、可计算性与复杂性 011计算复杂性理论 012可计算性理论 013自动机理论 02数学概念和术语 021集合 022序列和多元组 023函数和关系 024图 025字符串和语言 026布尔逻辑 027数学名词汇总 03定义、定理和证明 04证明的类型 041构造性证明 042反证法 043归纳法 练习 问题 习题选解 第一部分自动机与语言 第1章正则语言 11有穷自动机 111有穷自动机的形式化定义 112有穷自动机举例 113计算的形式化定义 114设计有穷自动机 115正则运算 12非确定性 121非确定型有穷自动机的形式化定义 122NFA与DFA的等价性 123在正则运算下的封闭性 13正则表达式 131正则表达式的形式化定义 132与有穷自动机的等价性 14非正则语言 练习 问题 习题选解 第2章上下文无关文法 21上下文无关文法概述 211上下文无关文法的形式化定义 212上下文无关文法举例 213设计上下文无关文法 214歧义性 215乔姆斯基范式 22下推自动机 221下推自动机的形式化定义 222下推自动机举例 223与上下文无关文法的等价性 23非上下文无关语言 24确定型上下文无关语言 241DCFL的性质 242确定型上下文无关文法 243DPDA和DCFG的关系 244语法分析和LR(k)文法 练习 问题 习题选解 第二部分可计算性理论 第3章丘奇图灵论题 31图灵机 311图灵机的形式化定义 312图灵机的例子 32图灵机的变形 321多带图灵机 322非确定型图灵机 323枚举器 324与其他模型的等价性 33算法的定义 331希尔伯特问题 332描述图灵机的术语 练习 问题 习题选解 第4章可判定性 41可判定语言 411与正则语言相关的可判定性问题 412与上下文无关语言相关的可判定性问题 42不可判定性 421对角化方法 422不可判定语言 423一个图灵不可识别语言 练习 问题 习题选解 第5章可归约性 51语言理论中的不可判定问题 52一个简单的不可判定问题 53映射可归约性 531可计算函数 532映射可归约性的形式化定义 练习 问题 习题选解 第6章可计算性理论的高级专题 61递归定理 611自引用 612递归定理的术语 613应用 62逻辑理论的可判定性 621一个可判定的理论 622一个不可判定的理论 63图灵可归约性 64信息的定义 641极小长度的描述 642定义的优化 643不可压缩的串和随机性 练习 问题 习题选解 第三部分复杂性理论 第7章时间复杂性 71度量复杂性 711大O和小o记法 712分析算法 713模型间的复杂性关系 72P类 721多项式时间 722P中的问题举例 73NP类 731NP中的问题举例 732P与NP问题 74NP完全性 741多项式时间可归约性 742NP完全性的定义 743库克列文定理 75几个NP完全问题 751顶点覆盖问题 752哈密顿路径问题 753子集和问题 练习 问题 习题选解 第8章空间复杂性 81萨维奇定理 82PSPACE类 83PSPACE完全性 831TQBF问题 832博弈的必胜策略 833广义地理学 84L类和NL类 85NL完全性 86NL等于coNL 练习 问题 习题选解 第9章难解性 91层次定理 92相对化 93电路复杂性 练习 问题 习题选解 第10章复杂性理论高级专题 101近似算法 102概率算法 1021BPP类 1022素数性 1023只读一次的分支程序 103交错式 1031交错式时间与交错式空间 1032多项式时间层次 104交互式证明系统 1041图的非同构 1042模型的定义 1043IP=PSPACE 105并行计算 1051一致布尔电路 1052NC类 1053P完全性 106密码学 1061密钥 1062公钥密码系统 1063单向函数 1064天窗函数 练习 问题 习题选解 参考文献 索引 |
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
