计算科学它的意义

1、第三章第三章 计算科学：它的意义、内容和方法计算科学：它的意义、内容和方法 先介绍三个基本术语，它们是先介绍三个基本术语，它们是科学科学、技术技术和和工程工程。 科学科学是关于自然、社会和思维的发展与变化规律的是关于自然、社会和思维的发展与变化规律的知识体系。知识体系。技术技术是泛指根据生产实践经验和科学原理而是泛指根据生产实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧。发展形成的各种工艺操作方法、技能和技巧。工程工程是指是指将科学原理应用到工农业生产部门中去而形成的各门学将科学原理应用到工农业生产部门中去而形成的各门学科的总称。科的总称。3.1 3.1 什么是计算科学？什么是计算

2、科学？ 计算科学是对描述和变换信息的算法过程，包括其计算科学是对描述和变换信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用的系统的研理论、分析、设计、效率分析、实现和应用的系统的研究。全部计算科学的基本问题是，什么能（有效地）自究。全部计算科学的基本问题是，什么能（有效地）自动进行，什么不能（有效地）自动进行。本学科来源于动进行，什么不能（有效地）自动进行。本学科来源于对数理逻辑、计算模型、算法理论、自动计算机器的研对数理逻辑、计算模型、算法理论、自动计算机器的研究，形成于本世纪究，形成于本世纪3030年代后期。现在，年代后期。现在，计算计算已成为继已成为继理论理论、实验实验之后的

3、第三种科学形态。之后的第三种科学形态。3.2 3.2 学科的基本问题学科的基本问题 一个学科如果没有问题需要解决，这个学科的生命就一个学科如果没有问题需要解决，这个学科的生命就结束了。每一个学科在发展的不同时期，都存在一些结束了。每一个学科在发展的不同时期，都存在一些基本基本问题问题和和重大问题重大问题，它们的解决推动了学科持续的发展。那，它们的解决推动了学科持续的发展。那么，哪些是计算科学学科发展的重大问题和基本问题呢？么，哪些是计算科学学科发展的重大问题和基本问题呢？ 重大问题重大问题是比较容易理解的，而且，相对于不同时期，是比较容易理解的，而且，相对于不同时期，重大问题既是相对的，也是比

4、较多的。例如，学科发展早重大问题既是相对的，也是比较多的。例如，学科发展早期提出的什么是期提出的什么是可计算与不可计算的概念可计算与不可计算的概念，5050年代末年代末6060年年代初提出的代初提出的高级程序设计语言的形式化描述问题高级程序设计语言的形式化描述问题，6060年代年代末末7070年代初提出的年代初提出的操作系统中的并发控制问题操作系统中的并发控制问题，等等。然，等等。然而，在学科经历了几十年的发展后，当我们今天以科学哲而，在学科经历了几十年的发展后，当我们今天以科学哲学的观点回顾历史的进程，系统总结学科的内容时，可以学的观点回顾历史的进程，系统总结学科的内容时，可以发现：如同数学

5、等一些基础学科一样，在学科各个分支学发现：如同数学等一些基础学科一样，在学科各个分支学科方向的发展进程中，不断地出现了一些在表现形式上虽科方向的发展进程中，不断地出现了一些在表现形式上虽然不同，但在科学哲学的解释下本质上是相同或相近的问然不同，但在科学哲学的解释下本质上是相同或相近的问题，即学科研究与发展普遍关心的题，即学科研究与发展普遍关心的基本问题基本问题。这些基本问。这些基本问题主要有如下三个：题主要有如下三个： 计算的平台与环境问题计算的平台与环境问题 计算过程的能行操作与效率问题计算过程的能行操作与效率问题 计算的正确性问题计算的正确性问题 在学科发展的历程中，不断地追求制造出各种新

6、型计在学科发展的历程中，不断地追求制造出各种新型计算机系统，拓展和提高计算机的应用领域和应用水平这样算机系统，拓展和提高计算机的应用领域和应用水平这样两个目标，围绕学科的三个基本问题使学科的发展形成了两个目标，围绕学科的三个基本问题使学科的发展形成了三条相对独立的主线，形成了许多相对独立的分支学科和三条相对独立的主线，形成了许多相对独立的分支学科和研究方向。同时，我们也注意到，在学科的发展过程中，研究方向。同时，我们也注意到，在学科的发展过程中，不同时期，围绕着学科的一些重大问题和基本问题，若干不同时期，围绕着学科的一些重大问题和基本问题，若干方向便构成了所谓的主流方向，由主流方向又形成了学科

7、方向便构成了所谓的主流方向，由主流方向又形成了学科的发展主线。的发展主线。 计算的平台与环境问题是不难理解的。历史上，为了计算的平台与环境问题是不难理解的。历史上，为了实现自动计算，人们首先想到了要发明和制造自动计算机实现自动计算，人们首先想到了要发明和制造自动计算机器，不仅要从理论上提供计算的平台器，不仅要从理论上提供计算的平台观察和描述计算观察和描述计算的的起点，或者证明问题本身不可解，而且要实际制造出针对起点，或者证明问题本身不可解，而且要实际制造出针对各种待处理问题特点和要求的自动计算机器。进一步，从各种待处理问题特点和要求的自动计算机器。进一步，从广义的计算的概念出发，计算的平台在使

8、用上还必须比较广义的计算的概念出发，计算的平台在使用上还必须比较方便，于是派生出计算环境的概念。据此，不难看出，理方便，于是派生出计算环境的概念。据此，不难看出，理论研究中提出的各种计算模型，各种实际的计算机系统，论研究中提出的各种计算模型，各种实际的计算机系统，各种高级程序设计语言，各种计算机体系结构，各种软件各种高级程序设计语言，各种计算机体系结构，各种软件开发工具与环境，编译程序与操作系统，数据库系统等都开发工具与环境，编译程序与操作系统，数据库系统等都是围绕这一基本问题发展而来的，其内容实质可归结为计是围绕这一基本问题发展而来的，其内容实质可归结为计算的模型问题，也就是说，这个基本问题

