基本信息
- 作者： [美]约翰·E.霍普克罗夫特(John E. Hopcroft）拉杰夫·莫特瓦尼（Rajeev Motwani）杰弗里·D.乌尔曼（Jeffrey D. Ullman)
- 译者： 孙家骕等
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111704294
- 上架时间：2022-4-29
- 出版日期：2022 年4月
- 开本：16开
- 页码：377
- 版次：1-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 计算理论 > 自动机
编辑推荐
三位理论计算大师的巅峰之作，计算机理论课程经典英亚注册
内容简介
作译者
[美]约翰·E.霍普克罗夫特(John E. Hopcroft）拉杰夫·莫特瓦尼（Rajeev Motwani）杰弗里·D.乌尔曼（Jeffrey D. Ullman) 著：约翰·E.霍普克罗夫特（John E. Hopcroft） 1986年图灵奖获得者、美国国家工程院院士、美国国家科学院院士、美国国家艺术与科学院院士、中国科学院外籍院士、美国康奈尔大学教授。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。他和Jeffrey D. Ullman一起获得2010年IEEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
拉杰夫·莫特瓦尼（Rajeev Motwani） 斯坦福大学计算机科学系教授。他的研究兴趣包括数据库、数据挖掘、Web搜索和信息检索、机器人等。他于2009年6月意外身亡，享年47岁。
杰弗里·D.乌尔曼（Jeffrey D. Ullman） 2020年图灵奖获得者、美国国家工程院院士、斯坦福大学计算机科学系名誉教授。他的研究兴趣包括数据库理论、数据库集成、数据挖掘、理论计算等。他和John E. Hopcroft一起获得2010年IEEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
拉杰夫·莫特瓦尼（Rajeev Motwani） 斯坦福大学计算机科学系教授。他的研究兴趣包括数据库、数据挖掘、Web搜索和信息检索、机器人等。他于2009年6月意外身亡，享年47岁。
杰弗里·D.乌尔曼（Jeffrey D. Ullman） 2020年图灵奖获得者、美国国家工程院院士、斯坦福大学计算机科学系名誉教授。他的研究兴趣包括数据库理论、数据库集成、数据挖掘、理论计算等。他和John E. Hopcroft一起获得2010年IEEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
目录
译者序
前言
第1章 自动机：方法与体验 1
1.1 为什么研究自动机理论 1
1.1.1 有穷自动机简介 1
1.1.2 结构表示法 3
1.1.3 自动机与复杂性 3
1.2 形式化证明简介 3
1.2.1 演绎证明 4
1.2.2 求助于定义 6
1.2.3 其他定理形式 7
1.2.4 表面上不是“如果-则”命题的
定理 9
1.3 其他的证明形式 9
1.3.1 证明集合等价性 9
1.3.2 逆否命题 10
1.3.3 反证法 12
1.3.4 反例 12
1.4 归纳证明 13
1.4.1 整数上的归纳法 13
前言
第1章 自动机：方法与体验 1
1.1 为什么研究自动机理论 1
1.1.1 有穷自动机简介 1
1.1.2 结构表示法 3
1.1.3 自动机与复杂性 3
1.2 形式化证明简介 3
1.2.1 演绎证明 4
1.2.2 求助于定义 6
1.2.3 其他定理形式 7
1.2.4 表面上不是“如果-则”命题的
定理 9
1.3 其他的证明形式 9
1.3.1 证明集合等价性 9
1.3.2 逆否命题 10
1.3.3 反证法 12
1.3.4 反例 12
1.4 归纳证明 13
1.4.1 整数上的归纳法 13
前言
在1979年出版的本书第1版的前言中，Hopcroft和Ullman对于下面的事实感到惊诧不已：与1969年他们写第一本书时的情形相比，自动机这一专题已经有了突破性进展。的确，1979年版的书中包含许多在以前的著作中找不到的主题，篇幅增加了大约一倍。如果读者有兴趣把本书与1979年版的那本书做比较，就会发现，正如20世纪70年代的汽车那样，本书是“外看大，内看小”。从表面看起来像是退步，但是我们有理由对此变化感到高兴。
第一，在1979年，自动机和语言理论还是一个比较活跃的研究领域。那本书的主要目的是鼓励擅长数学的学生为这个领域做出新的贡献。然而今天，直接针对自动机理论的研究几乎已经销声匿迹（相反，更多的是对其应用的研究），因此也就没有理由继续保持1979年那本书的简洁和高度数学化的风格。
第二，近年来，自动机和语言理论的角色已经发生了很大的变化。在1979年，自动机还主要是研究生水平的专题，那时我们假定的读者是高年级研究生，特别是使用这本书后几章的那些读者。然而到了今天，它已经成为本科生课程的主要内容。正是基于这个原因，本书在编排时必须假定读者只有很少的预备知识，因此必须比前一版本的书提供更多的背景知识介绍和论证的细节。
第三，计算机科学在过去的几十年里已经发展到了几乎无法想象的程度。在1979年，我们可能会觉得经受得起下一轮技术考验的材料太少了，以至于排满课程计划都很难，然而今天，却有非常多的子科目在竞争本科生课程的有限空间。
第四，计算机科学如今已经发展成为更加职业化的科目，在许多学习它的学生中存在着严重的实用主义倾向。但我们仍然相信，自动机理论的方方面面是各种新兴学科的重要工具，并且也相信，无论学生多么倾向于只去学习那些最能直接赚钱的技术，但在典型的自动机课程中，那些理论的和有利于拓宽思维的习题依然可以保持其价值。然而，为了保证这个科目在计算机科学专业学生的课程表中继续占有一席之地，我们认为有必要在强调数学理论的同时强调应用。因此，我们把上一版中许多比较深奥的主题换成了本版中如何使用这些思想的例子。虽然自动机和语言理论在众多编译器上的应用如今已经广为人知，以至于这些内容通常已经包含在介绍编译技术的课程中，但是还存在一些较新的用途，包括用来验证协议的模型验证算法以及采用上下文无关文法的模式的文本描述语言等，本书对此进行了补充说明。
本书用法
本书适用于本科三年级以上学生的一季度或一学期的课程。在斯坦福大学，我们把这份讲义用在CS154课程（即自动机和语言理论课程）中。这是一门一季度的课程，Rajeev和Jeffrey都曾经教过。由于授课时间有限，第11章不包括在授课范围以内，其他一些材料（比如较难的多项式时间归约等内容）也省略了。本书的网站（参见下面）包括CS154课程的笔记和教学大纲等材料。
几年前我们发现，许多进入斯坦福大学的研究生都学过一门不包括难解性理论的自动机理论课程。由于斯坦福大学的全体教员相信，对于每一位计算机科学家来说，仅仅停留在知道“NP完全意味着需要花费很长时间”这一层面是远远不够的，充分了解这些思想是十分必要的，所以就有了另外一门课程CS154N，选这个课的学生可以只学习第8～10章。他们实际上学习的是CS154课程大约后三分之一部分的内容，以此来满足CS154N课程的要求。即使在今天，我们仍然发现，每个季度都有一些学生采取这种优化的课程选项。由于这样做几乎不需要额外的努力，所以我们推荐使用这种方法。
预备知识
为了最好地使用本书，读者应当学过一门关于离散数学（如图、树、逻辑、证明技巧等）的课程。我们还假设读者学过一些有关程序设计的课程，熟悉常见的数据结构、递归和主要系统组件（如编译器）的作用等。这些预备知识一般应当包含在大学一、二年级计算机科学课程计划中。
习题
本书包含大量的习题，几乎每个章节都有。我们将较难的习题或其中的某一部分用单个叹号标出，最难的则用两个叹号标出。
某些习题或其中的某一部分标有星号。对于这部分习题，其解答方法可以通过本书的网页获得。这些解答可以公开获得，只限于进行自我检查。需要注意的一点是，在少数情况下，习题B要求修改或改编对另一个习题A的解答。如果A的某些部分有解答，那么你就可以预期B的对应部分也有解答。
Gradiance 在线作业
本书第3版有一个新的特色，即增加了一套由Gradiance公司开发的在线作业系统。教师可以利用它给学生安排课后作业，或者给那些没有选课的学生提供一个特殊的综合课程（不是由老师申请开设的课程），使得他们可以利用这些课后作业作为练习和指导。Gradiance系统所提供的问题和普通问题的形式一样，但会对你提交的解决方案进行检查。如果你提交的答案不正确，系统将会提供一些针对性的建议或反馈意见，以帮助纠正你的解决方案。只要你的老师允许，就可以重复尝试，直到达到满意的分数为止。
所有在北美地区购买这本书第3版的读者，都将自动获得这项Gradiance在线作业服务的授权。更多的信息，请访问Addison-Wesley网站 www.aw.com/gradiance 或者发邮件给 computing@aw.com 。
万维网上的支持
本书的主页是http://www-db.stanford.edu/~ullman/ialc.html。其中包含带星号习题的解答、已知的勘误表、后备材料等。我们希望提供所教CS154课程的所有笔记材料，包括课后作业、习题解答和考试等。
致谢
Craig Silverstein关于“如何进行证明”的讲稿为本书第1章中的一些材料提供了借鉴。对本书第2版手稿（2000年）的评论和勘误来自Zoe Abrams、George Candea、Haowen Chen、Byong-Gun Chun、Jeffrey Shallit、Bret Taylor、Jason Townsend和Erik Uzureau等。
第一，在1979年，自动机和语言理论还是一个比较活跃的研究领域。那本书的主要目的是鼓励擅长数学的学生为这个领域做出新的贡献。然而今天，直接针对自动机理论的研究几乎已经销声匿迹（相反，更多的是对其应用的研究），因此也就没有理由继续保持1979年那本书的简洁和高度数学化的风格。
第二，近年来，自动机和语言理论的角色已经发生了很大的变化。在1979年，自动机还主要是研究生水平的专题，那时我们假定的读者是高年级研究生，特别是使用这本书后几章的那些读者。然而到了今天，它已经成为本科生课程的主要内容。正是基于这个原因，本书在编排时必须假定读者只有很少的预备知识，因此必须比前一版本的书提供更多的背景知识介绍和论证的细节。
第三，计算机科学在过去的几十年里已经发展到了几乎无法想象的程度。在1979年，我们可能会觉得经受得起下一轮技术考验的材料太少了，以至于排满课程计划都很难，然而今天，却有非常多的子科目在竞争本科生课程的有限空间。
第四，计算机科学如今已经发展成为更加职业化的科目，在许多学习它的学生中存在着严重的实用主义倾向。但我们仍然相信，自动机理论的方方面面是各种新兴学科的重要工具，并且也相信，无论学生多么倾向于只去学习那些最能直接赚钱的技术，但在典型的自动机课程中，那些理论的和有利于拓宽思维的习题依然可以保持其价值。然而，为了保证这个科目在计算机科学专业学生的课程表中继续占有一席之地，我们认为有必要在强调数学理论的同时强调应用。因此，我们把上一版中许多比较深奥的主题换成了本版中如何使用这些思想的例子。虽然自动机和语言理论在众多编译器上的应用如今已经广为人知，以至于这些内容通常已经包含在介绍编译技术的课程中，但是还存在一些较新的用途，包括用来验证协议的模型验证算法以及采用上下文无关文法的模式的文本描述语言等，本书对此进行了补充说明。
本书用法
本书适用于本科三年级以上学生的一季度或一学期的课程。在斯坦福大学，我们把这份讲义用在CS154课程（即自动机和语言理论课程）中。这是一门一季度的课程，Rajeev和Jeffrey都曾经教过。由于授课时间有限，第11章不包括在授课范围以内，其他一些材料（比如较难的多项式时间归约等内容）也省略了。本书的网站（参见下面）包括CS154课程的笔记和教学大纲等材料。
几年前我们发现，许多进入斯坦福大学的研究生都学过一门不包括难解性理论的自动机理论课程。由于斯坦福大学的全体教员相信，对于每一位计算机科学家来说，仅仅停留在知道“NP完全意味着需要花费很长时间”这一层面是远远不够的，充分了解这些思想是十分必要的，所以就有了另外一门课程CS154N，选这个课的学生可以只学习第8～10章。他们实际上学习的是CS154课程大约后三分之一部分的内容，以此来满足CS154N课程的要求。即使在今天，我们仍然发现，每个季度都有一些学生采取这种优化的课程选项。由于这样做几乎不需要额外的努力，所以我们推荐使用这种方法。
预备知识
为了最好地使用本书，读者应当学过一门关于离散数学（如图、树、逻辑、证明技巧等）的课程。我们还假设读者学过一些有关程序设计的课程，熟悉常见的数据结构、递归和主要系统组件（如编译器）的作用等。这些预备知识一般应当包含在大学一、二年级计算机科学课程计划中。
习题
本书包含大量的习题，几乎每个章节都有。我们将较难的习题或其中的某一部分用单个叹号标出，最难的则用两个叹号标出。
某些习题或其中的某一部分标有星号。对于这部分习题，其解答方法可以通过本书的网页获得。这些解答可以公开获得，只限于进行自我检查。需要注意的一点是，在少数情况下，习题B要求修改或改编对另一个习题A的解答。如果A的某些部分有解答，那么你就可以预期B的对应部分也有解答。
Gradiance 在线作业
本书第3版有一个新的特色，即增加了一套由Gradiance公司开发的在线作业系统。教师可以利用它给学生安排课后作业，或者给那些没有选课的学生提供一个特殊的综合课程（不是由老师申请开设的课程），使得他们可以利用这些课后作业作为练习和指导。Gradiance系统所提供的问题和普通问题的形式一样，但会对你提交的解决方案进行检查。如果你提交的答案不正确，系统将会提供一些针对性的建议或反馈意见，以帮助纠正你的解决方案。只要你的老师允许，就可以重复尝试，直到达到满意的分数为止。
所有在北美地区购买这本书第3版的读者，都将自动获得这项Gradiance在线作业服务的授权。更多的信息，请访问Addison-Wesley网站 www.aw.com/gradiance 或者发邮件给 computing@aw.com 。
万维网上的支持
本书的主页是http://www-db.stanford.edu/~ullman/ialc.html。其中包含带星号习题的解答、已知的勘误表、后备材料等。我们希望提供所教CS154课程的所有笔记材料，包括课后作业、习题解答和考试等。
致谢
Craig Silverstein关于“如何进行证明”的讲稿为本书第1章中的一些材料提供了借鉴。对本书第2版手稿（2000年）的评论和勘误来自Zoe Abrams、George Candea、Haowen Chen、Byong-Gun Chun、Jeffrey Shallit、Bret Taylor、Jason Townsend和Erik Uzureau等。
媒体评论
本书是关于形式语言、自动机理论和计算复杂性方面的经典英亚注册，是三位理论计算大师的巅峰之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、图灵机、不可判定性以及难解问题等内容。
本书已被世界许多著名大学选为计算机理论课程的英亚注册或教学参考书，适合作为高校计算机专业高年级本科生及研究生的英亚注册，还可供从事理论计算工作的研究人员参考。
作者简介
约翰·E. 霍普克罗夫特（John E. Hopcroft） 1986年图灵奖获得者、美国国家工程院院士、美国国家科学院院士、美国国家艺术与科学院院士、中国科学院外籍院士、美国康奈尔大学教授。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。他和Jeffrey D. Ullman一起获得2010年IEEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
拉杰夫·莫特瓦尼（Rajeev Motwani） 斯坦福大学计算机科学系教授。他的研究兴趣包括数据库、数据挖掘、Web搜索和信息检索、机器人等。他于2009年6月意外身亡。
杰弗里·D. 乌尔曼（Jeffrey D. Ullman） 2020年图灵奖获得者、美国国家工程院院士、斯坦福大学计算机科学系名誉教授。他的研究兴趣包括数据库理论、数据库集成、数据挖掘、理论计算等。他和John E. Hopcroft一起获得2010年IEEE颁发的约翰·冯诺依曼奖。
本书已被世界许多著名大学选为计算机理论课程的英亚注册或教学参考书，适合作为高校计算机专业高年级本科生及研究生的英亚注册，还可供从事理论计算工作的研究人员参考。
作者简介
约翰·E. 霍普克罗夫特（John E. Hopcroft） 1986年图灵奖获得者、美国国家工程院院士、美国国家科学院院士、美国国家艺术与科学院院士、中国科学院外籍院士、美国康奈尔大学教授。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。他和Jeffrey D. Ullman一起获得2010年IEEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
拉杰夫·莫特瓦尼（Rajeev Motwani） 斯坦福大学计算机科学系教授。他的研究兴趣包括数据库、数据挖掘、Web搜索和信息检索、机器人等。他于2009年6月意外身亡。
杰弗里·D. 乌尔曼（Jeffrey D. Ullman） 2020年图灵奖获得者、美国国家工程院院士、斯坦福大学计算机科学系名誉教授。他的研究兴趣包括数据库理论、数据库集成、数据挖掘、理论计算等。他和John E. Hopcroft一起获得2010年IEEE颁发的约翰·冯诺依曼奖。
