具体描述
本书是计算理论领域的经典著作，被国外多所大学选用为教材。本书以注重思路、深入引导为特色，系统地介绍计算理论的三大主要内容：自动机与语言、可计算性理论和计算复杂性理论。同时，对可计算性和计算复杂性理论中的某些高级内容作了重点讲解。全书通过启发性的问题、精彩的结果和待解决问题来引导读者挑战此领域中的高层次问题。新版的一大亮点是增加了更多习题、教辅资料和部分习题解答，更加有利于教学。
全书叙述由浅入深、详略得当，重点突出，不拘泥于技术细节。可作为计算机专业高年级本科生和研究生的教材，也可作为相关专业教师和研究人员的参考书。
作者简介
目录信息
专家指导委员会
译者序
译者简介
第1版前言
第2版前言
第0章 绪论
0.1 自动机、可计算性与复杂性
0.2 数学概念和术语
0.3 定义、定理和证明
0.4 证明的类型
练习
问题
习题选解
第一部分 自动机与语言
第1章 正则语言
1.1 有穷自动机
1.2 非确定性
1.3 正则表达式
1.4 非正则语言
练习
问题
习题选解
第2章 上下文无关文法
2.1 上下文无关文法概述
2.2 下推自动机
2.3 非上下文无关语言
练习
问题
习题选解
第二部分 可计算性理论
第3章 丘奇-图灵论题
3.1 图灵机
3.2 图灵机的变形
3.3 算法的定义
练习
问题
习题选解
第4章 可判定性
4.1 可判定性
4.2 停机问题
练习
问题
习题选解
第5章 可归约性
5.1 语言理论中的不可判定问题
5.2 一个简单的不可判定问题
5.3 映射可归约性
练习
问题
习题选解
第6章 可计算性理论的高级专题
6.1 递归定理
6.2 逻辑理论的可判定性
6.3 图灵可归约性
……
· · · · · · (收起)
读后感
本书的作者是著名的计算理论方面专家，麻省理工学院应用数学系主任 M. Sipser。全书分为11章，并附有部分习题解答。全书思路清晰，由浅入深，内容详细，是一本零起点学习计算理论的理想教材。我是出于研究需要阅读此书的。其中第零章简要介绍了所需要的基本数学知识。第一到三...
评分本书的作者是著名的计算理论方面专家，麻省理工学院应用数学系主任 M. Sipser。全书分为11章，并附有部分习题解答。全书思路清晰，由浅入深，内容详细，是一本零起点学习计算理论的理想教材。我是出于研究需要阅读此书的。其中第零章简要介绍了所需要的基本数学知识。第一到三...
评分如果你周围的人在说P， NP之类，而你还不知道这些概念，请捧起这本书！ 之后，如果你还想去解决它们，寻求解决思路可以参考这本Metaheuristics For Hard Optimization
评分事知其然而后知其所以然。 现代计算机体系的构建，图灵机的数学模型的实现，正是指出了这道创世纪的光。 现在书里面的内容已经忘记的差不多了，只是记得不断的证明，一步步的证明，充满了智慧的光芒。 总之，是一本好的数学书。
评分在所有我看过的计算理论、可计算性、计算复杂度的教材中，Sipser的这本Introduction to the Theory of Computation是最适合入门的。把计算理论这么个艰深的学问讲解得清晰简洁，直观易懂。而且涵盖了计算理论的各个经典内容。作为一本introduction，真是再好不过了。 计算理论...
用户评价
百感交集
评分本书可以看做编译器原理的数学逻辑原理书。自动机 可计算性 复杂度。密码使问题变复杂，其他任务都是化简。自动机：有穷自动机（状态）和正则表达式在描述能力上等价（有限存储）；上下文化无关（下推自动机无限存储而且是栈机制）；有穷状态机类似于图灵机（无限存储任意访问数据）学习过数学基础（元数学）和离散数学这本书就基本上理解了。编译原理按照乔姆斯基文法结构的分类：词法：有穷自动机（ finite automata）和正则表达式（regular expression）乔姆斯基3型；程序设计乔姆斯基的2型— 与乔姆斯基分类结构（ Chomsky hierarchy）一样— 包括了文法的4个层次：0型、1型、2型和3型文法，且其中的每一个都是其前者的专门化计算理论对应着乔姆斯基的4个文法模型，0型文法的是图
评分终于看完了……
评分Pretty clear with lots of examples.
评分再看一遍。。才有收获
相关图书
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 book.quotespace.org All Rights Reserved. 小美书屋 版权所有