计算科学内容和方法

《计算科学内容和方法》由会员分享，可在线阅读，更多相关《计算科学内容和方法（178页珍藏版）》请在金锄头文库上搜索。

1、第五章 计算科学内容和方法,李陶深 ,第5章计算学科的内容 与方法,5.1 计算科学的基本问题,能行性,能行性：什么能（有效地）自动进行，什么不能（有效地）自动进行。 “能行性”这个计算学科的根本问题决定了计算机本身的结构和它处理的对象都是离散型的，甚至许多连续型的问题也必须在转化为离散型问题以后才能被计算机处理。例如，计算定积分就是把它变成离散量，再用分段求和的方法来处理的。,计算科学的发展主线,具体来说，有三大问题：1）计算的平台和环境问题（计算模型问题）2）计算过程的能行操作和效率问题（算法问题）3）计算的正确性问题（语义学问题） 计算机研究的目标是:拓展和提高计算机的应用领域和应用水平

2、。围绕学科的三个基本问题使学科的发展形成了三条相对独立的主线，形成了许多相对独立的分支学科和研究方向。不同时期，围绕着学科的一些重大问题和基本问题，若干方向便构成了所谓的主流方向，由主流方向又形成了学科的发展主线。,计算的平台与环境问题,计算的平台与环境问题是指描述计算问题的计算模型，或者实际制造出来的针对各种待处理问题特点和要求的自动计算机器。不难看出，理论研究中提出的各种计算模型，各种实际的计算机系统，各种高级程序设计语言，各种计算机体系结构，各种软件开发工具与环境，编译程序与操作系统，数据库系统等都是围绕这一基本问题发展而来的，其内容实质可归结为计算的模型问题，也就是说，这个基本问题实际

3、上关心的是计算问题在理论上是否能行的问题。,计算过程的能行操作与效率问题,含义是：当一个问题在判明为可计算的性质后，从具体解决这个问题着眼，必须按照能行可构造的特点与要求，给出实际解决该问题的一步一步的具体操作，同时还必须确保这样一种过程的开销成本是我们能够承受的。相关的分支学科有：数值与非数值计算方法，算法设计与分析，结构化程序设计技术，密码学与快速算法，演化计算，程序设计方法学，自动布线，RISC技术，人工智能的逻辑基础等。,计算的正确性问题,计算的正确性是指：一个计算问题在给出了能行操作序列并解决了其效率问题之后，必须确保计算的正确性，否则，计算是无意义的，也是容易产生不利影响的。这一基

4、本问题相关的分支学科有：算法理论，程序设计方法学，程序设计语言的语义学，进程代数与分布式事件代数，程序测试技术，电路测试技术，软件工程技术，计算语言学，容错理论与技术，Petri网理论，CSP理论，CCS理论，分布式网络协议等。今天，计算的正确性问题常常归结为各种语言的语义问题。,计算科学的三大基本问题,计算学科的三个基本问题普遍出现在学科的各个分支学科和研究方向之中，是学科研究与发展中经常面对而又必须解决的问题。循着这一线索，我们不难看出，整个学科正是在围绕这些基本问题和不同时期重大问题而展开的研究与发展中形成了学科的发展主线与主流方向。,第5章计算学科的内容 与方法,5.2 计算科学内容的

5、三个层面,计算科学的应用层,包括人工智能应用与系统，信息、管理与决策系统，移动计算、计算可视化、科学计算等计算机应用的各个方向。其中，人工智能应用与系统涵盖人工智能，机器人，神经元计算，知识工程，自然语言处理与机器翻译，自动推理等方向；信息、管理与决策系统涵盖数据库设计与数据管理技术，数据表示与存储（包括多媒体技术），数据与信息检索，管理信息系统，计算机辅助系统，决策系统等方向；计算可视化涵盖计算机图形学，计算几何，模式识别与图像处理等方向。,计算科学的专业基础层,它是为应用层提供技术和环境的一个层面，包括软件开发方法学，计算机网络与通信技术，程序设计科学，计算机体系结构，电子计算机系统基础。

