第三章 计算科学：它的意义、内容和方法

第三章计算科学：它的意义、内容和方法先介绍三个基本术语，它们是科学、技术和工程。科学是关于自然、社会和思维的发展与变化规律的知识体系。技术是泛指根据生产实践经验和科学原理而发展形成的各种工艺操作方法、技能和技巧。工程是指将科学原理应用到工农业生产部门中去而形成的各门学科的总称。3.1什么是计算科学？计算科学是对描述和变换信息的算法过程，包括其理论、分析、设计、效率分析、实现和应用的系统的研究。全部计算科学的基本问题是，什么能（有效地）自动进行，什么不能（有效地）自动进行。本学科来源于对数理逻辑、计算模型、算法理论、自动计算机器的研究，形成于本世纪30年代后期。现在，计算已成为继理论、实验之后的第三种科学形态。3.2学科的基本问题一个学科如果没有问题需要解决，这个学科的生命就结束了。每一个学科在发展的不同时期，都存在一些基本问题和重大问题，它们的解决推动了学科持续的发展。那么，哪些是计算科学学科发展的重大问题和基本问题呢？重大问题是比较容易理解的，而且，相对于不同时期，重大问题既是相对的，也是比较多的。例如，学科发展早期提出的什么是可计算与不可计算的概念，50年代末60年代初提出的高级程序设计语言的形式化描述问题，60年代末70年代初提出的操作系统中的并发控制问题，等等。然而，在学科经历了几十年的发展后，当我们今天以科学哲学的观点回顾历史的进程，系统总结学科的内容时，可以发现：如同数学等一些基础学科一样，在学科各个分支学科方向的发展进程中，不断地出现了一些在表现形式上虽然不同，但在科学哲学的解释下本质上是相同或相近的问题，即学科研究与发展普遍关心的基本问题。这些基本问题主要有如下三个：⑴计算的平台与环境问题⑵计算过程的能行操作与效率问题⑶计算的正确性问题在学科发展的历程中，不断地追求制造出各种新型计算机系统，拓展和提高计算机的应用领域和应用水平这样两个目标，围绕学科的三个基本问题使学科的发展形成了三条相对独立的主线，形成了许多相对独立的分支学科和研究方向。同时，我们也注意到，在学科的发展过程中，不同时期，围绕着学科的一些重大问题和基本问题，若干方向便构成了所谓的主流方向，由主流方向又形成了学科的发展主线。计算的平台与环境问题是不难理解的。历史上，为了实现自动计算，人们首先想到了要发明和制造自动计算机器，不仅要从理论上提供计算的平台——观察和描述计算的起点，或者证明问题本身不可解，而且要实际制造出针对各种待处理问题特点和要求的自动计算机器。进一步，从广义的计算的概念出发，计算的平台在使用上还必须比较方便，于是派生出计算环境的概念。据此，不难看出，理论研究中提出的各种计算模型，各种实际的计算机系统，各种高级程序设计语言，各种计算机体系结构，各种软件开发工具与环境，编译程序与操作系统，数据库系统等都是围绕这一基本问题发展而来的，其内容实质可归结为计算的模型问题，也就是说，这个基本问题实际上关心的是计算问题在理论上是否能行的问题。当然，这里所说的计算模型是广义的。计算过程的能行操作与效率问题也是学科的基本问题之一。一个问题在判明为可计算的性质后，从具体解决这个问题着眼，必须按照能行可构造的特点与要求，给出实际解决该问题的一步一步的具体操作，同时还必须确保这样一种过程的开销成本是我们能够承受的。围绕这一问题，学科发展了大量与之相关的研究内容与分支学科方向。例如，数值与非数值计算方法，算法设计与分析，结构化程序设计技术与效率分析，以计算机部件为背景的集成电路技术，密码学与快速算法，演化计算，数字系统逻辑设计，程序设计方法学（程序推导与程序变换技术），自动布线，RISC技术，人工智能的逻辑基础等分支学科的内容都是围绕这一基本问题展开、发展而形成的。显然，计算操作的能行与效率问题也涉及到了计算模型的问题，但是，这里所说的计算模型既包括类似于具有状态转换特征的那一类计算模型，也包括数学建摸这类计算模型。不难看出，这一基本问题的核心是算法问题。这也辅助说明了在计算科学发展的早期，当计算的平台与环境、计算的正确性问题尚不突出时，为什么学术界将本学科看成是算法的学问。计算的正确性是任何计算工作都不能回避的问题，特别是使用自动计算机器进行的各种计算。一个计算问题在给出了能行操作序列并解决了其效率问题之后，必须确保计算的正确性，否则，计算是无意义的，也是容易产生不利影响的。围绕这一基本问题，长期以来，学科发展了一些相关的分支学科与研究方向，例如，算法理论（数值与非数值算法设计的理论基础），程序理论（程序设计方法学），程序设计语言的语义学，进程代数与分布式事件代数，程序测试技术，电路测试技术，软件工程技术（形式化的软件开发方法学），计算语言学，容错理论与技术，Petri网理论，CSP理论，CCS理论，分布式网络 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 等都是针对为解决这一基本问题而发展形成的。今天，计算的正确性问题常常归结为各种语言的语义问题，这也从一个侧面提示了计算的正确性问题可以归结为语义学问题，揭示了语义学在整个学科中的重要地位。上述基本问题普遍出现在学科的各个分支学科和研究方向之中，是学科研究与发展中经常面对而又必须解决的问题。循着这一线索，我们不难看出，整个学科正是在围绕这些基本问题和不同时期重大问题而展开的研究与发展中形成了学科的发展主线与主流方向。3.3计算科学发展主线从科学哲学的角度，将计算科学的学科内容按照基础理论、基本开发技术、应用以及它们与硬件设备联系的紧密程度可分成三个层面。第一层面是计算科学的应用层，它包括人工智能应用与系统，信息、管理与决策系统，移动计算、计算可视化、科学计算等计算机应用的各个方向。其中，人工智能应用与系统涵盖人工智能，机器人，神经元计算，知识工程，自然语言处理与机器翻译，自动推理等方向；信息、管理与决策系统涵盖数据库设计与数据管理技术，数据表示与存储（包括多媒体技术），数据与信息检索，管理信息系统，计算机辅助系统，决策系统等方向；计算可视化涵盖计算机图形学，计算几何，模式识别与图像处理等方向；第二层面是计算科学的专业基础层，它是为应用层提供技术和环境的一个层面，包括软件开发方法学，计算机网络与通信技术，程序设计科学，计算机体系结构，电子计算机系统基础。其中，软件开发方法学涵盖顺序、并行与分布式软件开发方法学，如软件工程技术，软件开发工具和环境等方向；计算机网络与通信技术涵盖计算机网络互联技术，数据通信技术，以及信息保密与安全技术等方向；程序设计科学涵盖数据结构技术，数值与符号计算，算法设计与分析（包括并行与分布式算法设计与分析），程序设计语言，程序设计语言的文法与语义（指程序设计语言的文法与语义描述），程序设计方法学，程序理论等方向；电子计算机系统基础涵盖数字逻辑技术，计算机组成原理，故障诊断与器件测试技术，操作系统，编译技术，数据库系统实现技术，容错技术等方向；第三层面是计算科学的基础层，它包括计算的数学理论，高等逻辑等内容。其中，计算的数学理论涵盖可计算性（递归论）与计算复杂性理论，形式语言与自动机理论，形式语义学（主要指代数语义，公理语义等），Petri网理论等方向；高等逻辑涵盖模型论，各种非经典逻辑与公理集合论等方向。支撑这三个层面的是计算科学这一学科的理工科基础科目，包括物理学（主要是电子技术科学）、基础数学（含离散数学）等。详细可参见图。移动计算与全球定位计算机自动控制计算机辅助制造计算机集成制造系统计算机器人计算可视化与虚拟现实数据与信息检索计算机创作计算机网络应用软件科学科学计算多媒体信息系统计算机辅助设计信息、管理与决策系统自然语言处理应用模式识别与图像处理技术计算机图形学计算几何人工智能与知识工程层数据表示与存储网络与开放系统互联标准软件测试技术人机工程学（人机界面）───────────────────────────────────────计算软件开发方法学:软件工程技术、程序设计方法学、软件开发工具和环境、软件开发规范科学编码理论密码学计算机体系结构程序理论数据表示理论与数据库系统专业电子计算机系统基础计算机接口与通信计算机网络与数据通信技术自动推理基础故障诊断与器件测试技术容错技术汇编技术操作系统高级语言程序设计层数字系统设计符号计算与计算机代数数据结构技术算法设计与分析编译与解释技术────────────────────────────────────────计算控制论基础数字系统设计基础信息论基础网论（Petri网理论等）形式语义学科学框图理论算法理论可计算性（递归论）计算复杂性程序设计语言理论基础计算模型（各种抽象机）模型论与非经典逻辑公理集合论形式语言与自动机层──────────────────────────────────────────数学光电子技术基础电路基础电子线路基础数字与模拟电路基础数值分析与计算方法与大学物理学函数论基础（复变函数、λ演算、泛函分析等）泛代数概率与数理统计物理常微分方程偏微分方程集合论与图论组合数学抽象代数数理逻辑基础层空间解析几何数学分析布尔代数高等代数数论──────────────────────────────────────────其他学科计算机硬件与应用计算科学理论计算机软件与应用其他学科自动化技术电子科学等数据与信息表示理论信息处理等←━━━━━━━━━━────────→在上述三个层面构成的计算科学发展的历程中，不断地追求制造出各种新型计算机系统，拓展和提高计算机的应用领域和应用水平这样两个目标，在基础研究、应用基础研究和技术开发与应用的研究中，学科逐步发展形成了三条相对独立的主线，他们是：⑴计算模型与计算机系统⑵计算模型、语言与软件开发方法学⑶应用数学与计算机应用3.4计算科学的分类与分支学科简介学习一门新的学科，对这门学科的学科分类与各分支学科的内容作一些简要的了解有助于由浅入深地、系统地学好这门科学。3.4.1构造性数学基础对数学基础问题的讨论促进了构造性数学的产生和发展，产生了数学发展史上著名的三大逻辑学派：逻辑主义学派，形式主义学派和直觉主义逻辑学派。尽管数学科学的发展在计算科学的发展中得到广泛的应用，但是与计算科学在科学方法论上形成一致的是构造性数学。这是直觉主义所以受到计算科学家欢迎的原因。可以这么说：历史上，对计算的能行性和可构造性研究的最著名的产物要数图灵机。如果没有19世纪末20世纪初关于数学基础问题的讨论，没有直觉主义学派对数学的贡献，计算科学可能要推迟出现。数理逻辑与抽象代数是计算科学最重要的两项数学基础，它们的研究思想和研究方法在计算科学许多有深度的领域得到了最广泛的应用。数理逻辑是研究推理的科学，特别，在过去主要是研究数学中推理的科学。数理逻辑与哲学有着密切的联系，其哲学方面是形式逻辑，而形式逻辑的数学化方面构成了数理逻辑的研究内容。在计算科学的研究和发展中，应该接受什么样的数学理论呢？罗宾逊认为，如果大家不对一个数学理论的可解释性提出非议，那么，有几条通常被看作是基本的可接受性的准则：(1)一个数学理论，仅当它是协调的，或称无矛盾的，才能被看作是可接受的；(2)一个数学理论是可接受的，要是它能够作为自然科学的一个基础；(3)一个数学理论要由美学标准来判断，比如它的美或内在的适当性。(3)中提及的标准，迄今还无从进行任何科学的研究。不过，对于(1)中提出的标准，足可以使我们认识到数理逻辑对计算科学的重要性。众所周知，在计算科学的各个分支学科中，使用了各种数学理论，包括数理逻辑。要保证一个数学理论是协调的，或称无矛盾的，实际上是要保证该数学理论对客观世界或应用范畴的（语义）解释是无矛盾的，用逻辑学的术语来说就是该数学理论必须存在模型。这在方法论上是靠逻辑学中的模型理论提供的。而要学习模型论的内容，仅有命题演算、一阶谓词演算的知识是不够的。对于(2)中提及的标准，读者在今后的学习中会逐步体会到其涵义。抽象代数是关于运算的学问，是关于计算规则的学说。与古典代数不一样，抽象代数不是局限在字母的运算性质上，而是研究更具有一般性的元素（在表达的形式上仍可看成是字母）上的运算及其性质。现在，有经验和成熟的计算科学家都知道，除了数理逻辑以外，对计算科学最重要的数学分支是代数，特别是抽象代数。在计算科学中，代数方法被广泛应用于许多分支学科。例如，可计算性与计算复杂性，形式语言与自动机理论，密码学，算法理论，数据表示理论，网络与通信理论，Petri网理论，程序理论，形式语义学等许多方面都离不开代数。3.4.2计算的数学理论所谓计算的数学理论是指一切关于能行性问题的数学理论的总和。也有一种更具体的定义是指一切关于计算与计算模型问题的数学理论的总和。计算理论广义的可以看作同计算的数学理论，狭义的主要指算法理论、可计算理论、计算复杂性理论。3.4.3计算机组成原理、器件与体系结构计算机组成原理与设计是计算机发展的一个主流方向。这一方向的主要任务是根据各种计算模型研究计算机的工作原理，并按照器件、设备和工艺条件设计、制造具体的计算机。早期计算机的设计是建立在分离元器件的基础之上，这方面的工作更多的是集中在对各个部件微观的精细分析，后来，随着集成电路技术的进步，工作的重点已开始转到计算机的组织结构。集成电路对电路和功能部件的高集成度和计算机设计与软件开发之间建立的密切关系，使这一方向的发展逐步形成了一个新的计算机体系结构方向。 3.4.4计算机应用基础要开展各个领域的各种计算机具体应用，就必须首先要有一些计算机应用基础知识。对计算科学专业的学生来说，计算机应用基础知识包括算法基础、程序设计、数据结构、数据库基础、微机原理与接口技术等。3.4.5计算机基本应用技术我们知道，计算机应用和计算机基本应用技术是一回事，涉及到的分支学科很多。然而，从计算机应用的定义和科学方法论的角度出发，大致可以将计算机应用分支学科的范畴确定下来，即它所研究的内容在方法和技术上为计算机在各个领域的具体应用奠定了基础。3.4.6软件基础软件是计算科学一个较大的学科门类，包括众多的分支学科方向，主要有高级程序设计语言、数据结构理论、程序设计原理、编译程序原理与编译系统实现技术、数据库原理与数据库管理系统、操作系统原理与实现技术、软件工程技术、程序设计方法学、各种应用软件等。3.4.7新一代计算机体系结构与软件开发方法学所谓新一代计算机体系结构是相对于过去的体系结构而言的。目前，对这类体系结构的研究内容很多，主要是各种新型并行计算机的体系结构、集群式计算机体系结构，体系结构的可扩展性、任务级并性、指令级并行性、动态可改变结构等方面的内容，也有一些内容还不成熟，正在发展之中。高起点的软件开发方法学的主要基础是新一代计算机体系结构、高等逻辑、形式语义学、计算模型理论以及算法基础。这实际上也指出了新一代计算机体系结构与软件开发方法学（包括并行与分布式计算机系统、人工智能计算机系统、并行与分布式软件开发方法学等）是计算科学界需要长期努力奋斗的工作重点。3.5计算科学与数学和其它相关学科的关系计算科学与数学的关系我们已在前面的讨论中有了比较清楚的认识。总的说来，数学是计算科学的主要基础，数学与电子科学构成了我们今天计算机系统的基础，也构成了计算科学的基础。但是，与数学相比，电子技术基础地位的重要性不及数学，原因是数学提供了计算科学最重要的学科思想和学科的方法论基础，而电子技术主要是提供了今日计算机的实现技术，它仅仅是对计算科学许多数学思想和方法的一种当前最现实、最有效的实现技术。试问，假如有一天，其它的某一项技术可以更有效地取代电子技术，那么，计算科学的基础是否会发生变化呢？相比之下，作为数学和计算科学理论的内容，由于其为计算科学提供的是最重要的学科思想、技术理论和方法，因此，它们的生命力就更长，影响也更深远。3.5.1为什么说数理逻辑和代数是计算科学的主要基础我们所以这样说是基于以下几点：(1)首先，从计算模型和可计算性的研究来看，可计算函数和可计算谓词（一种能够能行判定其真值的断言或逻辑公式）是等价的，相互之间可以转化。这就是说，计算可以用函数演算来表达，也可以用逻辑系统来表达。作为计算模型可以计算的函数恰好与可计算谓词是等价的，而且，数理逻辑本身的研究也广泛使用代数方法，同时，逻辑系统又能通过自身的无矛盾性保证这样一种计算模型是合理的。由此可见，作为一种数学形式系统，图林机及其与它等价的计算模型的逻辑基础是坚实的。(2)实际计算机的设计与制造中，使用数字逻辑技术实现计算机的各种运算的理论基础是代数和布尔代数。布尔代数只是在形式演算方面使用了代数的方法，其内容的实质仍然是逻辑。依靠代数操作实现的指令系统具有（原始）递归性，而数字逻辑技术和集成电路技术只是计算机系统的一种产品的技术形式。(3)从计算机程序设计语言方面考察，语言的理论基础是形式语言、自动机与形式语义学。而形式语言、自动机和形式语义学所采用的主要研究思想和方法来源于数理逻辑和代数。程序设计语言中的许多机制和方法，如子程序调用中的参数代换、赋值等都出自数理逻辑的方法。此外，在语言的语义研究中，四种语义方法最终可归结为代数和逻辑的方法。这就是说，数理逻辑和代数为语言学提供了方法论的基础。(4)在计算机体系结构的研究中，象容错计算机系统、Transputer计算机、阵列式向量计算机、可变结构的计算机系统结构及其计算模型等都直接或间接与逻辑与代数密不可分。如容错计算机的重要基础之一是多值逻辑，Transputer计算机的理论基础是CSP理论，阵列式向量计算机必须以向量运算为基础，可变结构的计算机系统结构及其计算模型主要采用逻辑与代数的方法。(5)从计算机各种应用的程序设计方面考察，任何一个可在存储程序式电子数字计算机上运行的程序，其对应的计算方法首先都必须是构造性的，数据表示必须离散化，计算操作必须使用逻辑或代数的方法进行，这些，都应体现在算法和程序之中。此外，到现在为止，程序的语义及其正确性的理论基础仍然是数理逻辑，或进一步的模型论。⑹高等代数和一般抽象代数只解决了个体对象为简单个体的论域上的大量运算问题，但是对具有结构特征和属性成分的复杂个体的论域上的运算问题，表达和处理是不方便的，常常是有困难的。针对这类对象的运算操作及其正确性等语义学问题，有必要发展泛代数和高阶逻辑理论。3.5.2计算科学与其它相关学科的关系计算科学可以在几乎所有的学科领域，甚至我们日常生活的各个方面找到应用，原因是计算（作广义理解）确实是人类最基本的智力活动之一。一旦离开了计算，人类将一事无成。在各个比较大一些的领域范围内，计算科学已或多或少地找到了一些应用，这是计算机具体应用与各个学科之间建立的联系。需要指出的是，在大多数计算机具体应用中，由于所采用的计算机基本应用技术都是比较成熟的技术，实际应用中对系统的开发和数据的处理客观上要求研究人员具备专业领域的知识，因此，计算科学专业的人员在计算机具体应用中不具有优势。计算科学的发展也必然受制于其它科学技术的发展，这早已为计算机发展的历史所证实。为了将计算科学推向更高的层次和水平，学科的发展近年来正在更多地依赖其它学科的发展和进步、参照和利用其它学科的思想、方法和成果。例如，在新一代计算机系统的研制中，人们正在考虑使用光电子技术应用于计算机的设计和制造；医学中脑细胞结构、脑神经应激机制的研究，认知心理学的研究，甚至蜜蜂蜂窝结构的研究都在影响着计算科学一些方向的发展，如体系结构、神经元网络计算，等等。从现在大量的计算科学资料中不难得知，要断言一个学科对计算科学的发展没有丝毫的影响是难于想象的。就目前可以预见的对计算科学可能产生较大影响的学科而言，物理学中的光学、精细材料科学、哲学中的科学哲学、生物科学中的生物化学、脑科学与神经生理学、行为科学等对计算科学可能会产生较大影响。尽管如此，我们应该清楚地认识到，与计算科学联系最紧密的学科是哲学中的逻辑学，数学中的构造性数学，电学中的（微）电子科学。在不远的将来可能是光电子科学、生物科学中的遗传学和神经生理学，物理和化学科学中的精细材料科学，其影响的切入点主要集中在信息存储、信息传递、认知过程、大规模信息传输的介质和机理方面。3.6计算科学的学科形态与核心概念　每一个学科都有其自身的知识组织结构、学科形态、核心概念和基本工作流程方式。所谓学科形态，是指从事该领域工作的文化方式。对计算科学的深入研究使我们已知该学科存在三种主要的学科形态，即理论、抽象和设计。第一种形态是理论，基于计算科学的数学基础和计算科学理论，广泛采用数学的研究方法。按统一的合理的理论发展过程，包含以下四个步骤：⑴对研究对象的概念抽象（定义）；⑵假设对象的基本性质和对象之间可能存在的关系（定理）；⑶确定这些性质和关系是否正确（证明）；⑷解释结果（与计算机系统或研究对象形成对应）。这个学科形态的基本特征是其研究内容的构造性数学特征，是区别于更广泛的数学科学学科形态的典型特征。第二种形态是抽象，或称模型化，基于计算科学的实验科学方法，广泛采用实验物理学的研究方法。按照对客观现象和规律的实验研究过程，包含以下四个步骤：⑴确定可能世界（环境）并形成假设；⑵构造模型并做出预言；⑶设计实验并收集数据；⑷分析结果。这个学科形态主要出现在计算科学中与硬件设计和实验有关的研究之中。当计算科学理论比较深奥，理解较为困难时，不少科研人员在大致了解理论、方法和技术的情况下，基于经验和技能常以这种学科形态方式开展工作。第三种形态是设计，基于工程，广泛采用工程科学（如建筑工程）的研究方法。按照为解决某一个问题构作系统或装置的过程，包含以下四个步骤：⑴叙述要求；⑵给定技术条件；⑶设计并实现该系统或装置；⑷测试和分析该系统。这个学科形态广泛出现在计算科学中与硬件、软件、应用有关的设计和实现之中。当计算科学理论（包括技术理论）已解决某一问题后，科研人员在正确理解理论、方法和技术的情况下，可以十分有效地以这种学科形态方式开展工作。第二种学科形态抽象，是对客观现象和规律的抽象，是对客观现象和规律的描述和刻划。在这一过程中，与具体客观现象和规律无关或对具体客观现象和规律影响不大的因素被去掉了，其内容构成了计算科学理论的一部分，即技术理论中其内容比较难于用简洁的数学形式描述的那一部分。第一种学科形态理论，也是一种抽象，是对客观现象和规律的数学化、形式化描述，是对能行问题及其求解过程的刻划，其内容构成了计算科学的数学基础和理论计算机科学。本质上，这两种学科形态都是对客观现象和规律的抽象，只是方式的不同。第三种学科形态设计是对计算科学理论的工程化实现。理论和抽象（或称模型化）在本质上的统一，计算科学理论的构造性特征与全部计算科学的核心问题，即能行问题一起决定了计算机科学和计算机工程在本质上并没有区别。对现实世界中被研究的对象进行抽象，建立必要的基本概念，运用数学工具和方法对其进行基础和应用基础研究，研究（对象）概念的基本性质、概念与概念之间的关系，揭示对象发展变化的内在规律，为实验设计和工程设计实现提供方法和技术，并开展实验和工程设计与实现工作是计算科学学科的基本工作流程方式。其中，抽象（主要指抽象化过程）是理论、抽象和设计三个基本学科形态中最重要的一个形态，它是连接学科科学研究与工程应用开发研究的重要环节。在计算科学的研究与开发中，三种学科形态并不是孤立出现的，它们常常交织在一起。经验告诉我们，没有抽象形态的支持，理论研究就失去了背景参照；没有理论的指导，工程开发往往会误入歧途。有许多例子分别表明，抽象和设计阶段出现了理论；理论和设计阶段需要模型化；而理论和抽象阶段离不开设计，它们必须考虑到现实是否能行。三种不同的学科形态实际上反映了在计算科学领域内从事工作的三种文化方式。理论关心的是以形式化或演绎推理的方式揭示对象的性质和相互之间的关系，是一种按照某种科学规律构筑人工科学的典型模式。抽象关心的是以实验方式揭示对象的性质和相互之间的关系。而设计关心的是以生产方式对这些性质和关系的一些特定的实现，完成具体而有用的任务。在计算科学的发展中，有一批在各个分支学科中重复出现的概念。它们虽然在各学科中的具体解释在形式上有差异，但相互之间存在着重要的联系。核心概念是计算科学重要思想、原则、方法、技术过程的集中体现，有助于在学科的深层统一认识计算机科学。对核心概念的深入理解和正确拓展与应用的能力，是计算科学家和工程师成熟的标志之一。核心概念是方法论的重要组成内容，一般具有如下特点：⑴在本学科的不少分支学科中经常出现，甚至在学科中普遍出现；⑵在计算科学理论、抽象和设计这三个过程的各个层面上都有许多示例；⑶在理论上具有可延展和变形的作用，在技术上具有高度的独立性。下面我们筛选和分类给出计算科学的核心概念。当然，某一概念划入一个类并不说明它只在一些分支方向有效，学习中应注意这些概念在不同课程中的具体解释，最好能够通过思考，将这些概念串联起来，把自己所学的专业知识尽可能地系统化。⑴计算模型与能行性计算模型（ComputationalModel），可计算性（Computability），计算复杂性（ComputationalComplexity），最优性（Optimum），相似性与对偶性（SimilarityandDuality）；⑵抽象与构造性描述论域与计算对象（DomainandComputingObject），枚举（Enumeration）与有穷表示（FiniteRepresentation），分层与抽象的级（HierarchyandLevelsofAbstraction），内涵与外延（IntensionandExtension），递归（Recursion），归纳（Induction），自由与约束（FreedomandRestriction）；⑶系统特征相容性（Consistency），完备性（Completeness），单调性（Monotoneity），透明性（Transparence），容错与安全性（Fault-TolerantandSecurity），开放性（Openness），稳定性（Stability），健壮性（Robustness）；⑷计算方法折衷（Compromise），分解（Decomposition），集成（Integration），类比（Analogy），推导（InferenceorReasoning），变换（Transfomation），扩展（ExtensionandExpansion）；⑸实现技术类型（Type），进程与线程（ProcessandThread），顺序与并发（SequenceandConcurrent），软计算结点（Agent）；现役（的）（Active），关联（Binding）与实例化（Instantiation），虚拟（的）（Virtual），编码（Coding），模式匹配（PatternMatching），分杈（Branching），合一（或通代）（Unification），协议（Protocol），循环与迭代（LoopandIteration），重用（Reuse），规范与标准化（Standardization）；3.7计算科学的典型方法与典型实例对于上面所讨论的计算科学中的三种学科形态和在学科中重复出现的核心概念，在将三个过程（学科形态）贯穿在整个学科各门课程教学的始终，用核心概念将各分支学科的内在联系串联起来时，事实上，学科形态与核心概念并不能完全解决问题，还需要于教学中介绍在这门学科中反复出现的具有哲学意义的典型方法，并通过一批典型实例给学生以较深刻的感性认识。典型方法与典型实例是属于方法论的内容。就目前我们对学科的认识，已知有下列几种典型的方法和一大批典型实例。它们是内涵与外延的方法，以递归、归纳和迭代技术形式为代表的构造性方法，公理化方法，快速原型方法，演化方法，以及展开与规约方法。内涵与外延是哲学的两个基本的概念。所谓内涵是指一个概念所反映的事物的本质属性的总和，也就是概念的内容。外延是指概念所界定的所有对象的集合，即所有满足概念定义属性的对象的集合。内涵与外延的方法广泛出现在计算科学的许多分支学科中。这是一个能够对无穷对象的集合作分类处理的方法。例奇数与偶数的定义。奇数与偶数的外延定义：{1,3,5,7,9,...}、{2,4,6,8,10,...}奇数与偶数的内涵定义：{x│x∈N&（xmod2）=1}{x│x∈N&（xmod2）=0}构造性方法是整个计算科学学科最本质的方法。这是一种能够对论域为无穷的客观事物按其有限构造特征进行处理的方法。例谓词逻辑系统中合式公式的定义。(1)F(a1,...,an)是合式公式。其中，ai是表示不空论域中个体的形式符号，即个体词；(2)如果A是合式公式，则A是合式公式；(3)如果A和B是合式公式，则[A∧B]，[A∨B]，[A→B]，[AB]是合式公式；(4)如果A(a)是合式公式，a在其中出现，x不再其中出现，则xA(x)，xA(x)是合式公式。公理化方法也是计算科学的一种典型方法。它能帮助学生认识一个系统如何严格表述，认识到完备性和无矛盾性对一个公理系统的重要性，认识每一条公理深刻的背景，独立性和它的作用。可惜，其深刻的哲学意义、学术深度和理解上的困难性使得它在本科的课程中较少出现。近年来，这一方法出现在一些学科的前沿研究中。除了形式语义学的研究中使用公理化方法外，开放信息系统的思想和设计，自定义逻辑框架系统的研究，以及分布式代数系统的研究都采用了公理化方法或吸取了公理化方法的思想。随着学科发展的深化，预计这一方法还将在一些分支方向上得到运用，并推动学科进一步深入发展。例本书第四章给出的布尔代数的一个公理系统在学科的基础和应用基础的理论研究中，上述三种典型方法是比较常见的学科研究方法。下面，我们介绍在学科的应用研究的工程技术开发研究中使用较多的另外三种典型方法。当然，切不可由此认为某种典型方法仅仅适用于某一类研究而不适用于其他类研究，典型方法在学科的各个层面具有广泛的例示，只是在不同的类别中运用时有的多一些，有的少一些。快速原型方法是计算科学的典型方法。最初，快速原型的思想出现在软件工程的研究之中，其主要内涵是：在软件的开发中，随着程序代码量的日渐庞大，开发费用和周期的不断增长，人们迫切需要对软件开发中引入的新思想、新原理和采用的新方法、新技术的可行性进行验证，通过验证过程提出改进意见，为实际产品的工程技术开发提供原理性的指导。此时，Prolog语言刚刚出现，研究人员惊喜地发现，该语言特别适合充当快速原型实验的验证工具。对于软件开发中系统设计的一种新的构思，采用Prolog语言只对涉及新构思的内容“去粗取精”地开发原理性的验证程序，在证实了新构思确实可行之后，再按照规范的、工程化的要求进行软件的开发，并且在系统的开发中，基本上按照快速原型验证开发中设计的程序设计思想进行细化。这样做，不仅可以避免大型软件系统的开发出现原理性的错误，而且能够提高大型软件开发的速度和质量。由此不难看出，快速原型方法事实上是一种低成本系统原理验证性实验方法。演化方法也是计算科学的典型方法。所谓演化（Evolutation）方法，也叫进化方法，是一种模拟事物演进过程进而求解问题的方法。其主要思想是，针对具体的问题，首先找到解决该问题的办法（或算法、程序、电路等），然后通过各种有效的技术方法改进解决问题的办法（或算法、程序、电路等）进而改进求解的结果。近年来在演化算法基础上发展起来的演化计算是该方法最具代表性的研究领域之一。例如，算法设计与分析中的代数化简方法，程序设计方法学中的程序变换方法，电路设计与分析中通过布尔函数的化简进而简化电路设计的方法，软件维护与升级等都是演化方法的具体应用实例。近年来，演化计算的内涵开始更多地指向以模拟大自然演化过程对一类复杂问题的计算。演化方法在使用时常常与其他典型方法联系在一起。例如，与快速原型和展开方法合用，可以开发一类特殊软件的程序自动生成系统，如人机界面自动生成系统。尽管演化方法实际上在计算科学的发展中早就出现了，其他学科也有类似的方法，但是，学术界在相当长的一个时期内没有注意到该方法的方法学意义。作者认为，演化方法是一种特别适合计算科学的技术方法。随着学科研究与发展的不断深化，人们不可能在软硬件开发和应用中将所有的研究与开发工作都做得十分圆满，万无一失。学科自身知识体系的复杂性决定了今后在研究与开发中需要不断地对先前进行的工作进行改进，不断地完善，这不仅仅是工程技术开发中一个具有普遍规律性的问题，而且，演化方法本身还可能具有重大的、酝酿着学术研究突破价值的科学意义。从近年来演化计算的研究（主要是算法演化计算研究）中出现广泛使用逻辑与代数方法的特点考察和获得联想：如果在计算模型的研究中引入演化计算的方法改造传统的计算模型，或设计新型的计算模型，那么，新计算模型有可能变得具有演化计算能力，表现出某些健壮性的特征，这是否暗示了智能计算系统的研究不必一定要沿着首先发展人工智能的逻辑基础，然后发展智能计算机、智能计算系统的“演化”路线，而存在着一条崭新的、以前从未有人涉足过的研究路线呢？展开与归约是一对技术概念，是在处理实际事务的过程中对两个相向的处理活动所作的一般化的方法学概括。展开的内涵是从一个较为抽象的目标（对象）出发，通过一系列的过程操作或变换，将抽象的目标（对象）转换为具体的细节描述。例如，在程序设计方法学中，从一个程序的规范出发，运用程序推导技术，可以将一个程序一步一步地自动设计出来，这样就实现了对该程序的展开。理论上，一个具体的程序与该程序的规范指称的是同一个对象，语义完全相同，只是表现形式不同。从描述与理解的角度看，前者较为具体，后者较为抽象。规约方法可以视为展开过程的逆过程。不难理解，基于程序规范的“自顶向下”的程序设计方法是一种展开方法，从一个电路系统布尔函数表达式出发到对应的电路系统的实际完成所进行的工作方法也是一种展开方法。“自底向上”的语法分析方法，语义约化方法都是规约方法的实例。典型方法之所以重要，不仅在于它能深刻地揭示出学科的基本规律和各主科目之间内在的联系，而且在于它能启发人们更深入地思考学科的一些深层次的问题，培养学生的创造性能力和科学研究能力。当然。计算科学中还有许多方法也是重要的，如类比推理、证伪发现、统计推断与分析、各种测试方法与测试数据筛选的方法等。但相对于上述六种方法来说，这些方法应用范围比较单一、狭窄，或是哲学意义比较浅显。至于其它的典型方法，还有待人们去整理和总结。所谓典型实例是指那些反映学科某一方面内在规律和典型问题本质内容的实例。典型实例也是方法论的重要组成内容，由于它们往往以简化形式深入浅出地表达学科深奥的科学规律和学科典型问题的本质内容，因此，在学科研究中常常被用来辅助说明思想、原理、方法和技术，用来比较思想、理论、方法和技术的优劣。显然，典型实例在计算科学发展中具有重要的作用。在计算机科学的发展中，经过几十年的研究与积累，人们构思和设计了一大批能够反映各分支学科有代表性的、具有问题本质特性的典型实例。例哲学家共餐问题。设有5个哲学家围坐一张桌。圆桌上放有一盘可自动添加的面条，每2个人之间放有1根筷子，共5根筷子。进一步假设每个哲学家的活动均为一个重复下面动作的进程：⑴    思考问题；⑸    吃面条；⑵    饿了；⑹    放右手的筷子；⑶    拿左手的筷子；⑺    放左手的筷子；⑷    拿右手的筷子；⑻    重新转到思考问题状态⑴。问：怎样协调五个哲学家的活动，才能保证每一个哲学家都能按照他们的进程正常地活动，不致发生某个哲学家因吃不到面条而被饿死。考虑这样一种情况：五个哲学家的进程是并发的。如果每一个哲学家当前都恰好拿到了位于左手边的筷子，等待拿右手边的筷子准备吃面条，那么，由于谁也拿不到右手边的筷子，又不愿意放下左手中的一根筷子，所以，这个系统就处于一种僵死的状态（也叫系统处于死锁状态），最终将导致所有的哲学家饿死。哲学家共餐问题实际上反映了计算机程序设计中多进程共享单个处理机资源时的并发控制问题。要防止这种情况发生，就必须建立一种机制，既要让每一个哲学家都能吃到面条，又不能让任何一个哲学家始终拿着一根筷子不放。采用并发程序语言、Petri网、CSP等工具，都能很容易地解决这个问题。典型实例在计算机软硬件的开发中具有重要的应用价值。我们知道，一个系统开发出来之后，面临着用户的确认和验收。对软硬件中的程序而言，测试程序只能发现程序有错，但不能证明程序无错。然而，采用形式化的方法证明程序的正确性又是一个十分困难的问题，不仅成本高、周期长，而且，对并发程序和并行程序的验证还有一些关键问题尚未解决，怎么办？显然，用长期积累的一批典型实例对程序进行测试是一个比较可行的折衷解决问题的办法，因为程序能够通过测试，意味着程序没有违背人类积累的本学科范围内的“常理”，正确性在一定程度上比较可信。例一组典型实例：停机问题，哲学家共餐问题，饮料问题，最小费用流问题，可满足性问题，货郎担问题，生产与消费问题，文法的二义性问题，上下文语义问题，最小生成树问题，阿克曼函数，鞍点问题，子集和数问题，确定性自动机与不确定性自动机的等价问题，八皇后问题，九宫排定问题，三个中国人算法，0/1背包问题，作业调度问题，路由选择问题，图的最小覆盖问题，荷兰国旗问题，等等。3.8计算科学学科特点、发展规律和趋势计算科学是在数学和电子科学基础上发展起来的一门新兴学科。它既是一门理论性很强的学科，又是一门实践性很强的学科。几十年来学科自身发展的实践表明，一方面，围绕着一些重大的背景问题，各分支学科和方向上取得了一系列重要的理论和技术成果，推动了计算科学向深度和广度发展；另一方面，由于发展了一大批成熟的技术并成功地应用于各行各业，更多的人是把这门科学看成是一种技术。事实上，理论和技术是计算科学两个互为依托的侧面。计算科学的理论绝大多数属于技术理论。学科的基本问题和本质属性决定了计算科学理论、技术与工程相互之间常常界限模糊。从理论探索，技术开发到工程开发应用和生产的周期很短，许多 实验室 17025实验室iso17025实验室认可实验室检查项目微生物实验室标识重点实验室计划 产品和最终投向市场的产品之间几乎没有太大的差别，这在软硬件产品中是屡见不鲜的。虽然，目前整体上理论研究滞后于技术开发，但随着学科研究和应用的不断深化，理论的重要性地位将愈来愈突出，而技术则渐渐退居为次要的位置。因为大量的研究已经表明，象新一代计算机体系结构，NP完全性问题，软件工程，并行计算与处理，计算语言学，人工智能等许多方面的难题，并不是技术问题，而恰恰是理论问题。这些难题基本上都与某些数学理论或工具之间存在着密切的联系，它们的解决将对计算科学的发展产生极其深远的影响。数学是计算科学的主要基础，以离散数学为代表的应用数学是描述学科理论、方法和技术的主要工具，而微电子技术和程序技术则是反映学科产品的主要技术形式。在计算科学中，无论是理论研究还是技术研究的成果，最终目标要体现在计算机软硬件系统产品上。然而，作为硬件产品的计算机系统和作为软件产品的程序指令系统应能机械地，严格地按照程序指令执行，决不能无故出错。计算机系统的这一客观属性和特点决定了计算机的设计、制造、以及各种软件系统开发的每一步都应该是严密的、精确无误的。就目前基于图灵机这一理论计算模型和存储程序式思想设计制造的计算机系统而言，它们只能处理离散问题或可用构造性方式描述的问题，而且这些问题必须对给定的论域存在有穷表示。至于非离散的连续性问题，如实数域上的函数计算，方程求根等还只能用近似的逼近方法。于是，由于计算模型的非连续性（或称离散化）特点，使得以严密、精确著称的数学尤其是离散数学被首选作为描述计算科学的主要工具。在这一学科中，数学与电子技术的结合是理论与技术完美结合的一个成功范例。从事计算科学的人都知道，计算科学中不仅许多理论是用数学描述的，而且许多技术也是用数学描述的。大多数计算科学理论不仅仅是对研究对象变化规律的陈述，而且由于能行性这一本质的核心问题和特点的作用，理论描述中常通过构造性方法折射出技术的思想和步骤，而从理论通过方法跨越到技术则完全取决于对理论的深刻认识和理解。一个人如果看懂了以形式化方法描述的技术文献，自然明白技术上应该怎样去做，否则往往误以为是一种理论，离实现尚远。由于离散数学的构造性特征与反映计算科学本质的能行性之间形成了天然一致，从而使离散数学的构造性特征决定了计算科学的许多理论同时具有理论、技术、工程等多重属性，决定了其许多理论、技术和工程的内容是相互渗透在一起的，是不可分的。与大多数工程科学的工作方式不同，在几乎所有高起点的，有学术深度的计算科学的研究与开发中，试图参照经验科学的工作方式，通过反复实验获得数据，经分析后指导下一步的工作从而推进科研与开发工作的方式是行不通的。原因是有学术深度的问题其复杂性早已大大超出了专家们的直觉和经验所能及的范围。当然，并非所有的计算科学理论研究都具有应用价值。实际上，在计算科学发展的几十年中，有不少计算科学理论研究后来并没有得到继续发展。计算科学并不完全排斥工程的方法。相反，计算科学在发展中广泛采用了其它学科行之有效的工程方法。事实上，从软硬件开发的经济效益和专业技术人才的局限性两方面考虑，完全采用形式化的方法来解决计算科学中的所有问题是不现实的。长期以来，数学，特别是以离散数学为代表的应用数学与计算科学之间建立的密切联系不仅使计算科学具备了坚实的理论基础和科学基础，而且使计算科学从一开始就以一种与其他学科发展方式很不相同的方式发展。这种方式就是抽象描述与具体实现相分离的方式，即在计算科学的发展中，对大量的、各种有深度的问题的处理采用了将理论上解决问题的抽象描述计算方法、算法和技术的内容与具体解决问题的细节、具体实现计算的技术内容相分离。这样做的好处是由于可计算问题能行性的特点和数学方法的构造性特点，也由于计算科学理论的发展落后于技术发展的特点，人们可以更深入地探讨一些已经出现的技术问题的内在规律。一般说来，采用抽象描述方法从理论上解决的问题，实际工作中也是可以解决的。能否根据抽象描述解决具体的实际问题，关键在于能否正确地理解抽象描述的内容，这在计算科学各个分支学科的发展中不胜枚举。例如，对数据结构中各种表的数据处理我们已经建立了一套理论方法。在实际工作中，结合具体问题，一个表究竟是用数组表示，还是用链表等其他数据结构表示，在抽象描述阶段是不必关心的。而在实现阶段，我们虽然可以自己选定具体的表示形式，但是表上的具体操作则完全是在理论方法的指导下完成的。又如，针对一个复杂的可化简的逻辑电路，我们并不是先将这个电路设计、制造出来，然后通过反复试验减少电路的元器件实现化简，而是从一开始就设法先通过抽象这个电路的逻辑表达公式，然后按照逻辑公式的化简方法化简这个电路，最后根据化简结果设计、制造电路。抽象描述与具体实现相分离是计算科学发展过程中一个十分重要的特点，它不仅决定了一大批计算科学工作者的工作方式，而且使计算科学的研究与开发在很短的几十年里就已进入计算科学比较深层的阶段。特别，读者应该注意这样一个事实，计算科学正是在将抽象描述与具体实现相分离的过程中，经过对各种计算模型的深入研究和应用使学科很快走向深入的。由此形成了计算科学发展的另一个重要的特点，也使我们窥见到计算模型在整个学科发展中所起的不可替代的独特作用。计算科学发展的第二个重要的特点是几乎在学科各个方向和各个层面，一旦研究工作走向深入，研究内容具有比较复杂的特点，人们首先是发展相应的计算模型和数学工具，然后依靠计算模型和数学工具将研究工作推向深入。计算机科学的第三个重要的特点是一个问题求解方法和结果的好坏，首先取决于该问题抽象描述及其数据与信息表示的方式而不是施于数据与信息表示之上的操作和其他。随着计算机科学技术的不断发展和学科研究的深化，一方面，对计算模型和各种新型计算机体系结构、人工智能的研究将不断进行下去，另一方面，围绕着各种科学计算和数据处理的计算机应用问题，软件开发方法学，特别是并行与分布式软件开发方法学研究以及各种计算机基本应用技术将成为未来学科发展的主线。3.9计算科学知识组织结构及其演变虽然计算科学的发展在时间上很难划定几个独立的阶段，但粗略地分阶段考察学科的发展及其知识组织结构的演变确能给我们一些启示。在计算科学的研究与发展中，虽然具体地形成了一大批更为细小的方向，有些理论性较强，有些技术性较强，有些则与其它学科产生了密切的联系。但就核心的，在学术上有较深刻内涵，其概念、方法和技术对整个计算科学影响较大的主流方向而言，我们认为，在未来的二十年或更长一点的时间里国内外重要的计算科学学术研究机构将会逐步把研究重点集中在以下几个新的综合方向上：⑴新一代计算机体系结构。该方向包括神经元计算、计算机设计与制造、网络与通信技术（含信息安全技术）、大容量存储设备的研究、容错理论、算法理论、计算模型内容等；⑵并行与分布式软件开发方法学研究。该方向包括数理逻辑、计算理论（包括算法理论）、式语义学、高级语言与程序设计理论（包括程序设计方法学）、系统软件设计、软件工程、容错理论等内容；⑶人工智能理论及其应用。该方向包括数理逻辑、高等逻辑、算法理论、知识工程、神经元计算、人工智能高级语言与人工智能程序设计等内容；⑷计算机应用的关键技术。主要将围绕计算可视化与虚拟现实，计算几何，科学计算这几个重点方向开展工作，并带动数据库技术、计算机图形学、自然语言处理与机器翻译、模式识别与图像处理等方向发展。在这一综合方向上研究内容将几乎覆盖所有计算科学应用技术方向内容无论计算科学在发展中产生了多少新的研究与发展方向，我们应该清醒地认识到，推动计算科学发展的主要动力在于社会广泛的应用需求。发展计算科学各个分支学科方向主要的目的有两个：一个是针对各种实际问题应用背景的特点，希望能够不断地制造出性能更好的计算机系统，包括硬件和软件。为此，必须首先发展软硬件开发的思想、理论、方法、技术和工具；另一个是针对计算机在各行各业中的各类具体应用，为了在计算机系统上更有效地进行科学计算和事务处理，也必须首先发展支持计算机具体应用的各种共性思想、共性理论、共性方法和共性技术。我们还应该清醒地认识到，无论是哪一方面，发展一个学科的思想、理论、方法和技术必定有赖于支持该学科发展的公共知识体系。对这四个综合方向研究的重点内容作分析，结合国外顶尖学术刊物发表的与上述方向研究内容有关的学术 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 ，不难得出，它们共同的基础都趋向集中在数理逻辑（指高等逻辑）、形式语义学、新一代计算机体系结构、算法设计与分析、计算模型与计算理论这五个专业基础之上。具体地说，软件工程的主要基础是程序设计语言理论（主要基础涉及形式语言与自动机理论和形式语义学），形式语义学，高等逻辑（如一阶逻辑，模型论和时序逻辑）和程序设计方法学与程序理论；人工智能的主要基础是数理逻辑与高等逻辑，算法设计与分析；计算语言学的主要基础是数理逻辑与形式语义学，形式语言与自动机理论；而计算机体系结构的主要基础是计算模型与计算理论，算法设计与分析，以及形式语义学；其它方向在学术上有深度的内容从方法论的角度考察，基本上可以在这些内容的基础上发展。研究工作重点的转移实际上揭示了学科的发展和重大突破离不开学科核心知识组织结构中各分支学科的发展和支持，它们是现代计算科学人员所必需的专业基础知识。从知识组织的层次结构和方法论的角度观察，据对计算科学国际领头和重点刊物的分析，当前学科的重点研究几乎都与计算理论（包括算法理论）、体系结构、高等逻辑和形式语义学的内容密切相关。从目前的学科的整体发展情况来看，计算模型与体系结构，软件开发方法学与计算机应用技术是学科未来发展的主要方向，而计算理论（包括算法理论）、体系结构、高等逻辑与形式语义学是支撑学科未来主要方向发展的四大核心专业知识基础。如同50年代数学研究所需的核心专业基础