9、实际上关心的是算的模型问题，也就是说，这个基本问题实际上关心的是计算问题在理论上是否能行的问题。当然，这里所说的计计算问题在理论上是否能行的问题。当然，这里所说的计算模型是广义的。算模型是广义的。 计算过程的能行操作与效率问题也是学科的基本问题计算过程的能行操作与效率问题也是学科的基本问题之一。一个问题在判明为可计算的性质后，从具体解决这之一。一个问题在判明为可计算的性质后，从具体解决这个问题着眼，必须按照能行可构造的特点与要求，给出实个问题着眼，必须按照能行可构造的特点与要求，给出实际解决该问题的一步一步的具体操作，同时还必须确保这际解决该问题的一步一步的具体操作，同时还必须确保这样一种过程

10、的开销成本是我们能够承受的。围绕这一问题，样一种过程的开销成本是我们能够承受的。围绕这一问题，学科发展了大量与之相关的研究内容与分支学科方向。例学科发展了大量与之相关的研究内容与分支学科方向。例如，数值与非数值计算方法，算法设计与分析，结构化程如，数值与非数值计算方法，算法设计与分析，结构化程序设计技术与效率分析，以计算机部件为背景的集成电路序设计技术与效率分析，以计算机部件为背景的集成电路技术，密码学与快速算法，演化计算，数字系统逻辑设计，技术，密码学与快速算法，演化计算，数字系统逻辑设计，程序设计方法学（程序推导与程序变换技术），自动布线，程序设计方法学（程序推导与程序变换技术），自动布线

11、，RISCRISC技术，人工智能的逻辑基础等分支学科的内容都是围技术，人工智能的逻辑基础等分支学科的内容都是围绕这一基本问题展开、发展而形成的。显然，计算操作的绕这一基本问题展开、发展而形成的。显然，计算操作的能行与效率问题也涉及到了计算模型的问题，但是，这里能行与效率问题也涉及到了计算模型的问题，但是，这里所说的计算模型既包括类似于具有状态转换特征的那一类所说的计算模型既包括类似于具有状态转换特征的那一类计算模型，也包括数学建摸这类计算模型。不难看出，这计算模型，也包括数学建摸这类计算模型。不难看出，这一基本问题的核心是算法问题。这也辅助说明了在计算科一基本问题的核心是算法问题。这也辅助说明

12、了在计算科学发展的早期，当计算的平台与环境、计算的正确性问题尚学发展的早期，当计算的平台与环境、计算的正确性问题尚不突出时，为什么学术界将本学科看成是算法的学问。不突出时，为什么学术界将本学科看成是算法的学问。 计算的正确性是任何计算工作都不能回避的问题，特别计算的正确性是任何计算工作都不能回避的问题，特别是使用自动计算机器进行的各种计算。一个计算问题在给出是使用自动计算机器进行的各种计算。一个计算问题在给出了能行操作序列并解决了其效率问题之后，必须确保计算的了能行操作序列并解决了其效率问题之后，必须确保计算的正确性，否则，计算是无意义的，也是容易产生不利影响的。正确性，否则，计算是无意义的，

13、也是容易产生不利影响的。围绕这一基本问题，长期以来，学科发展了一些相关的分支围绕这一基本问题，长期以来，学科发展了一些相关的分支学科与研究方向，例如，算法理论（数值与非数值算法设计学科与研究方向，例如，算法理论（数值与非数值算法设计的理论基础），程序理论（程序设计方法学），程序设计语的理论基础），程序理论（程序设计方法学），程序设计语言的语义学，进程代数与分布式事件代数，程序测试技术，言的语义学，进程代数与分布式事件代数，程序测试技术，电路测试技术，软件工程技术（形式化的软件开发方法学），电路测试技术，软件工程技术（形式化的软件开发方法学），计算语言学，容错理论与技术，计算语言学，容错理论与技

14、术，PetriPetri网理论，网理论，CSPCSP理论，理论，CCSCCS理论，分布式网络协议等都是针对为解决这一基本问题而发理论，分布式网络协议等都是针对为解决这一基本问题而发展形成的。今天，计算的正确性问题常常归结为各种语言的展形成的。今天，计算的正确性问题常常归结为各种语言的语义问题，这也从一个侧面提示了计算的正确性问题可以语义问题，这也从一个侧面提示了计算的正确性问题可以归结为语义学问题，揭示了语义学在整个学科中的重要地位。归结为语义学问题，揭示了语义学在整个学科中的重要地位。 上述基本问题普遍出现在学科的各个分支学科和研究方上述基本问题普遍出现在学科的各个分支学科和研究方向之中，是

15、学科研究与发展中经常面对而又必须解决的问题。向之中，是学科研究与发展中经常面对而又必须解决的问题。 循着这一线索，我们不难看出，整个学科正是在围绕这循着这一线索，我们不难看出，整个学科正是在围绕这些基本问题和不同时期重大问题而展开的研究与发展中形成些基本问题和不同时期重大问题而展开的研究与发展中形成了学科的发展主线与主流方向。了学科的发展主线与主流方向。3.3 3.3 计算科学发展主线计算科学发展主线 从科学哲学的角度，将计算科学的学科内容按照基础理从科学哲学的角度，将计算科学的学科内容按照基础理论、基本开发技术、应用以及它们与硬件设备联系的紧密程论、基本开发技术、应用以及它们与硬件设备联系的

