计算理论基础

图书标准信息

• 作者 刘易斯、帕帕蒂米特里奥 著
• 出版社 清华大学出版社
• 出版时间 2006-07
• 版次 1
• ISBN 9787302132882
• 定价 29.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 244页
• 字数 367千字

【内容简介】

　　计算理论是计算机科学的理论基础。《计算理论基础》(第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.1Turing机的定义
4.2用Turing机计算
4.3Turing机的扩充
4.4随机存取Turing机
4.5非确定型Turing机
4.6文法
4.7数值函数
参考文献
第5章不可判定性
5.1Church-Turing论题
5.2通用Turing机
5.3停机问题
5.4与Turing机有关的不可判定问题
5.5与文法有关的不可解问题
5.6不可解的铺砖问题
5.7递归语言的性质
参考文献
第6章计算复杂性
6.1P类
6.2若干问题
6.3布尔可满足性
6.4NP类
参考文献
第7章NP完全性
7.1多项式时间归约
7.2Cook定理
7.3其他的NP完全问题
7.4对付NP完全性
参考文献
中英对照名词索引