语言与机器:计算机科学理论导论
版权信息
书名：语言与机器计算机科学理论导论
作者：(美)苏达坎
出版社：清华大学出版社
出版时间：2007
ISBN：9787302151722
开本：16
定价：69.00元
内容简介本书介绍了计算机科学的基础知识，以及各种算法计算的能力和局限性。本书通过大量示例，以一种直观、易懂的方式阐释了计算机科学理论的概念及相关数学知识。第3版还扩展介绍了自动机理论、计算理论和计算复杂性等内容。本书可作为计算机及相关专业的计算机科学理论课程的教材。
目录出版者的话
专家指导委员会
译者序
前言
绪论
第一部分 基础
第1章 数学预备知识
1.1集合论
1.2笛卡儿积、关系和函数
1.3等价关系
1.4可数集合和不可数集合
1.5对角化和自反
1.6递归定义
1.7数学归纳
1.8有向图
1.9练习
参考文献注释
第2章 语言
2.1字符串和语言
2.2语言的有穷规格说明
2.3正则集合和表达式
2.4正则表达式和文本搜索
2.5练习
参考文献注释
第二部分 文法、自动机和语言
第3章 上下文无关文法
3.1上下文无关文法和语言
3.2文法和语言的例子
3.3正则文法
3.4验证文法
3.5最左推导和二义性
3.6上下文无关文法和编程语言定义
3.7练习
参考文献注释
第4章 上下文无关文法范式
4.1文法转换
4.2消去入规则
4.3去掉链规则
4.4无用符
4.5乔姆斯基范式
4.6CYK算法
4.7去掉直接左递归
4.8格立巴赫范式
4.9练习
参考文献注释
第5章 有限自动机
5.1 一个有限状态自动机
5.2 确定型有限自动机
5.3 状态图和例子
5.4 非确定型有限自动机
5.5 λ-转换
5.6 去掉非确定性
5.7 DFA的最小化
5.8 练习
参考文献注释
第6章 正则语言的性质
6.1 有限状态机接收正则语言
6.2 表达式图
6.3 正则文法和有限自动机
6.4 正则语言的封闭性质
6.5 非正则语言
6.6 规则语言的泵引理
6.7 Myhill-Nerode定理
6.8 练习
参考文献注释
第7章 下推自动机和上下文无关语言
7.1 下推自动机
7.2 PDA的变种
7.3 上下文无关语言的接收
7.4 上下文无关语言的泵引理
7.5 上下文无关语言的封闭性
7.6练习
参考文献注释
第三部分 可计算性
第8章 图灵机
8.1标准图灵机
8.2作为语言接收器的图灵机
8.3可供选择接收标准
8.4多道图灵机
8.5双向图灵机
8.6多带图灵机
8.7非确定型图灵机
8.8用来枚举语言的图灵机
8.9练习
参考文献注释
第9章 图灵可计算函数
9.1函数的计算
9.2数值计算
9.3图灵机的顺序操作
9.4函数的合成
9.5不可计算函数
9.6关于编程语言
9.7练习
参考文献注释
第10章 乔姆斯基层次
10.1无限制文法
10.2上下文有关文法
10.3线性有界自动机
10.4乔姆斯基层次
10.5练习
参考文献注释
第11章 判定问题与丘奇—图灵论题
11.1判定问题的描述
11.2判定问题和递归语言
11.3问题归约
11.4丘奇—图灵论题
11.5通用机
11.6练习
参考文献注释
第12章 不可判定性
12.1图灵机的停机问题
12.2问题归约和不可判定性
12.3其他的停机问题
12.4莱斯定理
12.5不可解决的词问题
12.6波斯特对应问题
12.7上下文无关文法中的不可判定问题
12.8练习
参考文献注释
第13章 Mu-递归函数
13.1原始递归函数
13.2一些原始递归函数
13.3有界操作符
13.4除法函数
13.5歌德尔数字和串值递归
13.6可计算部分函数
13.7 图灵可计算函数和Mu-递归函数
13.8修订的丘奇—图灵论题
13.9练习
参考文献注释
第四部分计算复杂性
第14章 时间复杂性
14.1复杂性度量
14.2增长的速度
14.3图灵机的时间复杂性
14.4复杂性和图灵机的变种
14.5线性加速
14.6语言时间复杂性的属性
14.7计算机计算的模拟
14.8练习
参考文献注释
第15章 P、NP和库克定理
15.1 非确定型图灵机的时间复杂性
15.2P类和NP类
15.3问题表示和复杂性
15.4判定问题和复杂性类
15.5哈密尔顿回路问题
15.6多项式时间归约
15.7 P=NP？
15.8 可满足性问题
15.9 复杂类的关系
15.10练习
参考文献注释
第16章 NP-完全问题
16.1归约和NP-完全问题
16.2三元可满足性问题
16.3三元可满足性的归约
16.4归约和子问题
16.5最优化问题
16.6近似算法
16.7近似方案
16.8练习
参考文献注释
第17章 其他复杂性类
17.1 派生的复杂性类
17.2 空间复杂性
17.3 空间复杂性和时间复杂性的关系
17.4 P-空间，NP-空间和萨维奇定理
17.5 P-空间完全性
17.6 一个难解问题
17.7 练习
参考文献注释
第五部分确定型语法分析
第18章语法分析引论
18.1 文法图
18.2自顶向下语法分析
18.3归约和自底向上语法分析
18.4自底向上语法分析器
18.5语法分析和编译
18.6练习
参考文献注释
第19章LL(k)文法
19.1 上下文无关文法中的预读
19.2 FIRST集合、FOLLOW集合和预读集合
19.3 强LL(k)语法
19.4 FIRSTk集合的构造
19.5 FOLLOWk集合的构造
19.6 强LL(1)文法
19.7 强LL(k)分析器
19.8 LL(k)文法
19.9 练习
参考文献注释
第20章 LR(k)文法
20.1 LR(0)上下文
20.2 LR(0)分析器
20.3 LR(0)机
20.4 被LR(0)机接收
20.5 LR(1)文法
20.6 练习
参考文献注释
附录Ⅰ 标记索引
附录Ⅱ 希腊字母表
附录Ⅲ ASC Ⅱ字符集
附录Ⅲ Java的BNF范式定义
参考文献
索引