16、紧密程度可分成度可分成三个层面三个层面。 第一层面是计算科学的应用层，它包括人工智能应用与第一层面是计算科学的应用层，它包括人工智能应用与系统，信息、管理与决策系统，移动计算、计算可视化、科系统，信息、管理与决策系统，移动计算、计算可视化、科学计算等计算机应用的各个方向。其中，人工智能应用与系学计算等计算机应用的各个方向。其中，人工智能应用与系统涵盖人工智能，机器人，神经元计算，知识工程，自然语统涵盖人工智能，机器人，神经元计算，知识工程，自然语言处理与机器翻译，自动推理等方向；信息、管理与决策系言处理与机器翻译，自动推理等方向；信息、管理与决策系统涵盖数据库设计与数据管理技术，数据表示与存储

17、（包括统涵盖数据库设计与数据管理技术，数据表示与存储（包括多媒体技术），数据与信息检索，管理信息系统，计算机辅多媒体技术），数据与信息检索，管理信息系统，计算机辅助系统，决策系统等方向；计算可视化涵盖计算机图形学，助系统，决策系统等方向；计算可视化涵盖计算机图形学，计算几何，模式识别与图像处理等方向；计算几何，模式识别与图像处理等方向； 第二层面是计算科学的专业基础层，它是为应用层提供第二层面是计算科学的专业基础层，它是为应用层提供技术和环境的一个层面，包括软件开发方法学，计算机网络技术和环境的一个层面，包括软件开发方法学，计算机网络与通信技术，程序设计科学，计算机体系结构，电子计算机与通信技

18、术，程序设计科学，计算机体系结构，电子计算机系统基础。其中，软件开发方法学涵盖顺序、并行与分布式系统基础。其中，软件开发方法学涵盖顺序、并行与分布式软件开发方法学，如软件工程技术，软件开发工具和环境等软件开发方法学，如软件工程技术，软件开发工具和环境等方向；计算机网络与通信技术涵盖计算机网络互联技术，数方向；计算机网络与通信技术涵盖计算机网络互联技术，数据通信技术，以及信息保密与安全技术等方向；程序设计科据通信技术，以及信息保密与安全技术等方向；程序设计科学涵盖数据结构技术，数值与符号计算，算法设计与分析学涵盖数据结构技术，数值与符号计算，算法设计与分析（包括并行与分布式算法设计与分析），程序

19、设计语言，程（包括并行与分布式算法设计与分析），程序设计语言，程序设计语言的文法与语义（指程序设计语言的文法与语义描序设计语言的文法与语义（指程序设计语言的文法与语义描述），程序设计方法学，程序理论等方向；电子计算机系述），程序设计方法学，程序理论等方向；电子计算机系统基础涵盖数字逻辑技术，计算机组成原理，故障诊断与统基础涵盖数字逻辑技术，计算机组成原理，故障诊断与器件测试技术，操作系统，编译技术，数据库系统实现技器件测试技术，操作系统，编译技术，数据库系统实现技术，容错技术等方向；术，容错技术等方向； 第三层面是计算科学的基础层，它包括计算的数学理第三层面是计算科学的基础层，它包括计算的数学

20、理论，高等逻辑等内容。其中，计算的数学理论涵盖可计算论，高等逻辑等内容。其中，计算的数学理论涵盖可计算性（递归论）与计算复杂性理论，形式语言与自动机理论，性（递归论）与计算复杂性理论，形式语言与自动机理论，形式语义学（主要指代数语义，公理语义等），形式语义学（主要指代数语义，公理语义等），PetriPetri网理网理论等方向；高等逻辑涵盖模型论，各种非经典逻辑与公理论等方向；高等逻辑涵盖模型论，各种非经典逻辑与公理集合论等方向。集合论等方向。 支撑这三个层面的是计算科学这一学科的理工科基础支撑这三个层面的是计算科学这一学科的理工科基础科目，包括物理学（主要是电子技术科学）、基础数学科目，包括物

21、理学（主要是电子技术科学）、基础数学（含离散数学）等。（含离散数学）等。 详细可参见图。详细可参见图。 移动计算与全球定位移动计算与全球定位 计算机自动控制计算机自动控制 计算机辅助制造计算机辅助制造 计算机集成制造系统计算机集成制造系统 计算计算 机器人机器人 计算可视化与虚拟现实计算可视化与虚拟现实 数据与信息检索数据与信息检索 计算机创作计算机创作 计算机网络应用软件计算机网络应用软件 科学科学 科学计算科学计算 多媒体信息系统多媒体信息系统 计算机辅助设计计算机辅助设计 信息、管理与决策系统信息、管理与决策系统 自然语言处理自然语言处理 应用应用 模式识别与图像处理技术模式识别与图像处

22、理技术 计算机图形学计算机图形学 计算几何计算几何 人工智能与知识工程人工智能与知识工程 层层 数据表示与存储数据表示与存储 网络与开放系统互联标准网络与开放系统互联标准 软件测试技术软件测试技术 人机工程学（人机界面）人机工程学（人机界面） 计算计算 软件开发方法学软件开发方法学: : 软件工程技术、程序设计方法学、软件开发工具和环境、软件开发规范软件工程技术、程序设计方法学、软件开发工具和环境、软件开发规范 科学科学 编码理论编码理论 密码学密码学 计算机体系结构计算机体系结构 程序理论程序理论 数据表示理论与数据库系统数据表示理论与数据库系统 专业专业 电子计算机系统基础电子计算机系统基

23、础 计算机接口与通信计算机接口与通信 计算机网络与数据通信技术计算机网络与数据通信技术 自动推理自动推理 基础基础 故障诊断与器件测试技术故障诊断与器件测试技术 容错技术容错技术 汇编技术汇编技术 操作系统操作系统 高级语言高级语言 程序设计程序设计 层层 数字系统设计数字系统设计 符号计算与计算机代数符号计算与计算机代数 数据结构技术数据结构技术 算法设计与分析算法设计与分析 编译与解释技术编译与解释技术 计算计算 控制论基础控制论基础 数字系统设计基础数字系统设计基础 信息论基础信息论基础 网论（网论（PetriPetri网理论等）网理论等） 形式语义学形式语义学 科学科学 框图理论框图理

