计算机科学的数学基础
2007-9
湘潭大学出版社
周经野，刘任任 著
343
无
形式语言与自动机理论、可计算理论、逻辑学和程序设计理论，都是研究计算模型的。它们之间也是相互关联的，共同构成了现代计算机科学技术的理论基础。这些理论都是属于数学学科的。形式语言与自动机理论、可计算理论和逻辑学的研究都始于20世纪初叶，特别是20世纪30年代的数学家church（邱奇）、G甜el（哥德尔）、Ⅺeene（克林）、P0st（波斯特）以及Turing（图灵）等人的杰出工作催生了现代电子数字计算机的硬件和软件的诞生。程序设计理论的研究相比则要迟一些，是20世纪后半叶现代电子数字计算机以‘。及程序设计语言和软件诞生之后的事情了。它是专门研究程序设计语言和程序设计方法的数学理论。这些工作对于计算机科学的实践和理论的发展有着深远的影响。比如，图灵机模型就被证明是现代电子数字计算机的理论模型。这些先驱者的工作在今天看来似乎是很平常的，它们的思想渊源甚至并不为今天众多的计算机的使用者所知道。但是这些先驱者的工作确实是应该被那些从事计算机科学技术的工作者们所熟悉、所掌握的。因为这些思想和方法将对他们的工作产生很重要的启示和指导作用。正是因为这一点，形式语言与自动机理论、可计算理论、逻辑学和程序设计理论一直以来都是国内外计算机科学技术专业硕士研究生的课程，而且还是作为重要的课程来开设的。 然而，20多年来计算机科学技术已经发生了翻天覆地的变化，它作为一门年轻的学一科已经增长到了几乎无法想象的程度，而同时计算机的应用也已经到了无所不在的地步。在这种情形下，人们都感到有必要对原有的课程设置作一番调整。尽管在计算机科学技术领域越来越追求实用化，但是我们仍然执著地认为系统地了解和掌握计算机科学的数学理论对于从事计算机科学技术的工作者是重要的。本着“厚基础、宽口径、重能力”的精神，我们在计算机科学技术硕士研究生的教学计划的调整中将这几门课程合并为一门课程，取名为《计算机科学的数学基础》，并把它作为计算机科学技术一级学科的硕士研究生的必修课程。通过这几年的教学实践，我们感到这个调整是成功的。但是一直苦于在国内外找不到一本与之相适应的统一的教材，这样就萌发了编写这样一本教材的想法。我们的想法立刻得到了湘潭大学出版社的支持。
《计算机科学的数学基础》共分形式语言与自动机理论，可计算理论，逻辑学，程序设计理论等四个部分。内容包括：语言与正规语言；有限自动机；短语结构语言与上下文有关语言；可计算理论；模糊逻辑等。《计算机科学的数学基础》内容丰富，讲解通俗易懂，具有很强的可读性。 形式语言与自动机理论、可计算理论、逻辑学和程序设计理论，都是研究计算模型的。它们之间也是相互关联的，共同构成了现代计算机科学技术的理论基础。这些理论都是属于数学学科的。形式语言与自动机理论、可计算理论和逻辑学的研究都始于20世纪初叶，特别是20世纪30年代的数学家Church（邱奇）、GMel（哥德尔）、Kleene（克林）、Post（波斯特）以及Turing（图灵）等人的杰出工作催生了现代电子数字计算机的硬件和软件的诞生。程序设计理论的研究相比则要迟一些，是20世纪后半叶现代电子数字计算机以及程序设计语言和软件诞生之后的事情了。它是专门研究程序设计语言和程序设计方法的数学理论。这些工作对于计算机科学的实践和理论的发展有着深远的影响。比如，图灵机模型就被证明是现代电子数字计算机的理论模型。这些先驱者的工作在今天看来似乎是很平常的，它们的思想渊源甚至并不为今天众多的计算机的使用者所知道。但是这些先驱者的工作确实是应该被那些从事计算机科学技术的工作者们所熟悉、所掌握的。因为这些思想和方法将对他们的工作产生很重要的启示和指导作用。正是因为这一点，形式语言与自动机理论、可计算理论、逻辑学和程序设计理论一直以来都是国内外计算机科学技术专业硕士研究生的课程，而且还是作为重要的课程来开设的。
第一部分 形式语言与自动机理论第一章 语言与正规语言1.1 符号、符号串及其运算1.2 文法与语言的形式定义1.3 正规表达式1.4 正规文法与正规式第二章 有限自动机2.1 有限自动机的定义与构造2.2 确定的有限自动机（DFA）2.3 不确定的有限自动机（NFA）2.4 NFA的确定化2.5 DFA的最小化2.6 正规集与有限自动机的等价性2.7 双向有限自动机2.8 具有输出的有限自动机第三章 正规集的性质3.1 正规集的泵作用引理3.2 正规集的封闭性质3.3 正规集的一些判定算法第四章 上下文无关语言4.1 上下文无关文法4.2 上下文无关文法的简化4.3 Chomsky范式4.4 Greibach范式4.5 先天歧义的上下文无关语言的存在第五章 下推自动机5.1 非形式的描述5.2 下推自动机的定义5.3 下推自动机和上下文无关语言第六章 上下文无关语言的性质6.1 对CFL的泵作用引理6.2 上下文无关语言的封闭性质6.3 CFL的某些判定算法第二部分 可计算理论第七章 图灵机7.1 图灵机模型7.2 可计算语言和函数7.3 图灵机的构造技术7.4 图灵机的修改7.5 Church假设7.6 图灵机作为枚举器7.7 等价于基本模型的受限图灵机第八章 短语结构语言与上下文有关语言8.1 短语结构语言与图灵机8.2 上下文有关语言与线性有界自动机8.3 上下文无关语言与递归集合8.4 上下文有关语言类的性质第九章 可判定性9.1 递归语言和递归可枚举语言的性质9.2 通用图灵机和一个不可判定问题9.3 RICE定理和某些其他的不可判定问题9.4 POST对应问题的不可判定性9.5 图灵机的有效计算和无效计算9.6 Greibach定理9.7 圣人计算第十章 可计算理论10.1 原始递归函数10.2 递归函数与部分递归函数10.3 图灵机与部分递归函数的等价性第三部分 逻辑学第十一章 命题逻辑与一阶逻辑11.1 命题逻辑的自然推理11.2 命题演算的公理系统11.3 PC的可靠性与一致性11.4 PC的完备性11.5 一阶逻辑第十二章 直觉主义逻辑12.1 直觉主义的一些基本观点12.2 一阶直觉主义逻辑的形式化12.3 完全性定理第十三章 模态逻辑13.1 模态词“必然”与“可能”13.2 模态命题逻辑系统13.3 模态狭义谓词逻辑第十四章 非单调逻辑14.1 单调性与非单调性14.2 非单调逻辑14.3 缺省推理14.4 非单调逻辑系统14.5 限定理论第十五章 模糊逻辑15.1 逻辑与不确定性的研究15.2 模糊集15.3 模糊逻辑的代数模型——De-Morgan代数15.4 模糊变量与模糊逻辑公式（函数）15.5 模糊逻辑真值表与范式15.6 模糊逻辑公式的极小化15.7 似然推理15.8 模糊归纳推理第十六章 多值逻辑16.1 三值逻辑16.2 多值命题逻辑16.3 三值逻辑代数系统16.4 n值逻辑代数系统16.5 阈值逻辑第四部分 程序设计理论第十七章 程序的指称语义17.1 把程序看作函数17.2 序列程序结构的程序函数17.3 分支程序结构的程序函数17.4 循环程序结构的程序函数17.5 循环程序的正确性证明第十八章 程序的公理语义18.1 程序的公理语义18.2 霍尔公理系统18.3 最弱前置谓词与程序的公理语义第十九章 程序的形式推导19.1 程序形式推导的基本思想19.2 选择语句的设计19.3 循环程序的设计19.4 不变式与界函数的构造第二十章 递归程序理论20.1 递归的基本概念20.2 递归数据结构20.3 递归程序的证明习题参考文献
无