6、其中，软件开发方法学涵盖顺序、并行与分布式软件开发方法学，如软件工程技术，软件开发工具和环境等方向；计算机网络与通信技术涵盖计算机网络互联技术，数据通信技术，以及信息保密与安全技术等方向；程序设计科学涵盖数据结构技术，数值与符号计算，算法设计与分析，程序设计语言，程序设计语言的文法与语义，程序设计方法学，程序理论等方向；电子计算机系统基础涵盖数字逻辑技术，计算机组成原理，故障诊断与器件测试技术，操作系统，编译技术，数据库系统实现技术，容错技术等方向。,计算科学的基础层,它包括计算的数学理论，高等逻辑等内容。其中，计算的数学理论涵盖可计算性（递归论）与计算复杂性理论，形式语言与自动机理论，形式语

7、义学（主要指代数语义，公理语义等），Petri网理论等方向；高等逻辑涵盖模型论，各种非经典逻辑与公理集合论等方向。支撑这三个层面的是计算科学这一学科的理工科基础科目，包括物理学（主要是电子技术科学）、基础数学（含离散数学）等。,移动计算与全球定位 计算机自动控制 计算机辅助制造 计算机集成制造系统 计算 机器人 计算可视化与虚拟现实 数据与信息检索 计算机创作 计算机网络应用软件 科学 科学计算 多媒体信息系统 计算机辅助设计 信息、管理与决策系统 自然语言处理 应用 模式识别与图像处理技术 计算机图形学 计算几何 人工智能与知识工程 层 数据表示与存储 网络与开放系统互联标准 软件测试技术

8、人机工程学（人机界面） 计算 软件开发方法学: 软件工程技术、程序设计方法学、软件开发工具和环境、软件开发规范 科学 编码理论 密码学 计算机体系结构 程序理论 数据表示理论与数据库系统 专业 电子计算机系统基础 计算机接口与通信 计算机网络与数据通信技术 自动推理 基础 故障诊断与器件测试技术 容错技术 汇编技术 操作系统 高级语言 程序设计 层 数字系统设计 符号计算与计算机代数 数据结构技术 算法设计与分析 编译与解释技术 计算 控制论基础 数字系统设计基础 信息论基础 网论（Petri网理论等） 形式语义学 科学 框图理论 算法理论 可计算性（递归论） 计算复杂性 程序设计语言理论 基

9、础 计算模型（各种抽象机） 模型论与非经典逻辑 公理集合论 形式语言与自动机 层 数学 光电子技术基础 电路基础 电子线路基础 数字与模拟电路基础 数值分析与计算方法 与 大学物理学 函数论基础（复变函数、演算、泛函分析等） 泛代数 概率与数理统计 物理 常微分方程 偏微分方程 集合论与图论 组合数学 抽象代数 数理逻辑基础 层 空间解析几何 数学分析 布尔代数 高等代数 数论,第5章计算学科的内容 与方法,5.3 计算科学的发展主线,计算科学的发展主线,在计算机基础研究、应用基础研究和技术开发与应用的研究中，计算学科逐步发展形成了三条相对独立的主线：1）计算模型与计算机系统2）计算模型、语言

10、与软件开发方法学3）应用数学与计算机应用,第5章计算学科的内容 与方法,5.4 计算科学的分类与分支学科简介,构造性数学基础,对数学基础问题的讨论促进了构造性数学的产生和发展，产生了数学发展史上著名的三大逻辑学派：逻辑主义学派，形式主义学派和直觉主义逻辑学派。尽管数学科学的发展在计算科学的发展中得到广泛的应用，但是与计算科学在科学方法论上形成一致的是构造性数学。这是直觉主义所以受到计算科学家欢迎的原因。可以这么说：历史上，对计算的能行性和可构造性研究的最著名的产物要数图灵机。如果没有19世纪末20世纪初关于数学基础问题的讨论，没有直觉主义学派对数学的贡献，计算科学可能要推迟出现。,构造性数学基

11、础,数理逻辑与抽象代数是计算科学最重要的两项数学基础，它们的研究思想和研究方法在计算科学许多有深度的领域得到了最广泛的应用。数理逻辑是研究推理的科学，特别，在过去主要是研究数学中推理的科学。数理逻辑与哲学有着密切的联系，其哲学方面是形式逻辑，而形式逻辑的数学化方面构成了数理逻辑的研究内容。,构造性数学基础,在计算科学的研究和发展中，应该接受什么样的数学理论呢？罗宾逊认为，如果大家不对一个数学理论的可解释性提出非议，那么，有几条通常被看作是基本的可接受性的准则：(1) 一个数学理论，仅当它是协调的，或称无矛盾的，才能被看作是可接受的；(2) 一个数学理论是可接受的，要是它能够作为自然科学的一个基