24、论 算法理论算法理论 可计算性（递归论）可计算性（递归论） 计算复杂性计算复杂性 程序设计语言理论程序设计语言理论 基础基础 计算模型（各种抽象机）计算模型（各种抽象机） 模型论与非经典逻辑模型论与非经典逻辑 公理集合论公理集合论 形式语言与自动机形式语言与自动机 层层 数学数学 光电子技术基础光电子技术基础 电路基础电路基础 电子线路基础电子线路基础 数字与模拟电路基础数字与模拟电路基础 数值分析与计算方法数值分析与计算方法 与与 大学物理学大学物理学 函数论基础（复变函数、函数论基础（复变函数、演算、泛函分析等）演算、泛函分析等） 泛代数泛代数 概率与数理统计概率与数理统计 物理物理 常微

25、分方程常微分方程 偏微分方程偏微分方程 集合论与图论集合论与图论 组合数学组合数学 抽象代数抽象代数 数理逻辑基础数理逻辑基础 层层 空间解析几何空间解析几何 数学分析数学分析 布尔代数布尔代数 高等代数高等代数 数论数论 其他学科其他学科 计算机硬件与应用计算机硬件与应用 计算科学理论计算科学理论 计算机软件与应用计算机软件与应用 其他学科其他学科 自动化技术自动化技术 电子科学等电子科学等 数据与信息表示理论数据与信息表示理论 信息处理等信息处理等 在上述三个层面构成的计算科学发展的历程中，不断在上述三个层面构成的计算科学发展的历程中，不断地追求制造出各种新型计算机系统，拓展和提高计算机的

26、地追求制造出各种新型计算机系统，拓展和提高计算机的应用领域和应用水平这样两个目标，在基础研究、应用基应用领域和应用水平这样两个目标，在基础研究、应用基础研究和技术开发与应用的研究中，学科逐步发展形成了础研究和技术开发与应用的研究中，学科逐步发展形成了三条相对独立的主线，他们是：三条相对独立的主线，他们是： 计算模型与计算机系统计算模型与计算机系统 计算模型、语言与软件开发方法学计算模型、语言与软件开发方法学 应用数学与计算机应用应用数学与计算机应用3.4 3.4 计算科学的分类与分支学科简介计算科学的分类与分支学科简介 学习一门新的学科，对这门学科的学科分类与各分支学习一门新的学科，对这门学科

27、的学科分类与各分支学科的内容作一些简要的了解有助于由浅入深地、系统地学科的内容作一些简要的了解有助于由浅入深地、系统地学好这门科学。学好这门科学。 对数学基础问题的讨论促进了构造性数学的产生和发对数学基础问题的讨论促进了构造性数学的产生和发展，产生了数学发展史上著名的三大逻辑学派：逻辑主义展，产生了数学发展史上著名的三大逻辑学派：逻辑主义学派，形式主义学派和直觉主义逻辑学派。学派，形式主义学派和直觉主义逻辑学派。 尽管数学科学的发展在计算科学的发展中得到广泛的尽管数学科学的发展在计算科学的发展中得到广泛的应用，但是与计算科学在科学方法论上形成一致的是构造应用，但是与计算科学在科学方法论上形成一

28、致的是构造性数学。这是直觉主义所以受到计算科学家欢迎的原因。性数学。这是直觉主义所以受到计算科学家欢迎的原因。可以这么说：历史上，对计算的能行性和可构造性研究的可以这么说：历史上，对计算的能行性和可构造性研究的最著名的产物要数图灵机。如果没有最著名的产物要数图灵机。如果没有1919世纪末世纪末2020世纪初关世纪初关于数学基础问题的讨论，没有直觉主义学派对数学的贡献，于数学基础问题的讨论，没有直觉主义学派对数学的贡献，计算科学可能要推迟出现。计算科学可能要推迟出现。 数理逻辑与抽象代数是计算科学最重要的两项数学基数理逻辑与抽象代数是计算科学最重要的两项数学基础，它们的研究思想和研究方法在计算科

29、学许多有深度的础，它们的研究思想和研究方法在计算科学许多有深度的领域得到了最广泛的应用。领域得到了最广泛的应用。 数理逻辑是研究推理的科学，特别，在过去主要是研数理逻辑是研究推理的科学，特别，在过去主要是研究数学中推理的科学。数理逻辑与哲学有着密切的联系，究数学中推理的科学。数理逻辑与哲学有着密切的联系，其哲学方面是形式逻辑，而形式逻辑的数学化方面构成了其哲学方面是形式逻辑，而形式逻辑的数学化方面构成了数理逻辑的研究内容。数理逻辑的研究内容。 在计算科学的研究和发展中，应该接受什么样的数学在计算科学的研究和发展中，应该接受什么样的数学理论呢？罗宾逊认为，如果大家不对一个数学理论的可解理论呢？罗

30、宾逊认为，如果大家不对一个数学理论的可解释性提出非议，那么，有几条通常被看作是基本的可接受释性提出非议，那么，有几条通常被看作是基本的可接受性的准则：性的准则： (1) (1) 一个数学理论，仅当它是协调的，或称无矛盾的，一个数学理论，仅当它是协调的，或称无矛盾的，才能被看作是可接受的；才能被看作是可接受的； (2) (2) 一个数学理论是可接受的，要是它能够作为自然科一个数学理论是可接受的，要是它能够作为自然科学的一个基础；学的一个基础； (3) (3) 一个数学理论要由美学标准来判断，比如它的美或一个数学理论要由美学标准来判断，比如它的美或内在的适当性。内在的适当性。 (3)(3)中提及的

