可计算性与计算复杂性导引

图书标准信息

• 作者 张立昂 著
• 出版社 北京大学出版社
• 出版时间 2004-07
• 版次 2
• ISBN 9787301074633
• 定价 23.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 221页
• 字数 359千字
• 正文语种 简体中文

【内容简介】

《高等院校计算机专业及专业基础课系列教材：可计算性与计算复杂性导引（第2版）》是学习理论计算机科学基础的教材和参考书，内容包括三部分：可计算性、形式语言与自动机、计算复杂性。主要介绍几种计算模型及它们的等价性，函数、谓词和语言的可计算性等基本概念，形式语言及其对应的自动机模型，时间和空间复杂性，NP完全性等。
《高等院校计算机专业及专业基础课系列教材：可计算性与计算复杂性导引（第2版）》可作为计算机专业本科生和研究生的教材，也可作为从事计算机科学技术的研究和开发人员的参考书，还可作为对理论计算机科学感兴趣的读者的入门教材。

【目录】

第一章程序设计语言×和可计算函数
1.1预备知识
1.2Church-Turing论题
1.3程序设计语言×
1.4可计算函数
1.5宏指令
习题

第二章原始递归函数
2.1原始递归函数
2.2原始递归谓词
2.3迭代运算、有界量词和极小化
2.4配对函数和Godel数
2.5原始递归运算
2.6Ackermann函数
2.7字函数的可计算性
习题

第三章通用程序
3.1程序的代码
3.2停机问题
3.3通用程序
3.4递归可枚举集
习题

第四章Turing机
4.1Turing机的基本模型
4.2Turing机的各种形式
4.3Turing机与可计算性
4.4Turing机接受的语言
4.5非确定型Turing机
习题

第五章过程与文法
5.1半Thue过程
5.2用半Thue过程模拟Turing机
5.3文法
5.4再论递归可枚举集
5.5部分递归函数
5.6再论Church-Turing论题
习题

第六章不可判定的问题
6.1判定问题
6.2Turing机的停机问题
6.3字问题和Post对应问题
6.4有关文法的不可判定问题
6.5一阶逻辑中的判定问题
习题

第七章正则语言
7.1Chomsky谱系
7.2有穷自动机
7.3有穷自动机与正则文法的等价性
7.4正则表达式
7.5非正则语言
习题

第八章上下文无关语言
第九章时间复杂性与空间复杂性
第十章NP完全性
第十一章NP类的外面
第十二章P类的里面
第十三章随机算法与随机复杂性类
附录
参考文献