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

章节摘录

插图：

前言

计算机科学技术日新月异，新东西层出不穷、旧东西迅速被淘汰。但是，作为一门科学，它有其自身的基础理论。这些思想精华长久地、甚至永恒地放射着光芒。这些理论在应用开发中好像是"无用的"，但实际上，对于每一位从事计算机科学技术的研究和开发的人来说，它们都是不可缺少的，就像能量守恒之类的物理定律对于每一位自然科学工作者和工程技术人员那样。北京大学计算机科学技术系开设了"理论计算机科学基础"这门课，就是希望能把这样一些最基本的知识介绍给学生。本书是在这门课的讲稿的基础上加工而成的。    本书的内容包括三部分：可计算性、形式语言与自动机、计算复杂性。这三个领域（更不用说整个理论计算机科学）的内容极其丰富并且在不断地发展。作为本科生一个学期的课程只能选择其中最基本的部分，使学生在这些方面有一个大的理论框架。本书主要取材于参考文献[1]～[4]。书中部分章节涉及到数理逻辑和图论中的一些问题，不熟悉这些内容的读者可查阅参考文献[6]、[7]。书末附有中英文名词索引和记号，并给出定义这些名词和记号的章节。    本书的出版得到北京大学出版社的热情支持，笔者在此表示衷心的感谢。在本书的出版和写作过程中得到董士海教授、袁崇义教授、王捍贫博士和黄雄的各种形式的帮助，对他们表示感谢。最后，笔者要特别感谢许卓群教授，作为主管教学工作的系领导，许卓群教授从这门课的开设到本书的出版给予了一贯的积极支持和指导。    张立昂    1996年春于北大燕北园

书籍目录

第一章 程序设计语言×和可计算函数  1.1 预备知识   1.2 Church-Turing论题  1.3 程序设计语言×  1.4 可计算函数  1.5 宏指令   习题第二章 原始递归函数  2.1 原始递归函数  2.2 原始递归谓词  2.3 迭代运算、有界量词和极小化  2.4 配对函数和Godel数  2.5 原始递归运算  2.6 Ackermann函数  2.7 字函数的可计算性  习题第三章 通用程序   3.1 程序的代码  3.2 停机问题  3.3 通用程序  3.4 递归可枚举集  习题第四章 Turing 机  4.1 Turing 机的基本模型  4.2 Turing 机的各种形式  4.3 Turing 机与可计算性  4.4 Turing 机接受的语言  4.5 非确定型Turing 机  习题第五章 过程与文法  5.1 半Thue过程   5.2 用半Thue过程模拟Turing 机  5.3 文法  5.4 再论递归可枚举集  5.5 部分递归函数  5.6 再论Church-Turing论题  习题第六章 不可判定的问题  6.1 判定问题  6.2 Turing 机的停机问题  6.3 字问题和Post对应问题  6.4 有关文法的不可判定问题  6.5 一阶逻辑中的判定问题  习题第七章 正则语言  7.1 Chomsky谱系  7.2 有穷自动机  7.3 有穷自动机与正则文法的等价性  7.4 正则表达式  7.5 非正则语言   习题第八章 上下文无关语言第九章 时间复杂性与空间复杂性第十章 NP完全性第十一章 NP类的外面 第十二章 P类的里面第十三章 随机算法与随机复杂性类附录参考文献

作者简介

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

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

图书封面

---

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

---