31、标准，迄今还无从进行任何科学的研究。中提及的标准，迄今还无从进行任何科学的研究。 不过，对于不过，对于(1)(1)中提出的标准，足可以使我们认识到数中提出的标准，足可以使我们认识到数理逻辑对计算科学的重要性。众所周知，在计算科学的各理逻辑对计算科学的重要性。众所周知，在计算科学的各个分支学科中，使用了各种数学理论，包括数理逻辑。要个分支学科中，使用了各种数学理论，包括数理逻辑。要保证一个数学理论是协调的，或称无矛盾的，实际上是要保证一个数学理论是协调的，或称无矛盾的，实际上是要保证该数学理论对客观世界或应用范畴的（语义）解释是保证该数学理论对客观世界或应用范畴的（语义）解释是无矛盾的，用逻辑学

32、的术语来说就是该数学理论必须存在无矛盾的，用逻辑学的术语来说就是该数学理论必须存在模型。这在方法论上是靠逻辑学中的模型理论提供的。而模型。这在方法论上是靠逻辑学中的模型理论提供的。而要学习模型论的内容，仅有命题演算、一阶谓词演算的知要学习模型论的内容，仅有命题演算、一阶谓词演算的知识是不够的。对于识是不够的。对于(2)(2)中提及的标准，读者在今后的学习中提及的标准，读者在今后的学习中会逐步体会到其涵义。中会逐步体会到其涵义。 抽象代数是关于运算的学问，是关于计算规则的学说。抽象代数是关于运算的学问，是关于计算规则的学说。与古典代数不一样，抽象代数不是局限在字母的运算性质与古典代数不一样，抽象

33、代数不是局限在字母的运算性质上，而是研究更具有一般性的元素（在表达的形式上仍可上，而是研究更具有一般性的元素（在表达的形式上仍可看成是字母）上的运算及其性质。看成是字母）上的运算及其性质。 现在，有经验和成熟的计算科学家都知道，除了数理现在，有经验和成熟的计算科学家都知道，除了数理逻辑以外，对计算科学最重要的数学分支是代数，特别是逻辑以外，对计算科学最重要的数学分支是代数，特别是抽象代数。在计算科学中，代数方法被广泛应用于许多分抽象代数。在计算科学中，代数方法被广泛应用于许多分支学科。例如，可计算性与计算复杂性，形式语言与自动支学科。例如，可计算性与计算复杂性，形式语言与自动机理论，密码学，算

34、法理论，数据表示理论，网络与通信机理论，密码学，算法理论，数据表示理论，网络与通信理论，理论，PetriPetri网理论，程序理论，形式语义学等许多方面都网理论，程序理论，形式语义学等许多方面都离不开代数。离不开代数。 所谓计算的数学理论是指一切关于能行性问题的数学所谓计算的数学理论是指一切关于能行性问题的数学理论的总和。也有一种更具体的定义是指一切关于计算与理论的总和。也有一种更具体的定义是指一切关于计算与计算模型问题的数学理论的总和。计算理论广义的可以看计算模型问题的数学理论的总和。计算理论广义的可以看作同计算的数学理论，狭义的主要指算法理论、可计算理作同计算的数学理论，狭义的主要指算法理

35、论、可计算理论、计算复杂性理论。论、计算复杂性理论。 计算机组成原理与设计是计算机发展的一个主流方向。计算机组成原理与设计是计算机发展的一个主流方向。这一方向的主要任务是根据各种计算模型研究计算机的工这一方向的主要任务是根据各种计算模型研究计算机的工作原理，并按照器件、设备和工艺条件设计、制造具体的作原理，并按照器件、设备和工艺条件设计、制造具体的计算机。早期计算机的设计是建立在分离元器件的基础之计算机。早期计算机的设计是建立在分离元器件的基础之上，这方面的工作更多的是集中在对各个部件微观的精细上，这方面的工作更多的是集中在对各个部件微观的精细分析，后来，随着集成电路技术的进步，工作的重点已开

36、分析，后来，随着集成电路技术的进步，工作的重点已开始转到计算机的组织结构。集成电路对电路和功能部件的始转到计算机的组织结构。集成电路对电路和功能部件的高集成度和计算机设计与软件开发之间建立的密切关系，高集成度和计算机设计与软件开发之间建立的密切关系，使这一方向的发展逐步形成了一个新的计算机体系结构方使这一方向的发展逐步形成了一个新的计算机体系结构方向。向。 要开展各个领域的各种计算机具体应用，就必须首先要开展各个领域的各种计算机具体应用，就必须首先要有一些计算机应用基础知识。对计算科学专业的学生来要有一些计算机应用基础知识。对计算科学专业的学生来说，计算机应用基础知识包括算法基础、程序设计、数

37、据说，计算机应用基础知识包括算法基础、程序设计、数据结构、数据库基础、微机原理与接口技术等。结构、数据库基础、微机原理与接口技术等。 我们知道，计算机应用和计算机基本应用技术是一回我们知道，计算机应用和计算机基本应用技术是一回事，涉及到的分支学科很多。然而，从计算机应用的定义事，涉及到的分支学科很多。然而，从计算机应用的定义和科学方法论的角度出发，大致可以将计算机应用分支学和科学方法论的角度出发，大致可以将计算机应用分支学科的范畴确定下来，即它所研究的内容在方法和技术上为科的范畴确定下来，即它所研究的内容在方法和技术上为计算机在各个领域的具体应用奠定了基础。计算机在各个领域的具体应用奠定了基础

38、。 软件是计算科学一个较大的学科门类，包括众多的分软件是计算科学一个较大的学科门类，包括众多的分支学科方向，主要有高级程序设计语言、数据结构理论、支学科方向，主要有高级程序设计语言、数据结构理论、程序设计原理、编译程序原理与编译系统实现技术、数据程序设计原理、编译程序原理与编译系统实现技术、数据库原理与数据库管理系统、操作系统原理与实现技术、软库原理与数据库管理系统、操作系统原理与实现技术、软件工程技术、程序设计方法学、各种应用软件等。件工程技术、程序设计方法学、各种应用软件等。 所谓新一代计算机体系结构是相对于过去的体系结构所谓新一代计算机体系结构是相对于过去的体系结构而言的。目前，对这类体

