可计算性与计算复杂性导引——普通高等教育“九五”教育部重点教材

图书标准信息

• 作者 张立昂 编
• 出版社 北京大学出版社
• 出版时间 1996-10
• 版次 1
• ISBN 9787301032299
• 定价 15.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 299页
• 字数 250千字

【内容简介】

本书是学习理论计算机科学基础的教材和参考书，内容包括三部分：可计算性、形式语言与自动机、计算复杂性。主要介绍几种计算模型及它们的等价性，函数、谓词和语言的可计算性等基本概念，形式语言及其对应的自动机模型，时间和空间复杂性，NP完全性等。

  本书可作为计算机专业本科生和研究生的教材，也可作为从事计算机科学技术的研究和开发人员的参考书，还可作为对理论计算机科学感兴趣的读者的入门教材。

【目录】

第一章  程序设计语言和可计算函数

  1.1 预备知识

  1.2 程序设计语言

  1.3 可计算函数

  1.4 宏指令

  习题

第二章  原始递归函数

  2.1 原始递归函数

  2.2 原始递归谓词

  2.3 迭代运算、有界量词和极小化

  2.4 配对函数和Godel数

  2.5 原始递归运算

  2.6 Ackermann函数

  习题

第三章  通用程序

  3.1 程序的代码

  3.2 停机问题

  3.3 通用程序

  3.4 参数定理

  3.5 递归定理

  习题

第四章  字符串计算

  4.1 字符串的数字表示

  4.2 程序设计语言

  4.3 Post-Turing语言

  4.4 用模拟

  4.5 用模拟

  习题

第五章  递归可枚举集

  5.1 递归集和递归可枚举集

  5.2 递归语言和递归枚举语言

  5.3 非递归集和非递归可枚举集

  习题

第六章  Turing机

  6.1 Turing机的基本模型

  6.2 Turing机与可计算性

  6.3 Turing机接受的语言

  6.4 Turing机的各种形式

  6.5 非确定型Turing机

  习题

第七章  过程与文法

  7.1 半Thue过程

  7.2 用半Thue过程模拟Turing机

  7.3 文法

  7.4 再论递归可枚举集

  7.5 部分递归函数

  7.6 Church-Turing论题

  习题

第八章  不可判定的问题

  8.1 判定问题

  8.2 Turing机的停机问题

  8.3 字问题和Post对应问题

  8.4 有关文法的不可判定问题

  8.5 一阶逻辑中的判定问题

  习题

第九章  正则语言

第十章  上下文无关语言

第十一章  上下文有关语言

第十二章  计算复杂性

第十三章  NP完全性

第十四章  组合优化问题的近似计算

附录

参考文献