计算理论导引 (豆瓣)

作者: [美]Michael Sipser
出版社: 机械工业出版社
副标题: 第2版
原作名: Introduction to the Theory of Computation
译者: 唐常杰 / 陈鹏 / 向勇 / 刘齐宏
出版年: 2006-7
页数: 269
定价: 36.00元
丛书: 计算机科学丛书
ISBN: 9787111190288

豆瓣评分

9.3

183人评价

5星

63.9%
4星

25.1%
3星

10.9%
2星

0.0%
1星

0.0%

评价:

内容简介 · · · · · ·

本书是计算理论领域的经典著作，被国外多所大学选用为教材。本书以注重思路、深入引导为特色，系统地介绍计算理论的三大主要内容：自动机与语言、可计算性理论和计算复杂性理论。同时，对可计算性和计算复杂性理论中的某些高级内容作了重点讲解。全书通过启发性的问题、精彩的结果和待解决问题来引导读者挑战此领域中的高层次问题。新版的一大亮点是增加了更多习题、教辅资料和部分习题解答，更加有利于教学。

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

目录 · · · · · ·

出版者的话
专家指导委员会
译者序
译者简介
第1版前言
第2版前言
· · · · · · (更多)

豆瓣成员常用的标签(共104个) · · · · · ·

计算理论计算机科学计算机数学计算复杂性自动机算法 CS

丛书信息

　　计算机科学丛书 (共449册), 这套丛书还有《算法（第5部分）》,《Web服务》,《高性能科学与工程计算》,《语言与机器》,《数据挖掘：实用机器学习工具与技术（原书第3版）》等。

喜欢读"计算理论导引"的人也喜欢的电子书 · · · · · ·

支持 Web、iPhone、iPad、Android 阅读器

: Python源码剖析

38.39元

: CoffeeScript小书

1.99元

: 程序员的自我修养

36.00元

: MacTalk·人生元编程

2.99元

: 思考的乐趣

18.00元

喜欢读"计算理论导引"的人也喜欢 · · · · · ·

: 组合数学