39、系结构的研究内容很多，主要是而言的。目前，对这类体系结构的研究内容很多，主要是各种新型并行计算机的体系结构、集群式计算机体系结构，各种新型并行计算机的体系结构、集群式计算机体系结构，体系结构的可扩展性、任务级并性、指令级并行性、动态体系结构的可扩展性、任务级并性、指令级并行性、动态可改变结构等方面的内容，也有一些内容还不成熟，正在可改变结构等方面的内容，也有一些内容还不成熟，正在发展之中。发展之中。 高起点的软件开发方法学的主要基础是新一代计算机高起点的软件开发方法学的主要基础是新一代计算机体系结构、高等逻辑、形式语义学、计算模型理论以及算体系结构、高等逻辑、形式语义学、计算模型理论以及算法基

40、础。这实际上也指出了新一代计算机体系结构与软件法基础。这实际上也指出了新一代计算机体系结构与软件开发方法学（包括并行与分布式计算机系统、人工智能计开发方法学（包括并行与分布式计算机系统、人工智能计算机系统、并行与分布式软件开发方法学等）是计算科学算机系统、并行与分布式软件开发方法学等）是计算科学界需要长期努力奋斗的工作重点。界需要长期努力奋斗的工作重点。3.5 3.5 计算科学与数学和其它相关学科的关系计算科学与数学和其它相关学科的关系 计算科学与数学的关系我们已在前面的讨论中有了比计算科学与数学的关系我们已在前面的讨论中有了比较清楚的认识。总的说来，数学是计算科学的主要基础，较清楚的认识。总

41、的说来，数学是计算科学的主要基础，数学与电子科学构成了我们今天计算机系统的基础，也构数学与电子科学构成了我们今天计算机系统的基础，也构成了计算科学的基础。但是，与数学相比，电子技术基础成了计算科学的基础。但是，与数学相比，电子技术基础地位的重要性不及数学，原因是数学提供了计算科学最重地位的重要性不及数学，原因是数学提供了计算科学最重要的学科思想和学科的方法论基础，而电子技术主要是提要的学科思想和学科的方法论基础，而电子技术主要是提供了今日计算机的实现技术，它仅仅是对计算科学许多数供了今日计算机的实现技术，它仅仅是对计算科学许多数学思想和方法的一种当前最现实、最有效的实现技术。试学思想和方法的一

42、种当前最现实、最有效的实现技术。试问，假如有一天，其它的某一项技术可以更有效地取代电问，假如有一天，其它的某一项技术可以更有效地取代电子技术，那么，计算科学的基础是否会发生变化呢？相比子技术，那么，计算科学的基础是否会发生变化呢？相比之下，作为数学和计算科学理论的内容，由于其为计算科之下，作为数学和计算科学理论的内容，由于其为计算科学提供的是最重要的学科思想、技术理论和方法，因此，学提供的是最重要的学科思想、技术理论和方法，因此，它们的生命力就更长，影响也更深远。它们的生命力就更长，影响也更深远。 我们所以这样说是基于以下几点：我们所以这样说是基于以下几点： (1) (1) 首先，从计算模型和

43、可计算性的研究来看，可计首先，从计算模型和可计算性的研究来看，可计算函数和可计算谓词（一种能够能行判定其真值的断言或算函数和可计算谓词（一种能够能行判定其真值的断言或逻辑公式）是等价的，相互之间可以转化。这就是说，计逻辑公式）是等价的，相互之间可以转化。这就是说，计算可以用函数演算来表达，也可以用逻辑系统来表达。作算可以用函数演算来表达，也可以用逻辑系统来表达。作为计算模型可以计算的函数恰好与可计算谓词是等价的，为计算模型可以计算的函数恰好与可计算谓词是等价的，而且，数理逻辑本身的研究也广泛使用代数方法，同时，而且，数理逻辑本身的研究也广泛使用代数方法，同时，逻辑系统又能通过自身的无矛盾性保证

44、这样一种计算模型逻辑系统又能通过自身的无矛盾性保证这样一种计算模型是合理的。由此可见，作为一种数学形式系统，图林机及是合理的。由此可见，作为一种数学形式系统，图林机及其与它等价的计算模型的逻辑基础是坚实的。其与它等价的计算模型的逻辑基础是坚实的。 (2) (2) 实际计算机的设计与制造中，使用数字逻辑技术实实际计算机的设计与制造中，使用数字逻辑技术实现计算机的各种运算的理论基础是代数和布尔代数。布尔现计算机的各种运算的理论基础是代数和布尔代数。布尔代数只是在形式演算方面使用了代数的方法，其内容的实代数只是在形式演算方面使用了代数的方法，其内容的实质仍然是逻辑。依靠代数操作实现的指令系统具有（原

45、始）质仍然是逻辑。依靠代数操作实现的指令系统具有（原始）递归性，而数字逻辑技术和集成电路技术只是计算机系统递归性，而数字逻辑技术和集成电路技术只是计算机系统的一种产品的技术形式。的一种产品的技术形式。 (3) (3) 从计算机程序设计语言方面考察，语言的理论基础从计算机程序设计语言方面考察，语言的理论基础是形式语言、自动机与形式语义学。而形式语言、自动机是形式语言、自动机与形式语义学。而形式语言、自动机和形式语义学所采用的主要研究思想和方法来源于数理逻和形式语义学所采用的主要研究思想和方法来源于数理逻辑和代数。程序设计语言中的许多机制和方法，如子程序辑和代数。程序设计语言中的许多机制和方法，如

