![计算理论导引 - [美]Michael Sipser](https://static.book345.com/covers/s/9787111190288.jpg)
书籍介绍
本书是计算理论领域的经典著作，被国外多所大学选用为教材。本书以注重思路、深入引导为特色，系统地介绍计算理论的三大主要内容：自动机与语言、可计算性理论和计算复杂性理论。同时，对可计算性和计算复杂性理论中的某些高级内容作了重点讲解。全书通过启发性的问题、精彩的结果和待解决问题来引导读者挑战此领域中的高层次问题。新版的一大亮点是增加了更多习题、教辅资料和部分习题解答，更加有利于教学。
全书叙述由浅入深、详略得当，重点突出，不拘泥于技术细节。可作为计算机专业高年级本科生和研究生的教材，也可作为相关专业教师和研究人员的参考书。
精彩摘录
- "Ignoring the trees to see the forest doesn't mean that one is more important than the other--it just gives a different perspective."
- "We have come to a turning point in the study of the theory of computation. We continue to speak of Turing machines, but our real focus from now on is on algorithms. That is, the Turing machine merely serves as a precise model for the definition of algorithm. We skip over the extensive theory of Turi"
目录
用户评论
本科时候学的最痛苦的一门课没有之一。之前看过王垠对于计算理论用图灵机引入可计算性的吐槽文章深以为然……究竟为什么会有图灵机作规约的题目？？？图灵机真的适合作为引入可计算性的引子吗？？？横向比较了下，德语区（不知道欧陆其他国家如何，但德语区应该区别不大）的理论性普遍应该是最强的，Sipser的这本书也只能作为参考。计算机科班学生学过计算理论后，我觉得会对搞数学的那帮会有更深的敬畏吧……考试题每次最后一道证明NPC的问题总是做不出来，之前还有一道表面是描述图灵机实际是考察对角线证明的题目，很巧妙。期末考试24页，8道题目，3个半小时，60分满分24分及格，百分之40左右的通过率，纠结自己能不能通过考试，辗转不能眠，这是我人生目前为止经历过的最难忘也是最绝望的记忆之一……
理论计算机科学的入门好书
本书可以看做编译器原理的数学逻辑原理书。自动机 可计算性 复杂度。密码使问题变复杂，其他任务都是化简。自动机：有穷自动机（状态）和正则表达式在描述能力上等价（有限存储）；上下文化无关（下推自动机无限存储而且是栈机制）；有穷状态机类似于图灵机（无限存储任意访问数据）学习过数学基础（元数学）和离散数学这本书就基本上理解了。编译原理按照乔姆斯基文法结构的分类：词法：有穷自动机（ finite automata）和正则表达式（regular expression）乔姆斯基3型；程序设计乔姆斯基的2型— 与乔姆斯基分类结构（ Chomsky hierarchy）一样— 包括了文法的4个层次：0型、1型、2型和3型文法，且其中的每一个都是其前者的专门化计算理论对应着乔姆斯基的4个文法模型，0型文法的是图
清晰..
写的非常好，非常好。能让人学明白的书。
CS411书目
可判定，可识别，可计算，复杂性。真的很精彩。对于自动机的了解有了新的认识。对于还有不可计算的问题感到非常神奇。深深感到理论的魅力(就是我学习能力一般走不了学术路线了)
补标
看过前两张，状态机部分看的认真点，到上下文无关文法止，比较费脑
收藏