12、础；(3) 一个数学理论要由美学标准来判断，比如它的美或内在的适当性。 (3)中提及的标准，迄今还无从进行任何科学的研究。,构造性数学基础,对于(1)中提出的标准，足可以使我们认识到数理逻辑对计算科学的重要性。众所周知，在计算科学的各个分支学科中，使用了各种数学理论，包括数理逻辑。要保证一个数学理论是协调的，或称无矛盾的，实际上是要保证该数学理论对客观世界或应用范畴的（语义）解释是无矛盾的，用逻辑学的术语来说就是该数学理论必须存在模型。这在方法论上是靠逻辑学中的模型理论提供的。而要学习模型论的内容，仅有命题演算、一阶谓词演算的知识是不够的。对于(2)中提及的标准，读者在今后的学习中会逐步体会到

13、其涵义。,构造性数学基础,现在，有经验和成熟的计算科学家都知道，除了数理逻辑以外，对计算科学最重要的数学分支是代数，特别是抽象代数。在计算科学中，代数方法被广泛应用于许多分支学科。例如，可计算性与计算复杂性，形式语言与自动机理论，密码学，算法理论，数据表示理论，网络与通信理论，Petri网理论，程序理论，形式语义学等许多方面都离不开代数。,计算的数学理论,所谓计算的数学理论是指一切关于能行性问题的数学理论的总和。也有一种更具体的定义是指一切关于计算与计算模型问题的数学理论的总和。计算理论广义的可以看作同计算的数学理论，狭义的主要指算法理论、可计算理论、计算复杂性理论。,计算机组成原理、器件与体

14、系结构,计算机组成原理与设计是计算机发展的一个主流方向。这一方向的主要任务是根据各种计算模型研究计算机的工作原理，并按照器件、设备和工艺条件设计、制造具体的计算机。早期计算机的设计是建立在分离元器件的基础之上，这方面的工作更多的是集中在对各个部件微观的精细分析，后来，随着集成电路技术的进步，工作的重点已开始转到计算机的组织结构。集成电路对电路和功能部件的高集成度和计算机设计与软件开发之间建立的密切关系，使这一方向的发展逐步形成了一个新的计算机体系结构方向。,计算机应用基础,要开展各个领域的各种计算机具体应用，就必须首先要有一些计算机应用基础知识。对计算科学专业的学生来说，计算机应用基础知识包括

15、算法基础、程序设计、数据结构、数据库基础、微机原理与接口技术等。,计算机基本应用技术,我们知道，计算机应用和计算机基本应用技术是一回事，涉及到的分支学科很多。然而，从计算机应用的定义和科学方法论的角度出发，大致可以将计算机应用分支学科的范畴确定下来，即它所研究的内容在方法和技术上为计算机在各个领域的具体应用奠定了基础。,软件基础,软件是计算科学一个较大的学科门类，包括众多的分支学科方向，主要有高级程序设计语言、数据结构理论、程序设计原理、编译程序原理与编译系统实现技术、数据库原理与数据库管理系统、操作系统原理与实现技术、软件工程技术、程序设计方法学、各种应用软件等。,新一代计算机体系结构与软件开发方法学,所谓新一代计算机体系结构是相对于过去的体系结构而言的。目前，对这类体系结构的研究内容很多，主要是各种新型并行计算机的体系结构、集群式计算机体系结构，体系结构的可扩展性、任务级并性、指令级并行性、动态可改变结构等方面的内容，也有一些内容还不成熟，正在发展之中。高起点的软件开发方法学的主要基础是新一代计算机体系结构、高等逻辑、形式语义学、计算模型理论以及算法基础。这实际上也指出了新一代计算机体系结构与软件开发方法学（包括并行与分布式计算机系统、人工智能计算机系统、并行与分布式软件开发方法学等）是计算科学界需要长期努力奋斗的工作重点。,