第三章 计算科学：它的意义、内容和方法 先介绍三个基本术语,它们是

第三章计算科学：它的意义、内容和方法先介绍三个基本术语，它们是科学、技术和工程。科学是关于自然、社会和思维的发展与变化规律的知识体系。技术是泛指根据生产实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧。工程是指将科学原理应用到工农业生产部门中去而形成的各门学科的总称。3.1什么是计算科学？计算科学是对描述和变换信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用的系统研究。全部计算科学的基本问题是：什么能有效地自动进行，什么不能有效地自动进行。本学科来源于对数理逻辑、计算模型、算法理论、自动计算机器的研究，形成于1930年代后期。现在，计算已成为继理论、实验之后的第三种科学形态。3.2学科的基本问题一个学科如果没有问题需要解决，这个学科的生命就结束了。每一个学科在发展的不同时期，都存在一些基本问题和重大问题，它们的解决推动了学科持续的发展。那么，哪些是计算科学学科发展的重大问题和基本问题呢？重大问题是比较容易理解的，而且，相对于不同时期，重大问题既是相对的，也是比较多的。例如，学科发展早期提出的什么是可计算与不可计算的概念，1950年代末1960年代初提出的高级程序设计语言的形式化描述问题，1960年代末1970年代初提出的操作系统中的并发控制问题，等等。然而，在学科经历了几十年的发展后，当我们今天以科学哲学的观点回顾历史的进程，系统总结学科的内容时，可以发现：如同数学等一些基础学科一样，在学科各个分支学科方向的发展进程中，不断地出现了一些在表现形式上虽然不同，但在科学哲学的解释下本质上是相同或相近的问题，即学科研究与发展普遍关心的基本问题。这些基本问题主要有如下三个：⑴计算的平台与环境问题⑵计算过程的能行操作与效率问题⑶计算的正确性问题在学科发展的历程中，不断地追求制造出各种新型计算机系统，拓展和提高计算机的应用领域和应用水平这样两个目标，围绕学科的三个基本问题使学科的发展形成了三条相对独立的主线，形成了许多相对独立的分支学科和研究方向。同时，我们也注意到，在学科的发展过程中，不同时期，围绕着学科的一些重大问题和基本问题，若干方向便构成了所谓的主流方向，由主流方向又形成了学科的发展主线。计算的平台与环境问题是不难理解的。历史上，为了实现自动计算，人们首先想到了要发明和制造自动计算机器，不仅要从理论上提供计算的平台——观察和描述计算的起点，或者证明问题本身不可解，而且要实际制造出针对各种待处理问题特点和要求的自动计算机器。进一步，从广义的计算的概念出发，计算的平台在使用上还必须比较方便，于是派生出计算环境的概念。据此，不难看出，理论研究中提出的各种计算模型，各种实际的计算机系统，各种高级程序设计语言，各种计算机体系结构，各种软件开发工具与环境，编译程序与操作系统，数据库系统等都是围绕这一基本问题发展而来的，其内容实质可归结为计算的模型问题，也就是说，这个基本问题实际上关心的是计算问题在理论上是否能行的问题。当然，这里所说的计算模型是广义的。计算过程的能行操作与效率问题也是学科的基本问题之一。一个问题在判明为可计算的性质后，从具体解决这个问题着眼，必须按照能行可构造的特点与要求，给出实际解决该问题的一步一步的具体操作，同时还必须确保这样一种过程的开销成本是我们能够承受的。围绕这一问题，学科发展了大量与之相关的研究内容与分支学科方向。例如，数值与非数值计算方法，算法设计与分析，结构化程序设计技术与效率分析，以计算机部件为背景的集成电路技术，密码学与快速算法，演化计算，数字系统逻辑设计，程序设计方法学（程序推导与程序变换技术），自动布线，RISC技术，人工智能的逻辑基础等分支学科的内容都是围绕这一基本问题展开、发展而形成的。显然，计算操作的能行与效率问题也涉及到了计算模型的问题，但是，这里所说的计算模型既包括类似于具有状态转换特征的那一类计算模型，也包括数学建摸这类计算模型。不难看出，这一基本问题的核心是算法问题。这也辅助说明了在计算科学发展的早期，当计算的平台与环境、计算的正确性问题尚不突出时，为什么学术界将本学科看成是算法的学问。计算的正确性是任何计算工作都不能回避的问题，特别是使用自动计算机器进行的各种计算。一个计算问题在给出了能行操作序列并解决了其效率问题之后，必须确保计算的正确性，否则，计算是无意义的，也是容易产生不利影响的。围绕这一基本问题，长期以来，学科发展了一些相关的分支学科与研究方向，例如，算法理论（数值与非数值算法设计的理论基础），程序理论（程序设计方法学），程序设计语言的语义学，进程代数与分布式事件代数，程序测试技术，电路测试技术，软件工程技术（形式化的软件开发方法学），计算语言学，容错理论与技术，Petri网理论，CSP理论，CCS理论，分布式网络协议等都是针对为解决这一基本问题而发展形成的。今天，计算的正确性问题常常归结为各种语言的语义问题，这也从一个侧面提示了计算的正确性问题可以归结为语义学问题，揭示了语义学在整个学科中的重要地位。上述基本问题普遍出现在学科的各个分支学科和研究方向之中，是学科研究与发展中经常面对而又必须解决的问题。3.3计算科学发展主线从科学哲学的角度，将计算科学的学科内容按照基础理论、基本开发技术、应用以及它们与硬件设备联系的紧密程度可分成三个层面。第一层面是计算科学的应用层，它包括人工智能应用与系统，信息、管理与决策系统，移动计算、计算可视化、科学计算等计算机应用的各个方向。其中，人工智能应用与系统涵盖人工智能，机器人，神经元计算，知识工程，自然语言处理与机器翻译，自动推理等方向；信息、管理与决策系统涵盖数据库设计与数据管理技术，数据表示与存储（包括多媒体技术），数据与信息检索，管理信息系统，计算机辅助系统，决策系统等方向；计算可视化涵盖计算机图形学，计算几何，模式识别与图像处理等方向；第二层面是计算科学的专业基础层，它是为应用层提供技术和环境的一个层面，包括软件开发方法学，计算机网络与通信技术，程序设计科学，计算机体系结构，电子计算机系统基础。其中，软件开发方法学涵盖顺序、并行与分布式软件开发方法学，如软件工程技术，软件开发工具和环境等方向；计算机网络与通信技术涵盖计算机网络互联技术，数据通信技术，以及信息保密与安全技术等方向；程序设计科学涵盖数据结构技术，数值与符号计算，算法设计与分析（包括并行与分布式算法设计与分析），程序设计语言，程序设计语言的文法与语义（指程序设计语言的文法与语义描述），程序设计方法学，程序理论等方向；电子计算机系统基础涵盖数字逻辑技术，计算机组成原理，故障诊断与器件测试技术，操作系统，编译技术，数据库系统实现技术，容错技术等方向；第三层面是计算科学的基础层，它包括计算的数学理论，高等逻辑等内容。其中，计算的数学理论涵盖可计算性（递归论）与计算复杂性理论，形式语言与自动机理论，形式语义学（主要指代数语义，公理语义等），Petri网理论等方向；高等逻辑涵盖模型论，各种非经典逻辑与公理集合论等方向。支撑这三个层面的是计算科学这一学科的理工科基础科目，包括物理学（主要是电子技术科学）、基础数学（含离散数学）等。详细可参见图。移动计算与全球定位计算机自动控制计算机辅助制造计算机集成制造系统计算机器人计算可视化与虚拟现实数据与信息检索计算机创作计算机网络应用软件科学科学计算多媒体信息系统计算机辅助设计信息、管理与决策系统自然语言处理应用模式识别与图像处理技术计算机图形学计算几何人工智能与知识工程层数据表示与存储网络与开放系统互联标准软件测试技术人机工程学（人机界面）───────────────────────────────────────计算软件开发方法学:软件工程技术、程序设计方法学、软件开发工具和环境、软件开发规范科学编码理论密码学计算机体系结构程序理论数据表示理论与数据库系统专业电子计算机系统基础计算机接口与通信计算机网络与数据通信技术自动推理基础故障诊断与器件测试技术容错技术汇编技术操作系统高级语言程序设计层数字系统设计符号计算与计算机代数数据结构技术算法设计与分析编译与解释技术────────────────────────────────────────计算控制论基础数字系统设计基础信息论基础网论（Petri网理论等）形式语义学科学框图理论算法理论可计算性（递归论）计算复杂性程序设计语言理论基础计算模型（各种抽象机）模型论与非经典逻辑公理集合论形式语言与自动机层──────────────────────────────────────────数学光电子技术基础电路基础电子线路基础数字与模拟电路基础数值分析与计算方法与大学物理学函数论基础（复变函数、λ演算、泛函分析等）泛代数概率与数理统计物理常微分方程偏微分方程集合论与图论组合数学抽象代数数理逻辑基础层空间解析几何数学分析布尔代数高等代数数论──────────────────────────────────────────其他学科计算机硬件与应用计算科学理论计算机软件与应用其他学科自动化技术电子科学等数据与信息表示理论信息处理等←━━━━━━━━━━────────→在上述三个层面构成的计算科学发展的历程中，不断地追求制造出各种新型计算机系统，拓展和提高计算机的应用领域和应用水平这样两个目标，在基础研究、应用基础研究和技术开发与应用的研究中，学科逐步发展形成了三条相对独立的主线，他们是：⑴计算模型与计算机系统⑵计算模型、语言与软件开发方法学⑶应用数学与计算机应用3.4计算科学的分类与分支学科简介学习一门新的学科，对这门学科的学科分类与各分支学科的内容作一些简要的了解有助于由浅入深地、系统地学好这门科学。3.4.1构造性数学基础对数学基础问题的讨论促进了构造性数学的产生和发展，产生了数学发展史上著名的三大逻辑学派：逻辑主义学派，形式主义学派和直觉主义逻辑学派。尽管数学科学的发展在计算科学的发展中得到广泛的应用，但是与计算科学在科学方法论上形成一致的是构造性数学。这是直觉主义所以受到计算科学家欢迎的原因。可以这么说：历史上，对计算的能行性和可构造性研究的最著名的产物要数图灵机。如果没有19世纪末20世纪初关于数学基础问题的讨论，没有直觉主义学派对数学的贡献，计算科学可能要推迟出现。数理逻辑与抽象代数是计算科学最重要的两项数学基础，它们的研究思想和研究方法在计算科学许多有深度的领域得到了最广泛的应用。数理逻辑是研究推理的科学，特别，在过去主要是研究数学中推理的科学。数理逻辑与哲学有着密切的联系，其哲学方面是形式逻辑，而形式逻辑的数学化方面构成了数理逻辑的研究内容。在计算科学的研究和发展中，应该接受什么样的数学理论呢？罗宾逊认为，如果大家不对一个数学理论的可解释性提出非议，那么，有几条通常被看作是基本的可接受性的准则：(1)一个数学理论，仅当它是协调的，或称无矛盾的，才能被看作是可接受的；(2)一个数学理论是可接受的，要是它能够作为自然科学的一个基础；(3)一个数学理论要由美学标准来判断，比如它的美或内在的适当性。(3)中提及的标准，迄今还无从进行任何科学的研究。不过，对于(1)中提出的标准，足可以使我们认识到数理逻辑对计算科学的重要性。众所周知，在计算科学的各个分支学科中，使用了各种数学理论，包括数理逻辑。要保证一个数学理论是协调的，或称无矛盾的，实际上是要保证该数学理论对客观世界或应用范畴的（语义）解释是无矛盾的，用逻辑学的术语来说就是该数学理论必须存在模型。这在方法论上是靠逻辑学中的模型理论提供的。而要学习模型论的内容，仅有命题演算、一阶谓词演算的知识是不够的。对于(2)中提及的标准，读者在今后的学习中会逐步体会到其涵义。抽象代数是关于运算的学问，是关于计算规则的学说。与古典代数不一样，抽象代数不是局限在字母的运算性质上，而是研究更具有一般性的元素（在表达的形式上仍可看成是字母）上的运算及其性质。现在，有经验和成熟的计算科学家都知道，除了数理逻辑以外，对计算科学最重要的数学分支是代数，特别是抽象代数。在计算科学中，代数方法被广泛应用于许多分支学科。例如，可计算性与