: 自动机理论、语言和计算导论(英文...

: 计算机程序的构造和解释

: 计算机系统：核心概念及软硬件实现...

: 计算机系统要素

: 离散数学及其应用（原书第5版）

: 计算机系统：系统架构与操作系统的...

: 自动机理论、语言和计算导论（原书...

: 逻辑的引擎

: 具体数学（英文版第2版）

我来说两句

短评 · · · · · · ( 全部 53 条 )

计算理论导引的话题 · · · · · · ( 全部条 )

什么是话题

无论是一部作品、一个人，还是一件事，都往往可以衍生出许多不同的话题。将这些话题细分出来，分别进行讨论，会有更多收获。

我要写书评

计算理论导引的书评 · · · · · · ( 全部 8 条 )

我们为什么要学习计算理论

在所有我看过的计算理论、可计算性、计算复杂度的教材中，Sipser的这本Introduction to the Theory of Computation是最适合入门的。把计算理论这么个艰深的学问讲解得清晰简洁，直观易懂。而且涵盖了计算理论的各个经典内容。作为一本introduction，真是再好不过了。计算理论... (展开)

131

22回应

平凡的老鱼 2009-03-09 15:19:17

很不错的关于计算理论的介绍

事知其然而后知其所以然。现代计算机体系的构建，图灵机的数学模型的实现，正是指出了这道创世纪的光。现在书里面的内容已经忘记的差不多了，只是记得不断的证明，一步步的证明，充满了智慧的光芒。总之，是一本好的数学书。 (展开)

1回应

RONGE KUTA 2011-03-20 21:22:00

非常易读的计算理论教材

我觉得作者很可爱，他同很多人一样很喜欢把一个复杂的问题说的很简单很通俗。对于这本书来说，看了第一章，就应当一成的收获。计算机中重要的数学概念被解构的如此清楚，非常的难得。另外，要说一下，翻译的问题。翻译的很不错（话说本来英文版就很上口），但是却是看原版会... (展开)

1 1回应

陈炬 2009-03-19 11:11:59 机械工业出版社2002版

CS学生必读书籍

让人了解计算机的本质，它的能力与它的局限性。计算理论课的教材，上课上的很累，但很有收获。我觉得没读过这本书的不好意思说自己是Computer Science专业毕业的。 (展开)

1 1回应

我要飞羊习习 2012-06-13 20:35:42 Cengage Learning2005版

我想问问这本书有中文的翻译版么

RT，英语真心一般啊，想看看有木有翻译版本的，Introduction to the Theory of Computation，第二版，请各位大神指导一下，请告知翻译版本的书名，出版社等信息 RT，英语真心一般啊，想看看有木有翻译版本的，Introduction to the Theory of Computation，第二版，请各位大神指... (展开)

4 2回应

ying17zi 2011-09-21 05:19:35 Cengage Learning2005版

Introduction to “困难问题”

如果你周围的人在说P， NP之类，而你还不知道这些概念，请捧起这本书！之后，如果你还想去解决它们，寻求解决思路可以参考这本Metaheuristics For Hard Optimization (展开)

1 3回应

老鼠阿多 2007-12-29 15:51:47 机械工业出版社2006版

druidconanrei评论计算理论导引(英文版第2版新版)

本书的作者是著名的计算理论方面专家，麻省理工学院应用数学系主任 M. Sipser。全书分为11章，并附有部分习题解答。全书思路清晰，由浅入深，内容详细，是一本零起点学习计算理论的理想教材。我是出于研究需要阅读此书的。其中第零章简要介绍了所需要的基本数学知识。第一到三... (展开)

5 0回应

xyinktw 2013-07-15 14:43:43

绝版了？

这篇书评可能有关键情节透露

看了好几家都是没货，机械工业2006出版的这本绝版了？？啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 (展开)

3 1回应

> 更多书评8篇

读书笔记 · · · · · ·

我来写笔记

按有用程度
按页码先后
最新笔记

展开收起
第81页

Alan (be real. be cool.)

图灵机定义(Q, Σ, Γ, \delta, q_0, q_accept, q_reject)七元组图灵机的纸带无穷长，可读可写，是目前最强大的计算模型，也是目前计算机体系的计算模型图灵机与多带图灵机和非确定图灵机等价。图灵机可识别是对图灵机识别的语言到达接受状态，其他语言不确定。图灵机可判定是对图灵机识别语言到达接受状态，其他语言拒绝状态。希尔伯特问题：D={p|p是有整数根的多项式}，D是否可判定？否丘奇—图灵论题：一切合..
2013-02-17 20:59

图灵机定义(Q, Σ, Γ, \delta, q_0, q_accept, q_reject)七元组
图灵机的纸带无穷长，可读可写，是目前最强大的计算模型，也是目前计算机体系的计算模型
图灵机与多带图灵机和非确定图灵机等价。
图灵机可识别是对图灵机识别的语言到达接受状态，其他语言不确定。
图灵机可判定是对图灵机识别语言到达接受状态，其他语言拒绝状态。
希尔伯特问题：D={p|p是有整数根的多项式}，D是否可判定？否
丘奇—图灵论题：一切合理的计算模型都等同于图灵机。
图灵设计的TM计算法是对算法的精确定义，命令式编程便是基于此。
丘奇通过λ演算定义了算法，函数式编程。
TM同λ演算在算法上是等价的。

推荐

回应 2013-02-17 20:59
展开收起
第59页

Alan (be real. be cool.)

CFG可以由四元组描述(V, Σ, R, S) 设计CFG： 1 CFG可以由几个简单CFG组成 2 正则部分可以根据DFA状态转变成CFG的R 3 R-> uRv的应用 4 递归包含结构 CFG可以简化符合乔姆斯基范式 PDA可以由六元组(Q, Σ, Γ, \delta, q_0, F)来描述，同CFG等价。同DFA相比，多应用了栈数据结构，虽然栈可以无穷大，但是只能访问栈顶内容。 CFG的泵引理可以识别CFL。
2013-02-17 20:35

CFG可以由四元组描述(V, Σ, R, S)
设计CFG：
1 CFG可以由几个简单CFG组成
2 正则部分可以根据DFA状态转变成CFG的R
3 R-> uRv的应用
4 递归包含结构
CFG可以简化符合乔姆斯基范式
PDA可以由六元组(Q, Σ, Γ, \delta, q_0, F)来描述，同CFG等价。同DFA相比，多应用了栈数据结构，虽然栈可以无穷大，但是只能访问栈顶内容。
CFG的泵引理可以识别CFL。

推荐

回应 2013-02-17 20:35
展开收起
第19页

Alan (be real. be cool.)

能够被DFA识别的语言是正则语言 DFA，NFA，正则表达式是等价的，都可以表达正则语言。 FA可以用五元组来描述 (Q, Σ, \delta q_start, q_accept)。正则语言可以用泵引理来判定。
2013-02-17 20:21

能够被DFA识别的语言是正则语言
DFA，NFA，正则表达式是等价的，都可以表达正则语言。
FA可以用五元组来描述 (Q, Σ, \delta q_start, q_accept)。
正则语言可以用泵引理来判定。

推荐

回应 2013-02-17 20:21

展开收起
第19页

Alan (be real. be cool.)

能够被DFA识别的语言是正则语言 DFA，NFA，正则表达式是等价的，都可以表达正则语言。 FA可以用五元组来描述 (Q, Σ, \delta q_start, q_accept)。正则语言可以用泵引理来判定。
2013-02-17 20:21

能够被DFA识别的语言是正则语言
DFA，NFA，正则表达式是等价的，都可以表达正则语言。
FA可以用五元组来描述 (Q, Σ, \delta q_start, q_accept)。
正则语言可以用泵引理来判定。

推荐

回应 2013-02-17 20:21
展开收起
第59页

Alan (be real. be cool.)

CFG可以由四元组描述(V, Σ, R, S) 设计CFG： 1 CFG可以由几个简单CFG组成 2 正则部分可以根据DFA状态转变成CFG的R 3 R-> uRv的应用 4 递归包含结构 CFG可以简化符合乔姆斯基范式 PDA可以由六元组(Q, Σ, Γ, \delta, q_0, F)来描述，同CFG等价。同DFA相比，多应用了栈数据结构，虽然栈可以无穷大，但是只能访问栈顶内容。 CFG的泵引理可以识别CFL。
2013-02-17 20:35

CFG可以由四元组描述(V, Σ, R, S)
设计CFG：
1 CFG可以由几个简单CFG组成
2 正则部分可以根据DFA状态转变成CFG的R
3 R-> uRv的应用
4 递归包含结构
CFG可以简化符合乔姆斯基范式
PDA可以由六元组(Q, Σ, Γ, \delta, q_0, F)来描述，同CFG等价。同DFA相比，多应用了栈数据结构，虽然栈可以无穷大，但是只能访问栈顶内容。
CFG的泵引理可以识别CFL。

推荐

回应 2013-02-17 20:35
展开收起
第81页

Alan (be real. be cool.)

图灵机定义(Q, Σ, Γ, \delta, q_0, q_accept, q_reject)七元组图灵机的纸带无穷长，可读可写，是目前最强大的计算模型，也是目前计算机体系的计算模型图灵机与多带图灵机和非确定图灵机等价。图灵机可识别是对图灵机识别的语言到达接受状态，其他语言不确定。图灵机可判定是对图灵机识别语言到达接受状态，其他语言拒绝状态。希尔伯特问题：D={p|p是有整数根的多项式}，D是否可判定？否丘奇—图灵论题：一切合..
2013-02-17 20:59

图灵机定义(Q, Σ, Γ, \delta, q_0, q_accept, q_reject)七元组
图灵机的纸带无穷长，可读可写，是目前最强大的计算模型，也是目前计算机体系的计算模型
图灵机与多带图灵机和非确定图灵机等价。
图灵机可识别是对图灵机识别的语言到达接受状态，其他语言不确定。
图灵机可判定是对图灵机识别语言到达接受状态，其他语言拒绝状态。
希尔伯特问题：D={p|p是有整数根的多项式}，D是否可判定？否
丘奇—图灵论题：一切合理的计算模型都等同于图灵机。
图灵设计的TM计算法是对算法的精确定义，命令式编程便是基于此。
丘奇通过λ演算定义了算法，函数式编程。
TM同λ演算在算法上是等价的。

推荐

回应 2013-02-17 20:59

展开收起
第81页

Alan (be real. be cool.)

图灵机定义(Q, Σ, Γ, \delta, q_0, q_accept, q_reject)七元组图灵机的纸带无穷长，可读可写，是目前最强大的计算模型，也是目前计算机体系的计算模型图灵机与多带图灵机和非确定图灵机等价。图灵机可识别是对图灵机识别的语言到达接受状态，其他语言不确定。图灵机可判定是对图灵机识别语言到达接受状态，其他语言拒绝状态。希尔伯特问题：D={p|p是有整数根的多项式}，D是否可判定？否丘奇—图灵论题：一切合..
2013-02-17 20:59

图灵机定义(Q, Σ, Γ, \delta, q_0, q_accept, q_reject)七元组
图灵机的纸带无穷长，可读可写，是目前最强大的计算模型，也是目前计算机体系的计算模型
图灵机与多带图灵机和非确定图灵机等价。
图灵机可识别是对图灵机识别的语言到达接受状态，其他语言不确定。
图灵机可判定是对图灵机识别语言到达接受状态，其他语言拒绝状态。
希尔伯特问题：D={p|p是有整数根的多项式}，D是否可判定？否
丘奇—图灵论题：一切合理的计算模型都等同于图灵机。
图灵设计的TM计算法是对算法的精确定义，命令式编程便是基于此。
丘奇通过λ演算定义了算法，函数式编程。
TM同λ演算在算法上是等价的。

推荐

回应 2013-02-17 20:59
展开收起
第59页

Alan (be real. be cool.)

CFG可以由四元组描述(V, Σ, R, S) 设计CFG： 1 CFG可以由几个简单CFG组成 2 正则部分可以根据DFA状态转变成CFG的R 3 R-> uRv的应用 4 递归包含结构 CFG可以简化符合乔姆斯基范式 PDA可以由六元组(Q, Σ, Γ, \delta, q_0, F)来描述，同CFG等价。同DFA相比，多应用了栈数据结构，虽然栈可以无穷大，但是只能访问栈顶内容。 CFG的泵引理可以识别CFL。
2013-02-17 20:35

CFG可以由四元组描述(V, Σ, R, S)
设计CFG：
1 CFG可以由几个简单CFG组成
2 正则部分可以根据DFA状态转变成CFG的R
3 R-> uRv的应用
4 递归包含结构
CFG可以简化符合乔姆斯基范式
PDA可以由六元组(Q, Σ, Γ, \delta, q_0, F)来描述，同CFG等价。同DFA相比，多应用了栈数据结构，虽然栈可以无穷大，但是只能访问栈顶内容。
CFG的泵引理可以识别CFL。

推荐

回应 2013-02-17 20:35
展开收起
第19页

Alan (be real. be cool.)

能够被DFA识别的语言是正则语言 DFA，NFA，正则表达式是等价的，都可以表达正则语言。 FA可以用五元组来描述 (Q, Σ, \delta q_start, q_accept)。正则语言可以用泵引理来判定。
2013-02-17 20:21

能够被DFA识别的语言是正则语言
DFA，NFA，正则表达式是等价的，都可以表达正则语言。
FA可以用五元组来描述 (Q, Σ, \delta q_start, q_accept)。
正则语言可以用泵引理来判定。

推荐

回应 2013-02-17 20:21

论坛 · · · · · ·


波斯特对应问题的一个匹配是否要把所有骨牌都用上？	来自飞猫		2014-02-09
请问这本书得翻译怎样？	来自有机体	1 回应	2013-08-17
pp.120上关于证明REGULAR_TM的不可判定性没问题？	来自哗呀哩呜	6 回应	2012-05-07
计算理论导引定理6.14 的证明	来自小碗豆		2011-12-14
很好的书！	来自conquersky		2007-11-10