46、子程序调用中的参数代换、赋值等都出自数理逻辑的方法。此外，调用中的参数代换、赋值等都出自数理逻辑的方法。此外，在语言的语义研究中，四种语义方法最终可归结为代数和在语言的语义研究中，四种语义方法最终可归结为代数和逻辑的方法。这就是说，数理逻辑和代数为语言学提供了逻辑的方法。这就是说，数理逻辑和代数为语言学提供了方法论的基础。方法论的基础。 (4) (4) 在计算机体系结构的研究中，象容错计算机系统、在计算机体系结构的研究中，象容错计算机系统、TransputerTransputer计算机、阵列式向量计算机、可变结构的计算计算机、阵列式向量计算机、可变结构的计算机系统结构及其计算模型等都直接或间接

47、与逻辑与代数密机系统结构及其计算模型等都直接或间接与逻辑与代数密不可分。如容错计算机的重要基础之一是多值逻辑，不可分。如容错计算机的重要基础之一是多值逻辑，TransputerTransputer计算机的理论基础是计算机的理论基础是CSPCSP理论，阵列式向量计算理论，阵列式向量计算机必须以向量运算为基础，可变结构的计算机系统结构及机必须以向量运算为基础，可变结构的计算机系统结构及其计算模型主要采用逻辑与代数的方法。其计算模型主要采用逻辑与代数的方法。 (5) (5) 从计算机各种应用的程序设计方面考察，任何一个从计算机各种应用的程序设计方面考察，任何一个可在存储程序式电子数字计算机上运行的程

48、序，其对应的可在存储程序式电子数字计算机上运行的程序，其对应的计算方法首先都必须是构造性的，数据表示必须离散化，计算方法首先都必须是构造性的，数据表示必须离散化，计算操作必须使用逻辑或代数的方法进行，这些，都应体计算操作必须使用逻辑或代数的方法进行，这些，都应体现在算法和程序之中。此外，到现在为止，程序的语义及现在算法和程序之中。此外，到现在为止，程序的语义及其正确性的理论基础仍然是数理逻辑，或进一步的模型论。其正确性的理论基础仍然是数理逻辑，或进一步的模型论。 高等代数和一般抽象代数只解决了个体对象为简单个高等代数和一般抽象代数只解决了个体对象为简单个体的论域上的大量运算问题，但是对具有结构

49、特征和属性体的论域上的大量运算问题，但是对具有结构特征和属性成分的复杂个体的论域上的运算问题，表达和处理是不方成分的复杂个体的论域上的运算问题，表达和处理是不方便的，常常是有困难的。针对这类对象的运算操作及其正便的，常常是有困难的。针对这类对象的运算操作及其正确性等语义学问题，有必要发展泛代数和高阶逻辑理论。确性等语义学问题，有必要发展泛代数和高阶逻辑理论。 计算科学可以在几乎所有的学科领域，甚至我们日常计算科学可以在几乎所有的学科领域，甚至我们日常生活的各个方面找到应用，原因是计算（作广义理解）确生活的各个方面找到应用，原因是计算（作广义理解）确实是人类最基本的智力活动之一。一旦离开了计算，

50、人类实是人类最基本的智力活动之一。一旦离开了计算，人类将一事无成。在各个比较大一些的领域范围内，计算科学将一事无成。在各个比较大一些的领域范围内，计算科学已或多或少地找到了一些应用，这是计算机具体应用与各已或多或少地找到了一些应用，这是计算机具体应用与各个学科之间建立的联系。需要指出的是，在大多数计算机个学科之间建立的联系。需要指出的是，在大多数计算机具体应用中，由于所采用的计算机基本应用技术都是比较具体应用中，由于所采用的计算机基本应用技术都是比较成熟的技术，实际应用中对系统的开发和数据的处理客观成熟的技术，实际应用中对系统的开发和数据的处理客观上要求研究人员具备专业领域的知识，因此，计算科

51、学专上要求研究人员具备专业领域的知识，因此，计算科学专业的人员在计算机具体应用中不具有优势。业的人员在计算机具体应用中不具有优势。 计算科学的发展也必然受制于其它科学技术的发展，计算科学的发展也必然受制于其它科学技术的发展，这早已为计算机发展的历史所证实。为了将计算科学推向这早已为计算机发展的历史所证实。为了将计算科学推向更高的层次和水平，学科的发展近年来正在更多地依赖其更高的层次和水平，学科的发展近年来正在更多地依赖其它学科的发展和进步、参照和利用其它学科的思想、方法它学科的发展和进步、参照和利用其它学科的思想、方法和成果。例如，在新一代计算机系统的研制中，人们正在和成果。例如，在新一代计算

52、机系统的研制中，人们正在考虑使用光电子技术应用于计算机的设计和制造；医学中考虑使用光电子技术应用于计算机的设计和制造；医学中脑细胞结构、脑神经应激机制的研究，认知心理学的研究，脑细胞结构、脑神经应激机制的研究，认知心理学的研究，甚至蜜蜂蜂窝结构的研究都在影响着计算科学一些方向的甚至蜜蜂蜂窝结构的研究都在影响着计算科学一些方向的发展，如体系结构、神经元网络计算，等等。从现在大量发展，如体系结构、神经元网络计算，等等。从现在大量的计算科学资料中不难得知，要断言一个学科对计算科学的计算科学资料中不难得知，要断言一个学科对计算科学的发展没有丝毫的影响是难于想象的。就目前可以预见的的发展没有丝毫的影响是

53、难于想象的。就目前可以预见的对计算科学可能产生较大影响的学科而言，物理学中的光对计算科学可能产生较大影响的学科而言，物理学中的光学、精细材料科学、哲学中的科学哲学、生物科学中的生学、精细材料科学、哲学中的科学哲学、生物科学中的生物化学、脑科学与神经生理学、行为科学等对计算科学可物化学、脑科学与神经生理学、行为科学等对计算科学可能会产生较大影响。能会产生较大影响。 尽管如此，我们应该清楚地认识到，与计算科学联系尽管如此，我们应该清楚地认识到，与计算科学联系最紧密的学科是哲学中的逻辑学，数学中的构造性数学，最紧密的学科是哲学中的逻辑学，数学中的构造性数学，电学中的（微）电子科学。在不远的将来可能是

