计算理论导引

出版时间：2006-7  出版社：机械工业出版社  作者：[美]Michael Sipser  页数：269  
Tag标签：无  

内容概要

本书是计算理论领域的经典著作，被国外多所大学选用用为教材。本书以注重思路、深入引导为特色，系统地介绍计算机理论的三大主要内容：自动机与语言、可计算性理论和计算复杂性理论。同时，对可计算性和计算复杂理论中的某些高级内容作了重点讲解。全书通过启发性的问题、精彩的结果和待解决问题来引导读者挑战此领域中的高层次问题。新版的一大亮点是增加了更多习题、教辅资料和部分习题解答，更加有利于教学。    全书叙述由浅入深、详略得当，重点突出，不拘泥于技术细节。可作为计算机专业高年级本科生和研究生的教材，也可作为相关专业教师和研究人员的参考书。

作者简介

Michael Sipser：麻省理工学院应用数学系教授，计算机科学和人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作25年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。

书籍目录

出版者的话专家指导委员会译者序译者简介第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 图灵可归约性    ……第三部分  复杂性理论  第7章 时间复杂性  第8章 空间复杂性  第9章 难解性  第10章 复杂性理论高级专题参考文献索引

媒体关注与评论

　　元昌安（教授，硕士生导师）　　（广西师范学院信息技术系，南宁，530001）　　我在攻读博士学位期间曾经认真攻读学习《计算理论导引》，如今我又引导我的学生学习这门功课，作为双重身份的“过来人”, 我有独特的体会。作者Michael Sipser以其独特的视角，综合地描述了计算机科学理论，并以清新的笔触、生动的语言给出了宽泛的数学原理，对一些低层次的技术细节，或通俗解释描述，或高屋建瓴、给出思想而不陷入细节，或让读者自己思考取舍。阅读完教材并修完这门课程时，感触颇深：　　1．唤醒了久违的数学解题思路，学习能力进一步提高。我们这一代人（20世纪60年代出生），曾几何时，捧着代数、几何题，展开想象的翅膀、推导着一道又一道难题。但是，多年来从事计算机科学研究的经历，已经让我们当年活跃的解题思维出现迟钝。正是这本教材的证明和练习，唤醒了久违的活跃的逻辑推导思维，激发起当年高考解题的斗志，又一次让我尝到了遇到难题愁眉不展和解决了一个难题后欢呼雀跃的滋味。一门课修完，自感不惑之年，又一次提高了学习能力。　　2．同类教材中，难度广度均显现出来。教材从自动机语言到可计算机性理论和复杂性理论，计算机软硬件理论均给出了较有深度且严谨的描述，其中定理理解及其证明的难度绝不亚于任何一门代数学的课程。行内人都知道，从事计算机科学研究的人，往往被数学界所看贬，其重要原因是，计算机科学研究的内容所涉及的数学内容往往较之数学界的前沿研究浅显。但这本教材所描述的计算机理论却向人们显示出计算机科学研究的难度和深度，也即计算机科学技术的研究并不单纯只是炒其他学科的剩饭！这让广大从事计算机科学理论研究的人在基础研究领域也能挺直腰杆！　　3． 作为一门理论修养课，自感受益匪浅！在计算机学习的各个阶段，我们都接触了一些计算机理论知识。学完这本书，却感觉在计算机理论的理解上产生了一个质的飞跃，对许多问题知其然且知其所以然。由于作者对理论证明的独特设计，再加上导师课堂上对作者意图的深刻理解和坚决贯彻，使得在学习过程中，能把许多复杂问题简单化，从而达到真正理解的目的。计算机理论修养的提高，直接影响着博士论文和研究论文的质量。我周围的同学都受到《计算机理论》的影响，论文中不断迸发出计算机理论指导的火花，亮点不断闪现。　　　　我的体会或许有一点个人的情感杂于其中，但《计算理论导引》已然是一本经典著作而为举世所公认。如果你想让自己的计算机理论素养升华，建议阅读一下这本教材！

编辑推荐

　　《计算理论导引》（第2版）叙述由浅入深、详略得当，重点突出，不拘泥于技术细节。可作为计算机专业高年级本科生和研究生的教材，也可作为相关专业教师和研究人员的参考书。

用户评论 (总计41条)

•   这个商品不错~ 计算理论导引（第2版）——计算机科学丛书
•   对这本书还能说些什么呢，绝对的入门好书，名不虚传。我上课用的是《自动机理论、语言和计算导论（原书第2版）》，后来快考试时再看第二遍觉得这书也相当好，但一开始我还是先用sipser的这本书入的门。这本书的好处就是而且一旦入了门，再深入学习就会相当容易。你如果想深入了解计算理论的话，这本书读完了就去读那本《自动机理论、语言和计算导论》吧但如果你觉得那本书入门太难，或者先想高屋建瓴理解计算理论的精髓，就来读sipser这本书吧，强烈推荐。
•   这本书其实应该算是数学书了，但相当于计算机的理论基础，是每个学计算机的人都应该了解的，从理论上界定了什么是计算。。各类计算模型能识别的语言（有限状态，下推，线性有间，图灵）计算能达到的极限（可判定与可规约）以及计算的复杂度（时间复杂度与空间复杂度）不了解计算的人，就算不上了解计算机。。当然了，如果你只是想实用，就不必要读了，这更像是一本计算哲学。。。
•   经典图书，需要恶补计算理论的童鞋们推荐看看。能建立你的系统思维能力，跳跃出算法改进的局限。
•   计算理论学不会的都应该看这本书，思想清晰而直观
•   我们可计算理论的课的教材
•   计算理论是深奥的理论，比较难懂，这本书还不错，清楚。
•   很不错的一本计算理论的入门书
•   如果你看完着本书，你会对计算机有更深入的理解
•   程序编程到一定程度后，需要读这样的书在思路和理论程度上做一点提高
•   对于理论学习非常好
•   教材，书的质量不错，没开始读
•   老师推荐的书，外文书应该比较经典，比较深，读懂当然最好了
•   经典之作～
•   书的内容有点儿冗余，前几章完全跟现在没关系
•   书的质量很不错
  内容看起来挺艰深的，得好好研读才行了
•   学算法必看的书，不过现在还没能全部看懂
•   听介绍说很好 先买来 需要的时候研读下
•   不错，书中有少许很低级错误 望再版时更正。
•   很好的一本书，建议购买，呵呵
•   觉得还不错. 浅显易懂.
•   质量不错，上课用的
•   不错，就是纸质稍微差了点。
•   读了一点有收获
•   浅显易懂的书 很好
•   质量不错，不够有点压折了。
•   不仅书的价钱比别家便宜，而且发货的速度很快，马上就收到了，非常好，省时省事...
•   计算理论导引
•   还没仔细看，翻译质量不了解，看了目录，主要讲理论，推导过程不少，需要有离散的基础。学过这个就能读了。
•   我自学的，很容易懂，深入浅出，把复杂理论讲的很生动
•   这本书是我们的教材，很不错的说
•   经典书籍，讲得不错，值得学习与收藏。
•   对于想学好算法，写好代码的同学，这本书一定要来看。
•   书是不错，为什么纸张很薄呢？
•   刚收到书就降价了。。。。
•   书还可以，就是自学起来比较吃力，只要功夫深，还是能啃动的，书质量不错
•   我是在上课用的，这书很经典不错，只不过有些部分较难。
•   老公买的~没见这小子拜读呢！
•   教师拿他当教科书还行，除此外也没有多大用处了。
•   你们送货的速度有点慢，我星期一下的订单，星期天才收到，希望你们以后送货速度能快些。
•   不错，就是送货慢了些啊