计算理论导引
￥ 51 7.4折 ￥ 69 全新
库存40件
四川成都
认证卖家担保交易快速发货售后保障
作者(美)迈克尔·西普塞(Michael Sipser) 著;段磊 等 译
出版社机械工业出版社
ISBN9787111499718
出版时间2015-08
装帧平装
开本16开
定价69元
货号1201147867
上书时间2024-06-16
- 在售商品 暂无
- 平均发货时间 7小时
- 好评率 暂无
商品详情
- 品相描述：全新
- 商品描述
-
目录
出版者的话
译者序
第3版前言
第2版前言
版前言
第0章绪论
0.1自动机、可计算性与复杂性
0.1.1计算复杂性理论
0.1.2可计算性理论
0.1.3自动机理论
0.2数学概念和术语
0.2.1集合
0.2.2序列和多元组
0.2.3函数和关系
0.2.4图
0.2.5字符串和语言
0.2.6布尔逻辑
0.2.7数学名词汇总
0.3定义、定理和证明
0.4证明的类型
0.4.1构造性证明
0.4.2反证法
0.4.3归纳法
练习
问题
习题选解
部分自动机与语言
章正则语言
1.1有穷自动机
1.1.1有穷自动机的形式化定义
1.1.2有穷自动机举例
1.1.3计算的形式化定义
1.1.4设计有穷自动机
1.1.5正则运算
1.2非确定性
1.2.1非确定型有穷自动机的形式化定义
1.2.2NFA与DFA的等价性
1.2.3在正则运算下的封闭性
1.3正则表达式
1.3.1正则表达式的形式化定义
1.3.2与有穷自动机的等价性
1.4非正则语言
练习
问题
习题选解
第2章上下文无关文法
2.1上下文无关文法概述
2.1.1上下文无关文法的形式化定义
2.1.2上下文无关文法举例
2.1.3设计上下文无关文法
2.1.4歧义性
2.1.5乔姆斯基范式
2.2下推自动机
2.2.1下推自动机的形式化定义
2.2.2下推自动机举例
2.2.3与上下文无关文法的等价性
2.3非上下文无关语言
2.4确定型上下文无关语言
2.4.1DCFL的性质
2.4.2确定型上下文无关文法
2.4.3DPDA和DCFG的关系
2.4.4语法分析和LR(k)文法
练习
问题
习题选解
第二部分可计算性理论
第3章丘奇图灵论题
3.1图灵机
3.1.1图灵机的形式化定义
3.1.2图灵机的例子
3.2图灵机的变形
3.2.1多带图灵机
3.2.2非确定型图灵机
3.2.3枚举器
3.2.4与其他模型的等价性
3.3算法的定义
3.3.1希尔伯特问题
3.3.2描述图灵机的术语
练习
问题
习题选解
第4章可判定性
4.1可判定语言
4.1.1与正则语言相关的可判定性问题
4.1.2与上下文无关语言相关的可判定性问题
4.2不可判定性
4.2.1对角化方法
4.2.2不可判定语言
4.2.3一个图灵不可识别语言
练习
问题
习题选解
第5章可归约性
5.1语言理论中的不可判定问题
5.2一个简单的不可判定问题
5.3映射可归约性
5.3.1可计算函数
5.3.2映射可归约性的形式化定义
练习
问题
习题选解
第6章可计算性理论的不错专题
6.1递归定理
6.1.1自引用
6.1.2递归定理的术语
6.1.3应用
6.2逻辑理论的可判定性
6.2.1一个可判定的理论
6.2.2一个不可判定的理论
6.3图灵可归约性
6.4信息的定义
6.4.1极小长度的描述
6.4.2定义的优化
6.4.3不可压缩的串和随机性
练习
问题
习题选解
第三部分复杂性理论
第7章时间复杂性
7.1度量复杂性
7.1.1大O和小o记法
7.1.2分析算法
7.1.3模型间的复杂性关系
7.2P类
7.2.1多项式时间
7.2.2P中的问题举例
7.3NP类
7.3.1NP中的问题举例
7.3.2P与NP问题
7.4NP完全性
7.4.1多项式时间可归约性
7.4.2NP完全性的定义
7.4.3库克列文定理
7.5几个NP完全问题
7.5.1顶点覆盖问题
7.5.2哈密顿路径问题
7.5.3子集和问题
练习
问题
习题选解
第8章空间复杂性
8.1萨维奇定理
8.2PSPACE类
8.3PSPACE完全性
8.3.1TQBF问题
8.3.2博弈的必胜策略
8.3.3广义地理学
8.4L类和NL类
8.5NL完全性
8.6NL等于coNL
练习
问题
习题选解
第9章难解性
9.1层次定理
9.2相对化
9.3电路复杂性
练习
问题
习题选解
0章复杂性理论不错专题
10.1近似算法
10.2概率算法
10.2.1BPP类
10.2.2素数性
10.2.3只读一次的分支程序
10.3交错式
10.3.1交错式时间与交错式空间
10.3.2多项式时间层次
10.4交互式证明系统
10.4.1图的非同构
10.4.2模型的定义
10.4.3IP=PSPACE
10.5并行计算
10.5.1一致布尔电路
10.5.2NC类
10.5.3P完全性
10.6密码学
10.6.1密钥
10.6.2公钥密码系统
10.6.3单向函数
10.6.4天窗函数
练习
问题
习题选解
参考文献
索引
内容摘要
本书由计算理论领域的知名非常不错MichaelSipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。
精彩内容
第3版前言Introduction to the Theory of Computation,3e本版新增了关于确定型上下文无关语言的一节。我选择这个主题有以下几个原因。首先，它填补了我之前对自动机理论和语言处理之间的明显空白。以前的版本介绍了有穷自动机以及图灵机在确定型和非确定型上的变形，但却只包含了下推自动机的非确定型变形。因此，增加关于确定型下推自动机的讨论正如同找到完成拼图游戏所缺的那块。 其次，确定型上下文无关文法理论是LR(k)文法的基础，同时也是自动机理论在编程语言和编译器设计上重要且非平凡应用的基础。这个应用将一些关键概念，包括确定型和非确定型有穷自动机的等价性、上下文无关文法和下推自动机之间的相互转换，汇聚一起得到一个高效且漂亮的语法分析方法。这里我们实现了理论和实践的相互联系。 最后，虽然该主题作为自动机理论一个真实的应用非常重要，但它在现有理论教科书中却没有得到足够重视。我研究LR(k)文法多年但一直没有完整理解它们如何工作，也没有看到它们与确定型上下文无关语言理论的完美契合。我写作这一节旨在为理论学者和实践者提供关于这个领域直观而不失严谨的介绍，并由此对该领域做出贡献。需要注意的是：这一节的部分内容非常具有挑战性，因此基础理论课程的教师可考虑将其作为补充读物。之后的章节不依赖于这部分内容。 在撰写本版的过程中，很多人给了我直接或间接的帮助。我很感激两位审阅者Christos Kapoutsis和Cem Say。他们阅读了这一版新内容的初稿，并提供了很有价值的反馈意见。在Cengage Learning的一些人协助了本书的出版工作，特别是Alyssa Pratt和Jennifer FeltriGeorge。Suzanne Huizenga编辑了文字，ByteGraphics的Laura Segel绘制了新的图片并修改了以前版本中的图片。 感谢我在MIT的助教：Victor Chen, Andy Drucker, Michael Forbes, Elena Grigorescu, Brendan Juba, Christos Kapoutsis, Jon Kelner, Swastik Kopparty, Kevin Matulef, Amanda Redlich, Zack Remscrim, Ben Rossman, Shubhangi Saraf, Oren Weimann。他们都给予了我帮助，包括：讨论新的问题并给出解决方法，提出如何让学生理解课程内容的见解。我非常享受与这群有天赋、有热情的年轻人一起工作。 我很高兴收到了来自世界各地的邮件，非常感谢你们的建议、问题和思路。这里有一个相关人员列表，他们的意见对这个版本产生了影响： Djihed Afifi, Steve Aldrich, Eirik Bakke, Suzanne Balik, Victor Bandur, Paul Beame, Elazar Birnbaum, Goutam Biswas, Rob Bittner, Marina Blanton, Rodney Bliss, Promita Chakraborty, Lewis Collier, Jonathan Deber, Simon Dexter, Matt Diephouse, Peter Dillinger, Peter Drake, Zhidian Du, Peter Fejer, Margaret Fleck, Atsushi Fujioka, Valerio Genovese, Evangelos Georgiadis, Joshua Grochow, Jerry Grossman, Andreas Guelzow, Hjalmtyr Hafsteinsson, Arthur Hall III, Cihat Imamoglu, Chinawat Isradisaikul, Kayla Jacobs, Flemming Jensen, Barbara Kaiser, Matthew Kane, Christos Kapoutsis, Ali Durlov Khan, Edwin Sze Lun Khoo, Yongwook Kim, Akash Kumar, Eleazar Leal, Zsolt Lengvarszky, ChengChung Li, Xiangdong Liang, Vladimir Lifschitz, Ryan Lortie, Jonathan Low, Nancy Lynch, Alexis Maciel, Kevin Matulef, Nelson Max, HansRudolf Metz, Mladen Mika, Sara Miner More, Rajagopal Nagarajan, Marvin Nakayama, Jonas Nyrup, Gregory Roberts, Ryan Romero, Santhosh Samarthyam, Cem Say, Joel Seiferas, John Sieg, Marc Smith, John Steinberger, Nuri Ta？瘙塂demir, Tamir Tassa, Mark Testa, Jesse Tjang, John Trammell, Hiroki Ueda, Jeroen Vaelen, Kurt L. Van Etten, Guillermo Vázquez, Phanisekhar Botlaguduru Venkata, Benjamin BingYi Wang, Lutz Warnke, David Warren, Thomas Watson, Joseph Wilson, David Wittenberg, Brian Wongchaowart, Kishan Yerubandi, Dai Yi。 最重要的是，我要感谢我的家人——我的妻子Ina以及我们的孩子Rachel和Aaron。时光荏苒，岁月如梭，你们的爱就是一切。 Michael Sipser马萨诸塞州，剑桥2012年4月第2版前言Introduction to the Theory of Computation,3e大量读者来的电子邮件反映，版没有习题解答是一个缺陷。这一版弥补了这一缺陷。每一章现在都增加了“习题选解”小节，给出了该章的练习和问题中有代表性题目的答案。给出了答案的问题就不能再作为有趣的有挑战性的家庭作业，为弥补这一损失，又添加了若干新问题。教师可以和wwwcoursecom上所指定的相应地区的销售代表联系，索取一份教师手册，其中包含了附加的答案。 第2版的国际版是针对国外读者的。尽管涵盖了同样的主题，它和标准第2版还是有所不同，并且不是用来替代标准第2版的。 许多读者更喜欢学习更多的“标准”主题，比如MyhillNerode定理和Rice定理。通过将这些主题展示在给出答案的问题中，我部分地采纳了这些读者的意见。没有将MyhillNerode定理放到书本主体中是因为我认为，这门课程的目标是初步介绍而非深入研究有穷自动机。有穷自动机在这里的角色是使学生通过研究计算的简单形式模型，为了解复杂模型奠定基础，同时为后续的主题提供方便的例子。当然，一些人希望有更全面的内容，同时另一些人觉得应该略去所有对有穷自动机的引用（或者至少是依赖）。尽管Rice定理对于不可判定性的证明是一个有用的“工具”，第2版还是没有将它放到书本主体中，因为一些学生可能只是机械地使用它而没有真正理解其作用。换用归约来证明不可判定性，可以为学习复杂性理论中出现的归约做更好的准备。 我很感谢我的助教Ilya Baran、Sergi Elizalde、Rui Fan、Jonathan Feldman、Venkatesan Guruswami、Prahladh Harsha、Christos Kapoutsis、Julia Khodor、Adam Klivans、Kevin Matulef、Ioana Popescu、April Rasala、Sofya Raskhodnikova和Iuliu Vasilescu，他们帮助我草拟了若干新问题及其答案。Ching Law、Edmond Kayi Lee和Zulfikar Ramzan也为给出答案付出了努力。感谢Victor Shoup提出了一个简洁的方法，用于修整在版中出现在概率原始算法分析中的缺陷。 感谢Course Technology出版社的编辑们的努力，尤其是Alyssa Pratt和Aimee Poirier。多谢Gerald Eisman、Weizhen Mao、Rupak Majumdar、Chris Umans和Christopher Wilson所做的审校。感谢Jerry Moore在编辑上的出色工作，还有ByteGraphics的Laura Segel (lauras@bytegraphicscom) 精彩而又精确的图表再现。 我所收到的电子邮件数量超乎预料。收到来自这么多地方的这么多人的来信绝对是一种快乐。我会尽量回复并向我未曾回复者表示歉意。我在此列出对本书第2版提供了有益的建议的人，同时对所有给我来信的人表示感谢。 Luca Aceto，Arash Afkanpour，Rostom Aghanian，Eric Allender，Karun Bakshi，Brad Ballinger，Ray Bartkus，Louis Barton，Arnold Beckmann，Mihir Bellare，Kevin Trent Bergeson，Matthew Berman，Rajesh Bhatt，Somenath Biswas，Lenore Blum，Mauro ABonatti，Paul Bondin，Nicholas Bone，Ian Bratt，Gene Browder，Doug Burke，Sam Buss，Vladimir Bychkovsky，Bruce Carneal，Soma Chaudhuri，RongJaye Chen，Samir Chopra，Benny Chor，John Clausen，Allison Coates，Anne Condon，Jeffrey Considine，John JCrashell，Claude Crepeau，Shaun Cutts，Susheel MDaswani，Geoff Davis，Scott Dexter，Peter Drake，Jeff Edmonds，Yaakov Eisenberg，Kurtcebe Eroglu，Georg Essl，Alexander TFader，Farzan Fallah，Faith Fich，Joseph EFitzgerald，Perry Fizzano，David Ford，Jeannie Fromer，Kevin Fu，Atsushi Fujioka，Michel Galley，KGanesan，Simson Garfinkel，Travis Gebhardt，Peymann Gohari，Ganesh Gopalakrishnan，Steven Greenberg，Larry Griffith，Jerry Grossman，Rudolf de Haan，Michael Halper，Nick Harvey，Mack Hendricks，Laurie Hiyakumoto，Steve Hockema，Michael Hoehle，Shahadat Hossain，Dave Isecke，Ghaith Issa，Raj DIyer，Christian Jacobi，Thomas Janzen，Mike DJones，Max Kanovitch，Aaron Kaufman，Roger Khazan，Sarfraz Khurshid，Kevin Killourhy，Seungjoo Kim，Victor Kuncak，Kanata Kuroda，Suk YLee，Edward DLegenski，LiWei Lehman，Kong Lei，Zsolt Lengvarszky，Jeffrey Levetin，Baekjun Lim，Karen Livescu，Thomas Lasko，Stephen Louie，TzerHung Low，Wolfgang Maass，Arash Madani，Michael Manapat，Wojciech Marchewka，David MMartin Jr，Anders Martinson，Lyle McGeoch，Alberto Medina，Kurt Mehlhorn，Nihar Mehta，Albert RMeyer，Thomas Minka，Mariya Minkova，Daichi Mizuguchi，GAllen Morris Ⅲ，Damon MoskAoyama，Xiaolong Mou，Paul Muir，German Muller，Donald Nelson，Gabriel Nivasch，Mary Obelnicki，Kazuo Ohta，Thomas MOleson，Jr，Curtis Oliver，Owen Ozier，Rene Peralta，Alexander Perlis，Holger Petersen，Detlef Plump，Robert Prince，David Pritchard，Bina Reed，Nicholas Riley，Ronald Rivest，Robert Robinson，Christi Rockwell，Phil Rogaway，Max Rozenoer，John Rupf，Teodor Rus，Larry Ruzzo，Brian Sanders，Cem Say，Kim Schioett，Joel Seiferas，Joao Carlos Setubal，Geoff Lee Seyon，Mark Skandera，Bob Sloan，Geoff Smith，Marc LSmith，Stephen Smith，Alex CSnoeren，Guy StDenis，Larry Stockmeyer，Radu Stoleru，David Stucki，Hisham MSueyllam，Kenneth Tam，Elizabeth Thompson，Michel Toulouse，Eric Tria，Chittaranjan Tripathy，Dan Trubow，Hiroki Ueda，Giora Unger，Kurt LVan Etten，Jesir Vargas，Bienvenido VelezRivera，Kobus Vos，Alex Vrenios，Sven Waibel，Marc Waldman，Tom Whaley，Anthony Widjaja，Sean Williams，Joseph NWilson，Chris Van Wyk，Guangming Xing，Vee Voon Yee，Cheng Yongxi，Neal Young，Timothy Yuen，Kyle Yung，Jinghua Zhang，Lilla Zollei。 当我夜以继日地坐在我的电脑屏幕前时，尤其要感谢我的家人Ina、Rachel和Aaron的耐心、理解和爱。 Michael Sipser马萨诸塞州，剑桥2004年12月版前言Introduction to the Theory of Computation,3e写给学生欢迎使用本书！ 将要开始学习的是重要而又引人入胜的课题：计算理论。它包括计算机硬件、软件以及某些应用的基本数学特性。这一课程试图回答什么是不能计算的，什么是能计算的，可以算多快，要用多少存储，以及采用什么计算模型等。这些问题与工程实践有着紧密的联系，也具有纯理论的一面。 许多同学主动盼望学习这门课程，有些同学可能只是为了完成计算机科学或者计算机工程的学位必需的理论课程学分——他们也许认为理论比较神秘、难学且用处不大。 通过学习，读者会发现理论既不神秘、也不讨厌，是好理解、甚至是有趣的。理论计算机科学有许多迷人而重要的思想，同时它也有许多细小的、有时甚至是乏味的细节，这些细
— 没有更多了 —
以下为对购买帮助不大的评价