54、光电子科电学中的（微）电子科学。在不远的将来可能是光电子科学、生物科学中的遗传学和神经生理学，物理和化学科学学、生物科学中的遗传学和神经生理学，物理和化学科学中的精细材料科学，其影响的切入点主要集中在信息存储、中的精细材料科学，其影响的切入点主要集中在信息存储、信息传递、认知过程、大规模信息传输的介质和机理方面。信息传递、认知过程、大规模信息传输的介质和机理方面。3.6 3.6 计算科学的学科形态与核心概念计算科学的学科形态与核心概念 每一个学科都有其自身的每一个学科都有其自身的知识组织结构知识组织结构、学科形态学科形态、核心概念核心概念和和基本工作流程方式基本工作流程方式。所谓学科形态，是指

55、从事。所谓学科形态，是指从事该领域工作的文化方式。对计算科学的深入研究使我们已该领域工作的文化方式。对计算科学的深入研究使我们已知该学科存在三种主要的学科形态，即知该学科存在三种主要的学科形态，即理论理论、抽象抽象和和设计设计。 第一种形态是理论，基于计算科学的数学基础和计算第一种形态是理论，基于计算科学的数学基础和计算科学理论，广泛采用数学的研究方法。按统一的合理的理科学理论，广泛采用数学的研究方法。按统一的合理的理论发展过程，包含以下四个步骤：论发展过程，包含以下四个步骤： 对研究对象的概念抽象（定义）；对研究对象的概念抽象（定义）； 假设对象的基本性质和对象之间可能存在的关系假设对象的基

56、本性质和对象之间可能存在的关系（定理）；（定理）； 确定这些性质和关系是否正确（证明）；确定这些性质和关系是否正确（证明）； 解释结果（与计算机系统或研究对象形成对应）。解释结果（与计算机系统或研究对象形成对应）。 这个学科形态的基本特征是其研究内容的构造性数学这个学科形态的基本特征是其研究内容的构造性数学特征，是区别于更广泛的数学科学学科形态的典型特征。特征，是区别于更广泛的数学科学学科形态的典型特征。 第二种形态是抽象，或称模型化，基于计算科学的实第二种形态是抽象，或称模型化，基于计算科学的实验科学方法，广泛采用实验物理学的研究方法。按照对客验科学方法，广泛采用实验物理学的研究方法。按照对

57、客观现象和规律的实验研究过程，包含以下四个步骤：观现象和规律的实验研究过程，包含以下四个步骤： 确定可能世界（环境）并形成假设；确定可能世界（环境）并形成假设； 构造模型并做出预言；构造模型并做出预言； 设计实验并收集数据；设计实验并收集数据； 分析结果。分析结果。 这个学科形态主要出现在计算科学中与硬件设计和实这个学科形态主要出现在计算科学中与硬件设计和实验有关的研究之中。当计算科学理论比较深奥，理解较为验有关的研究之中。当计算科学理论比较深奥，理解较为困难时，不少科研人员在大致了解理论、方法和技术的情困难时，不少科研人员在大致了解理论、方法和技术的情况下，基于经验和技能常以这种学科形态方式

58、开展工作。况下，基于经验和技能常以这种学科形态方式开展工作。 第三种形态是设计，基于工程，广泛采用工程科学第三种形态是设计，基于工程，广泛采用工程科学（如建筑工程）的研究方法。按照为解决某一个问题构作（如建筑工程）的研究方法。按照为解决某一个问题构作系统或装置的过程，包含以下四个步骤：系统或装置的过程，包含以下四个步骤： 叙述要求；叙述要求； 给定技术条件；给定技术条件； 设计并实现该系统或装置；设计并实现该系统或装置； 测试和分析该系统。测试和分析该系统。 这个学科形态广泛出现在计算科学中与硬件、软件、这个学科形态广泛出现在计算科学中与硬件、软件、应用有关的设计和实现之中。当计算科学理论（包

59、括技术应用有关的设计和实现之中。当计算科学理论（包括技术理论）已解决某一问题后，科研人员在正确理解理论、方理论）已解决某一问题后，科研人员在正确理解理论、方法和技术的情况下，可以十分有效地以这种学科形态方式法和技术的情况下，可以十分有效地以这种学科形态方式开展工作。开展工作。 第二种学科形态抽象，是对客观现象和规律的抽象，第二种学科形态抽象，是对客观现象和规律的抽象，是对客观现象和规律的描述和刻划。在这一过程中，与具是对客观现象和规律的描述和刻划。在这一过程中，与具体客观现象和规律无关或对具体客观现象和规律影响不大体客观现象和规律无关或对具体客观现象和规律影响不大的因素被去掉了，其内容构成了计

60、算科学理论的一部分，的因素被去掉了，其内容构成了计算科学理论的一部分，即技术理论中其内容比较难于用简洁的数学形式描述的那即技术理论中其内容比较难于用简洁的数学形式描述的那一部分。第一种学科形态理论，也是一种抽象，是对客观一部分。第一种学科形态理论，也是一种抽象，是对客观现象和规律的数学化、形式化描述，是对能行问题及其求现象和规律的数学化、形式化描述，是对能行问题及其求解过程的刻划，其内容构成了计算科学的数学基础和理论解过程的刻划，其内容构成了计算科学的数学基础和理论计算机科学。本质上，这两种学科形态都是对客观现象和计算机科学。本质上，这两种学科形态都是对客观现象和规律的抽象，只是方式的不同。第