计算理论导引
分类: 图书,计算机/网络,计算机理论,
作者： （美）西普塞著
出 版 社： 机械工业出版社
出版时间： 2000-2-1字数：版次： 1页数： 250印刷时间：开本：印次：纸张：I S B N ： 9787111075745包装： 平装编辑推荐
本书由计算理论领域的知名权威Michael Sipser撰写。他以独特的视角，综合地描述了计算机科学理论，并以清新的笔触、生动的语言给出了宽泛的数学理论，而并非拘泥于某些低层次的技术细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。同样，对于算法描述，均以直观的文字，而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。本书的内容包括三个部分：自动机与语言、可计算性理论和计算复杂性理论。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。
内容简介
本书由计算理论领域的知名权威Michael Sipser撰写。他以独特的视角，综合地描述了计算机科学理论，并以清新的笔触、生动的语言给出了宽泛的数学理论，而并非拘泥于某些低层次的技术细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。同样，对于算法描述，均以直观的文字，而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。本书的内容包括三个部分：自动机与语言、可计算性理论和计算复杂性理论。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。
作者简介
译者介绍
张立昂，1941年2月出生，1965年毕业于北京大学数学力学系数学专业。现为北京大学计算机科学与技术系教授、博士生导师。主要研究方向：算法设计与分析、计算复杂性理论。著有《可计算性与计算复杂性导引》等。
王捍贫，1964年7月出生，1993年毕业于北京师范大学数学系数理逻辑专业，获博士学位。现为北京大学计算机科学与技术系副教授。主要研究方向为数理逻辑、计算复杂性、程序语义及正确性验证技术。著作有《数理逻辑》等。
黄雄，1969年8月出生，北京大学计算机科学硕士，北京航空航天大学计算机科学博士。现在中国科学院计算所做博士后。研究领域包括：算未能设计与分析、计算复杂性Web信息检索。
目录
第1章 导引
第一部分 自动机与语言
第2章 正则语言
第3章 上下文无关语言
第二部分 可计算性理论
第4章 丘奇—图灵论题
第5章 可判定性
第6章 可归约性
第7章 可计算性理论的高级专题
第三部分 复杂性理论
第8章 时间复杂性
第9章 空间复杂性
第10章 难解性
第11章 复杂性理论中的高级专题
