计算理论基础

出版时间：2006-7  出版社：清华大学  作者：Harry R. Lewis,Christos H. Papadimitriou  页数：244  
Tag标签：无  

前言

　　自《计算理论基础》问世以来，在这15年中许多东西变了，也有许多东西没有变。计算机科学现在是一门成熟得多的公认的学科，在这个计算无处不在、信息全球化和复杂性迅速增长的世界上扮演越来越重要的角色，因此有更多的理由关心它的基础。《计算理论基础》的作者们自己现在更加成熟和忙碌——这是何以这么久才出第二版的原因。我们写第二版，是因为我们感觉到有几处可以说得更好些，有几处可以简单些，还有一些可以删掉。更重要的是，我们希望本书反映计算理论和学它的学生在这些年的进步。虽然就绝对而言现在教计算理论的比过去多了，但是它在计算机科学教学计划中的相对地位，例如与算法课程相比，没有得到加强..

内容概要

　　计算理论是计算机科学的理论基础。《计算理论基础》(第2版)介绍了计算理论最核心、最基本的内容，包括形式语言与自动机、可计算性和计算复杂性三大部分。全书共分七章，分别为：集合、关系和语言；有穷自动机；上下文无关语言； Turing机；不可判定性；计算复杂性；NP完全性。《计算理论基础》(第2版)突出了算法，从而使计算机专业的学生更易接受，也更有收益。

书籍目录

第1章 集合. 关系和语言1. 1 集合1. 2 关系与函数1. 3 特殊类型的二元关系1. 4 有穷集合与无穷集合1. 5 三个基本的证明技术1. 6 闭包与算法1. 7 字母表与语言1. 8 语言的有穷表示参考文献第2章 有穷自动机2. 1 确定型有穷自动机2. 2 非确定型有穷自动机2. 3 有穷自动机与正则表达式2. 4 正则语言与非正则语言2. 5 状态最小化2. 6 关于有穷自动机的算法参考文献第3章 上下文无关语言3. 1 上下文无关文法3. 2 语法分析树3. 3 下推自动机3. 4 下推自动机与上下文无关文法3. 5 上下文无关语言与非上下文无关语言3. 6 关于上下文无关文法的算法3. 7 确定性与语法分析参考文献第4章 Turing机4. 1 Turing机的定义4. 2 用Turing机计算4. 3 Turing机的扩充4. 4 随机存取Turing机4. 5 非确定型Turing机4. 6 文法4. 7 数值函数参考文献第5章 不可判定性5. 1 Church-Turing论题5. 2 通用Turing机5. 3 停机问题5. 4 与Turing机有关的不可判定问题5. 5 与文法有关的不可解问题5. 6 不可解的铺砖问题5. 7 递归语言的性质参考文献第6章 计算复杂性6. 1 P类6. 2 若干问题6. 3 布尔可满足性6. 4 NP类参考文献第7章 NP完全性7. 1 多项式时间归约7. 2 Cook定理7. 3 其他的NP完全问题7. 4 对付NP完全性参考文献中英对照名词索引

编辑推荐

　　《计算理论基础》(第2版)适合作为计算机专业及数学专业本科生或研究生的教材，也可供从事计算机科学的教学与研究人员参考。

用户评论 (总计2条)

•   　　 如果是计算机专业的，我觉得越早看越好。
  　　 这本书描述的是非常奇妙的事情，把一个简单的有穷机，下推自动机，图灵机和正则表达式，上下无关文法，无限制文法统一在一起，将一些以前看是若隐若现，似是而非的东西，用理论的科学的方法研究，居然还可以推导。在不停地推导，构造中，又能解决实际中的一些看似无法表达的东西。在这个锻炼的过程中，慢慢知道了计算机的能力，能做什么，不能做什么，怎样做是比较可行的。这是发现和认识世界的一个过程，也是在现实中的一个妥协。图灵机真伟大。
  　　 不过看本书会比较累，都是离散的东西，不停定义构造证明应用，特别是证明的过程，有时候觉得和以前学的证明相差太大，差不多都是构造的方法，好像都不是证明。
  　　 唯一遗憾，就是这本书的习题答案好像没有，网上没有找到。
  　　 书中的NP问题可以结合图论的相关章节和《算法导论》的最后2章一起看，NP在神经网络，人工智能里面都反复提到，也可以结合一起看。
•   　　中文翻译版，翻译的还行
  　　
  　　书籍说明
  　　
  　　计算理论课程使用的书籍
  　　
  　　作者同样是大牛，书写的不错，应该算是经典教材
  　　
  　　学习计算理论的话，可以作为入门参考
  　　
  　　阅读建议
  　　
  　　计算理论入门学习书籍
  　　
  　　开始学习计算理论的时候可以考虑学习