第1章 基础知识

计算机科学与技术学科强调4个方面的专业能力：计算思维能力，算法设计与分析能力，程序设计与实现能力，计算机系统的认知、分析、设计和运用能力。这也是计算机科学与技术学科同其他学科的重要区别。相关的理论是计算机科学与技术学科的基础。理论方面的知识是计算机的真正灵魂。理论是从计算机应用中抽象出来的，目的在于使用抽象出来的理论去更好地指导实践。

在本科阶段的学习过程中，学生以观察、描述、比较、分类、推断、应用、创造性思维等科学思维过程为主，强调自学的能力在于培养；研究生阶段，需要对学生进一步进行抽象思维、逻辑思维、创造性思维能力的培养。本科生与研究生的根本区别，在于研究生需要宽厚、坚实的理论基础。

建立物理符号系统并对其实施等价变换，是计算机科学与技术学科进行问题描述和求解的重要手段。“可行性”所要求的“形式化”及其“离散特征”使得数学成为重要的工具，而计算模型无论是从方法还是从工具等方面，都表现出它在计算机科学中的重要作用。

计算机科学与技术学科要求具有形式化描述和抽象思维能力，要求掌握逻辑思维方法。这种能力就是计算思维能力或计算机思维能力[1]。

计算机科学与技术学科系统地研究信息描述和变换算法，重点包括信息描述和变换算法的理论、分析、效率、实现与运用。学科的根本问题在于：什么能被（有效地）自动化？学科的重要内容之一是研究计算领域中的一些普遍规律，描述算法的基本概念与模型。

计算思维能力的培养主要是通过基础理论系列课程实现的，该系列由数学和抽象度较高的理论课程组成，包括数学分析、集合和图论、近世代数、数学建模、计算理论等。它们构成了对学生计算思维能力培养的一个阶梯训练系统，如图1.1所示^^chapter2.xhtml-[1]$$[1]。

在计算思维阶梯训练系统中，连续数学、离散数学、计算模型3部分内容按阶段分开。3个阶段对应于计算机学科的学生在本科和研究生学习期间的思维方式和能力变化的3个步骤，使得学生的计算思维能力不断提高。

在中学阶段所学的数学，研究的是具体的、静止对象的计算。到了数学分析阶段，通过连续变量和函数，将运动带入了问题考虑的范围中，到离散数学和近世代数阶段，开始考虑基本运算系统，该系统更加抽象，更具一般性，所考虑的计算对象具有更明显的抽象和离散的特征。到形式语言与自动机理论阶段，所考虑的运算对象是更高级别上抽象出来的形式化特征，而运算也呈现出模型化的特征。计算从孤立的、单一的计算演变为一般、形式化的计算，而一般、形式化的计算，正是计算机科学所要研究的计算。

考虑的计算对象不同，所需要的思维方式和能力就有所不同，正是通过系列课程的学习，在不断升华的过程中，逐步培养出学生的抽象思维能力和逻辑思维方法，同时，创新意识的建立和创新能力的培养也在学习过程中不断进行。

计算理论是研究使用计算机解决计算问题的数学理论。它有 3 个核心领域：形式语言与自动机理论、可计算性理论和计算的复杂性理论。可计算性理论的中心问题是，建立计算的数学模型，进而研究哪些是可计算的，哪些是不可计算的。计算的复杂性理论研究算法的时间复杂性和空间复杂性。在可计算性理论中，将问题分成可计算的和不可计算的；在复杂性理论中，目标是把可计算的问题分成简单的和困难的。

形式语言与自动机理论论述计算的数学模型的定义与性质，这些模型在计算机科学的若干应用领域中起着重要作用，其应用范围已被扩展到生物工程、自动控制系统、图像处理与模式识别等许多领域。

形式语言与自动机理论是学习计算理论的良好起点，不仅能提高感知能力，同时也能提高思维的敏捷性，使得考虑问题仔细、严谨、周密、有理有据；由具体形象思维逐渐向抽象思维过渡，从而促进逻辑思维和创造力的发展；使得逻辑思维过程清晰化、条理化、整体化，有利于培养计算表达能力，提高推理、判断、分析问题和解决问题的能力。

计算理论并不神秘，也不令人厌烦，而是容易理解的，甚至是有趣的。计算理论中包括许多迷人而重要的思想，要体会并感悟思想的闪光，并且体会大师们当初发现这些思想而获得的极大乐趣。

计算机学科的方法论有 3 个过程：抽象、理论和设计及实现。最根本的问题是：问题如何进行描述？哪些部分能够被自动化？如何进行自动化描述？

问题的计算机求解建立在高度抽象的基础上，问题的符号表示及处理过程的机械化、严格化等固有特性决定了数学是计算机科学与技术学科的重要基础之一。数学及其形式化描述以及严密的表达和计算，是计算机科学与技术学科的重要工具。建立物理符号系统并对其实施变换，是计算机科学与技术学科进行问题描述和求解的重要手段。学科所要求的计算机问题求解的“可行性”限定了从问题抽象开始到根据适当理论的指导进行实现的科学世界过程。

形式语言与自动机理论包括 3 方面的内容：形式语言理论、自动机理论和形式语言与自动机等价性理论。本书主要讨论自动机理论和形式语言与自动机等价性理论。

本书内容属于理论计算机科学的理论范畴，所需的数学基础知识较多。本章对形式语言和有限自动机理论中所需的数学基础知识做扼要的介绍，内容包括集合及其运算、关系、证明和证明的方法以及图与树的概念；对形式语言和自动机理论中的基本知识做简要介绍。