计算科学内容和方法精选文档.ppt

《计算科学内容和方法精选文档.ppt》由会员分享，可在线阅读，更多相关《计算科学内容和方法精选文档.ppt（178页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算科学内容和方法本讲稿第一页，共一百七十八页第第5章计算学科的内容章计算学科的内容 与方法与方法5.1 计算科学的基本问题本讲稿第二页，共一百七十八页能行性能行性o能能行行性性：什什么么能能（有有效效地地）自自动动进进行行，什什么么不不能（有效地）自动进行。能（有效地）自动进行。o“能能行行性性”这这个个计计算算学学科科的的根根本本问问题题决决定定了了计计算算机机本本身身的的结结构构和和它它处处理理的的对对象象都都是是离离散散型型的的，甚甚至至许许多多连连续续型型的的问问题题也也必必须须在在转转化化为为离离散散型型问题以后才能被计算机处理。问题以后才能被计算机处理。o例例如如，计计算算定定积

2、积分分就就是是把把它它变变成成离离散散量量，再再用用分段求和的方法来处理的。分段求和的方法来处理的。本讲稿第三页，共一百七十八页计算科学的发展主线计算科学的发展主线o具体来说，有三大问题：具体来说，有三大问题：具体来说，有三大问题：具体来说，有三大问题：n1）计算的平台和环境问题（计算模型问题）计算的平台和环境问题（计算模型问题）n2）计算过程的能行操作和效率问题（算法问题）计算过程的能行操作和效率问题（算法问题）n3）计算的正确性问题（语义学问题）计算的正确性问题（语义学问题）o计算机研究的目标是计算机研究的目标是:拓展和提高计算机的应用领域和应拓展和提高计算机的应用领域和应拓展和提高计算机

3、的应用领域和应拓展和提高计算机的应用领域和应用水平。用水平。用水平。用水平。o围绕学科的三个基本问题使学科的发展形成了三条相对围绕学科的三个基本问题使学科的发展形成了三条相对独立的主线，形成了许多相对独立的分支学科和研究方独立的主线，形成了许多相对独立的分支学科和研究方向。向。oo不同时期，围绕着学科的一些重大问题和基本问题，若干方不同时期，围绕着学科的一些重大问题和基本问题，若干方不同时期，围绕着学科的一些重大问题和基本问题，若干方不同时期，围绕着学科的一些重大问题和基本问题，若干方向便构成了所谓的主流方向，由主流方向又形成了学科的发向便构成了所谓的主流方向，由主流方向又形成了学科的发向便构

4、成了所谓的主流方向，由主流方向又形成了学科的发向便构成了所谓的主流方向，由主流方向又形成了学科的发展主线。展主线。展主线。展主线。本讲稿第四页，共一百七十八页计算的平台与环境问题计算的平台与环境问题o计计算算的的平平台台与与环环境境问问题题是是指指描描述述计计算算问问题题的的计计算算模模型型，或或者者实实际际制制造造出出来来的的针针对对各各种种待待处理问题特点和要求的自动计算机器。处理问题特点和要求的自动计算机器。o不不难难看看出出，理理论论研研究究中中提提出出的的各各种种计计算算模模型型，各各种种实实际际的的计计算算机机系系统统，各各种种高高级级程程序序设设计计语语言言，各各种种计计算算机机

5、体体系系结结构构，各各种种软软件件开开发发工工具具与与环环境境，编编译译程程序序与与操操作作系系统统，数数据据库库系系统统等等都都是是围围绕绕这这一一基基本本问问题题发发展展而而来来的的，其其内内容容实实质质可可归归结结为为计计算算的的模模型型问问题题，也也就就是是说说，这这个个基基本本问问题题实实际际上上关关心心的的是是计计算算问问题在理论上是否能行的问题。题在理论上是否能行的问题。本讲稿第五页，共一百七十八页计算过程的能行操作与效率问题计算过程的能行操作与效率问题o含含义义是是：当当一一个个问问题题在在判判明明为为可可计计算算的的性性质质后后，从从具具体体解解决决这这个个问问题题着着眼眼，

6、必必须须按按照照能能行行可可构构造造的的特特点点与与要要求求，给给出出实实际际解解决决该该问问题题的的一一步步一一步步的的具具体体操操作作，同同时时还还必必须须确确保保这样一种过程的开销成本是我们能够承受的。这样一种过程的开销成本是我们能够承受的。o相相关关的的分分支支学学科科有有：数数值值与与非非数数值值计计算算方方法法，算算法法设设计计与与分分析析，结结构构化化程程序序设设计计技技术术，密密码码学学与与快快速速算算法法，演演化化计计算算，程程序序设设计计方方法法学学，自自动动布布线线，RISC技技术术，人人工工智智能能的的逻逻辑辑基础等。基础等。本讲稿第六页，共一百七十八页计算的正确性问题

7、计算的正确性问题o计计算算的的正正确确性性是是指指：一一个个计计算算问问题题在在给给出出了了能能行行操操作作序序列列并并解解决决了了其其效效率率问问题题之之后后，必必须须确确保保计计算算的的正正确确性性，否否则则，计计算算是是无无意意义义的，也是容易产生不利影响的。的，也是容易产生不利影响的。o这这一一基基本本问问题题相相关关的的分分支支学学科科有有：算算法法理理论论，程程序序设设计计方方法法学学，程程序序设设计计语语言言的的语语义义学学，进进程程代代数数与与分分布布式式事事件件代代数数，程程序序测测试试技技术术，电电路路测测试试技技术术，软软件件工工程程技技术术，计计算算语语言言学学，容容错

8、错理理论论与与技技术术，Petri网网理理论论，CSP理理论论，CCS理论，分布式网络协议等。理论，分布式网络协议等。o今今天天，计计算算的的正正确确性性问问题题常常常常归归结结为为各各种种语语言的语义问题。言的语义问题。本讲稿第七页，共一百七十八页计算科学的三大基本问题计算科学的三大基本问题o计计算算学学科科的的三三个个基基本本问问题题普普遍遍出出现现在在学学科科的的各各个个分分支支学学科科和和研研究究方方向向之之中中，是是学学科科研研究究与发展中经常面对而又必须解决的问题。与发展中经常面对而又必须解决的问题。o循循着着这这一一线线索索，我我们们不不难难看看出出，整整个个学学科科正正是是在在

9、围围绕绕这这些些基基本本问问题题和和不不同同时时期期重重大大问问题题而而展展开开的的研研究究与与发发展展中中形形成成了了学学科科的的发发展展主主线与主流方向。线与主流方向。本讲稿第八页，共一百七十八页第第5章计算学科的内容章计算学科的内容 与方法与方法5.2 计算科学内容的三个层面本讲稿第九页，共一百七十八页计算科学的应用层计算科学的应用层o包包括括人人工工智智能能应应用用与与系系统统，信信息息、管管理理与与决决策策系系统统，移移动动计计算算、计计算算可可视视化化、科科学学计计算算等等计计算算机机应应用用的的各各个个方方向向。其其中中，人人工工智智能能应应用用与与系系统统涵涵盖盖人人工工智智能

10、能，机机器器人人，神神经经元元计计算算，知知识识工工程程，自自然然语语言言处处理理与与机机器器翻翻译译，自自动动推推理理等等方方向向；信信息息、管管理理与与决决策策系系统统涵涵盖盖数数据据库库设设计计与与数数据据管管理理技技术术，数数据据表表示示与与存存储储（包包括括多多媒媒体体技技术术），数数据据与与信信息息检检索索，管管理理信信息息系系统统，计计算算机机辅辅助助系系统统，决决策策系系统统等等方方向向；计计算算可可视视化化涵涵盖盖计计算算机机图图形形学学，计计算几何，模式识别与图像处理等方向。算几何，模式识别与图像处理等方向。本讲稿第十页，共一百七十八页计算科学的专业基础层计算科学的专业基础

11、层o它它是是为为应应用用层层提提供供技技术术和和环环境境的的一一个个层层面面，包包括括软软件件开开发发方方法法学学，计计算算机机网网络络与与通通信信技技术术，程程序序设设计计科科学学，计计算算机机体体系系结结构构，电电子子计计算算机机系系统统基基础础。其其中中，软软件件开开发发方方法法学学涵涵盖盖顺顺序序、并并行行与与分分布布式式软软件件开开发发方方法法学学，如如软软件件工工程程技技术术，软软件件开开发发工工具具和和环环境境等等方方向向；计计算算机机网网络络与与通通信信技技术术涵涵盖盖计计算算机机网网络络互互联联技技术术，数数据据通通信信技技术术，以以及及信信息息保保密密与与安安全全技技术术等

12、等方方向向；程程序序设设计计科科学学涵涵盖盖数数据据结结构构技技术术，数数值值与与符符号号计计算算，算算法法设设计计与与分分析析，程程序序设设计计语语言言，程程序序设设计计语语言言的的文文法法与与语语义义，程程序序设设计计方方法法学学，程程序序理理论论等等方方向向；电电子子计计算算机机系系统统基基础础涵涵盖盖数数字字逻逻辑辑技技术术，计计算算机机组组成成原原理理，故故障障诊诊断断与与器器件件测测试试技技术术，操操作作系系统统，编编译译技技术术，数数据据库库系系统统实现技术，容错技术等方向。实现技术，容错技术等方向。本讲稿第十一页，共一百七十八页计算科学的基础层计算科学的基础层o它它包包括括计计

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

14、离散数学）等。术科学）、基础数学（含离散数学）等。本讲稿第十二页，共一百七十八页 移动计算与全球定位移动计算与全球定位 计算机自动控制计算机自动控制 计算机辅助制造计算机辅助制造 计算机集成制造系统计算机集成制造系统 计算计算 机器人机器人 计算可视化与虚拟现实计算可视化与虚拟现实 数据与信息检索数据与信息检索 计算机创作计算机创作 计算机网络应用软件计算机网络应用软件 科学科学 科学计算科学计算 多媒体信息系统多媒体信息系统 计算机辅助设计计算机辅助设计 信息、管理与决策系统信息、管理与决策系统 自然语言处理自然语言处理 应用应用 模式识别与图像处理技术模式识别与图像处理技术 计算机图形学计

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

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

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

18、 集合论与图论集合论与图论 组合数学组合数学 抽象代数抽象代数 数理逻辑基础数理逻辑基础 层层 空间解析几何空间解析几何 数学分析数学分析 布尔代数布尔代数 高等代数高等代数 数论数论本讲稿第十三页，共一百七十八页第第5章计算学科的内容章计算学科的内容 与方法与方法5.3 计算科学的发展主线本讲稿第十四页，共一百七十八页计算科学的发展主线计算科学的发展主线o在计算机基础研究、应用基础研究和技术开发在计算机基础研究、应用基础研究和技术开发与应用的研究中，计算学科逐步发展形成了三与应用的研究中，计算学科逐步发展形成了三条相对独立的主线：条相对独立的主线：n1）计算模型与计算机系统）计算模型与计算机

19、系统n2）计算模型、语言与软件开发方法学）计算模型、语言与软件开发方法学n3）应用数学与计算机应用）应用数学与计算机应用本讲稿第十五页，共一百七十八页第第5章计算学科的内容章计算学科的内容 与方法与方法5.4 计算科学的分类与分支学科简介本讲稿第十六页，共一百七十八页构造性数学基础构造性数学基础o对数学基础问题的讨论促进了构造性数学的产生和发展，对数学基础问题的讨论促进了构造性数学的产生和发展，产生了数学发展史上著名的三大逻辑学派：逻辑主义学产生了数学发展史上著名的三大逻辑学派：逻辑主义学派，形式主义学派和直觉主义逻辑学派。派，形式主义学派和直觉主义逻辑学派。oo尽管数学科学的发展在计算科学的

20、发展中得到广泛的应用，尽管数学科学的发展在计算科学的发展中得到广泛的应用，尽管数学科学的发展在计算科学的发展中得到广泛的应用，尽管数学科学的发展在计算科学的发展中得到广泛的应用，但是与计算科学在科学方法论上形成一致的是构造性数学。但是与计算科学在科学方法论上形成一致的是构造性数学。但是与计算科学在科学方法论上形成一致的是构造性数学。但是与计算科学在科学方法论上形成一致的是构造性数学。这是直觉主义所以受到计算科学家欢迎的原因。这是直觉主义所以受到计算科学家欢迎的原因。这是直觉主义所以受到计算科学家欢迎的原因。这是直觉主义所以受到计算科学家欢迎的原因。o可以这么说：历史上，对计算的能行性和可构造性

21、研究可以这么说：历史上，对计算的能行性和可构造性研究的最著名的产物要数图灵机。如果没有的最著名的产物要数图灵机。如果没有1919世纪末世纪末世纪末世纪末20202020世纪初世纪初关于数学基础问题的讨论，没有直觉主义学派对数学的关于数学基础问题的讨论，没有直觉主义学派对数学的贡献，计算科学可能要推迟出现。贡献，计算科学可能要推迟出现。本讲稿第十七页，共一百七十八页构造性数学基础构造性数学基础o数理逻辑与抽象代数是计算科学最重要的两数理逻辑与抽象代数是计算科学最重要的两项数学基础，它们的研究思想和研究方法在项数学基础，它们的研究思想和研究方法在计算科学许多有深度的领域得到了最广泛的计算科学许多有

22、深度的领域得到了最广泛的应用。应用。o数理逻辑是研究推理的科学，特别，在过去数理逻辑是研究推理的科学，特别，在过去主要是研究数学中推理的科学。数理逻辑与主要是研究数学中推理的科学。数理逻辑与哲学有着密切的联系，其哲学方面是形式逻哲学有着密切的联系，其哲学方面是形式逻辑，而形式逻辑的数学化方面构成了数理逻辑，而形式逻辑的数学化方面构成了数理逻辑的研究内容。辑的研究内容。本讲稿第十八页，共一百七十八页构造性数学基础构造性数学基础oo在计算科学的研究和发展中，应该接受什么样的数学理论呢在计算科学的研究和发展中，应该接受什么样的数学理论呢在计算科学的研究和发展中，应该接受什么样的数学理论呢在计算科学的

23、研究和发展中，应该接受什么样的数学理论呢？罗宾逊认为，如果大家不对一个数学理论的可解释性提出？罗宾逊认为，如果大家不对一个数学理论的可解释性提出？罗宾逊认为，如果大家不对一个数学理论的可解释性提出？罗宾逊认为，如果大家不对一个数学理论的可解释性提出非议，那么，有几条通常被看作是基本的可接受性的准则：非议，那么，有几条通常被看作是基本的可接受性的准则：非议，那么，有几条通常被看作是基本的可接受性的准则：非议，那么，有几条通常被看作是基本的可接受性的准则：n n(1)(1)一个数学理论，仅当它是协调的，或称无矛盾的，才能被看作一个数学理论，仅当它是协调的，或称无矛盾的，才能被看作一个数学理论，仅当

24、它是协调的，或称无矛盾的，才能被看作一个数学理论，仅当它是协调的，或称无矛盾的，才能被看作是可接受的；是可接受的；是可接受的；是可接受的；n n(2)(2)一个数学理论是可接受的，要是它能够作为自然科学的一个一个数学理论是可接受的，要是它能够作为自然科学的一个一个数学理论是可接受的，要是它能够作为自然科学的一个一个数学理论是可接受的，要是它能够作为自然科学的一个基础；基础；基础；基础；n n(3)(3)一个数学理论要由美学标准来判断，比如它的美或内在的适一个数学理论要由美学标准来判断，比如它的美或内在的适一个数学理论要由美学标准来判断，比如它的美或内在的适一个数学理论要由美学标准来判断，比如它

25、的美或内在的适当性。当性。当性。当性。n n o(3)(3)中提及的标准，迄今还无从进行任何科学的研究。中提及的标准，迄今还无从进行任何科学的研究。中提及的标准，迄今还无从进行任何科学的研究。中提及的标准，迄今还无从进行任何科学的研究。本讲稿第十九页，共一百七十八页构造性数学基础构造性数学基础o对于对于对于对于(1)(1)中提出的标准，足可以使我们认识到数理逻辑对中提出的标准，足可以使我们认识到数理逻辑对中提出的标准，足可以使我们认识到数理逻辑对中提出的标准，足可以使我们认识到数理逻辑对计算科学的重要性。计算科学的重要性。计算科学的重要性。计算科学的重要性。o众所周知，在计算科学的各个分支学科

26、中，使用了各众所周知，在计算科学的各个分支学科中，使用了各种数学理论，包括数理逻辑。要保证一个数学理论是种数学理论，包括数理逻辑。要保证一个数学理论是协调的，或称无矛盾的，实际上是要保证该数学理论协调的，或称无矛盾的，实际上是要保证该数学理论对客观世界或应用范畴的（语义）解释是无矛盾的，对客观世界或应用范畴的（语义）解释是无矛盾的，用逻辑学的术语来说就是该数学理论必须存在模型。用逻辑学的术语来说就是该数学理论必须存在模型。这在方法论上是靠逻辑学中的模型理论提供的。而要这在方法论上是靠逻辑学中的模型理论提供的。而要学习模型论的内容，仅有命题演算、一阶谓词演算的学习模型论的内容，仅有命题演算、一阶

27、谓词演算的知识是不够的。知识是不够的。o对于对于(2)(2)中提及的标准，读者在今后的学习中会逐步中提及的标准，读者在今后的学习中会逐步体会到其涵义。体会到其涵义。本讲稿第二十页，共一百七十八页构造性数学基础构造性数学基础o现在，有经验和成熟的计算科学家都知道，现在，有经验和成熟的计算科学家都知道，除了数理逻辑以外，对计算科学最重要的数除了数理逻辑以外，对计算科学最重要的数学分支是代数，特别是学分支是代数，特别是抽象代数抽象代数。o在计算科学中，代数方法被广泛应用于许多在计算科学中，代数方法被广泛应用于许多分支学科。例如，可计算性与计算复杂性，分支学科。例如，可计算性与计算复杂性，形式语言与自

28、动机理论，密码学，算法理论，形式语言与自动机理论，密码学，算法理论，数据表示理论，网络与通信理论，数据表示理论，网络与通信理论，PetriPetri网理网理论，程序理论，形式语义学等许多方面都离论，程序理论，形式语义学等许多方面都离不开代数。不开代数。本讲稿第二十一页，共一百七十八页计算的数学理论计算的数学理论o所谓计算的数学理论是指一切关于能行性问题所谓计算的数学理论是指一切关于能行性问题的数学理论的总和。也有一种更具体的定义是的数学理论的总和。也有一种更具体的定义是指一切关于计算与计算模型问题的数学理论的指一切关于计算与计算模型问题的数学理论的总和。总和。o计算理论广义的可以看作同计算的数

29、学理论，计算理论广义的可以看作同计算的数学理论，狭义的主要指算法理论、可计算理论、计算复狭义的主要指算法理论、可计算理论、计算复杂性理论。杂性理论。本讲稿第二十二页，共一百七十八页计算机组成原理、器件与体系结构计算机组成原理、器件与体系结构o计算机组成原理与设计是计算机发展的一个主计算机组成原理与设计是计算机发展的一个主流方向。这一方向的主要任务是根据各种计算流方向。这一方向的主要任务是根据各种计算模型研究计算机的工作原理，并按照器件、设模型研究计算机的工作原理，并按照器件、设备和工艺条件设计、制造具体的计算机。备和工艺条件设计、制造具体的计算机。o早期计算机的设计是建立在分离元器件的基础早期

30、计算机的设计是建立在分离元器件的基础之上，这方面的工作更多的是集中在对各个部之上，这方面的工作更多的是集中在对各个部件微观的精细分析，后来，随着集成电路技术件微观的精细分析，后来，随着集成电路技术的进步，工作的重点已开始转到计算机的组织的进步，工作的重点已开始转到计算机的组织结构。结构。o集成电路对电路和功能部件的高集成度和计算集成电路对电路和功能部件的高集成度和计算机设计与软件开发之间建立的密切关系，使这机设计与软件开发之间建立的密切关系，使这一方向的发展逐步形成了一个新的计算机体系一方向的发展逐步形成了一个新的计算机体系结构方向。结构方向。本讲稿第二十三页，共一百七十八页计算机应用基础计算

31、机应用基础o要开展各个领域的各种计算机具体应用，就必要开展各个领域的各种计算机具体应用，就必须首先要有一些计算机应用基础知识。对计算须首先要有一些计算机应用基础知识。对计算科学专业的学生来说，计算机应用基础知识包科学专业的学生来说，计算机应用基础知识包括算法基础、程序设计、数据结构、数据库基括算法基础、程序设计、数据结构、数据库基础、微机原理与接口技术等。础、微机原理与接口技术等。本讲稿第二十四页，共一百七十八页计算机基本应用技术计算机基本应用技术o我们知道，计算机应用和计算机基本应用技术我们知道，计算机应用和计算机基本应用技术是一回事，涉及到的分支学科很多。然而，从是一回事，涉及到的分支学科

32、很多。然而，从计算机应用的定义和科学方法论的角度出发，计算机应用的定义和科学方法论的角度出发，大致可以将计算机应用分支学科的范畴确定下大致可以将计算机应用分支学科的范畴确定下来，即它所研究的内容在方法和技术上为计算来，即它所研究的内容在方法和技术上为计算机在各个领域的具体应用奠定了基础。机在各个领域的具体应用奠定了基础。本讲稿第二十五页，共一百七十八页软件基础软件基础o软件是计算科学一个较大的学科门类，包括众软件是计算科学一个较大的学科门类，包括众多的分支学科方向，主要有高级程序设计语言、多的分支学科方向，主要有高级程序设计语言、数据结构理论、程序设计原理、编译程序原理数据结构理论、程序设计原

33、理、编译程序原理与编译系统实现技术、数据库原理与数据库管与编译系统实现技术、数据库原理与数据库管理系统、操作系统原理与实现技术、软件工程理系统、操作系统原理与实现技术、软件工程技术、程序设计方法学、各种应用软件等。技术、程序设计方法学、各种应用软件等。本讲稿第二十六页，共一百七十八页新一代计算机体系结构与软件开发方法学新一代计算机体系结构与软件开发方法学o所谓新一代计算机体系结构是相对于过去的体系结构而言所谓新一代计算机体系结构是相对于过去的体系结构而言所谓新一代计算机体系结构是相对于过去的体系结构而言所谓新一代计算机体系结构是相对于过去的体系结构而言的。目前，对这类体系结构的研究内容很多，主

34、要是各种的。目前，对这类体系结构的研究内容很多，主要是各种的。目前，对这类体系结构的研究内容很多，主要是各种的。目前，对这类体系结构的研究内容很多，主要是各种新型并行计算机的体系结构、集群式计算机体系结构，体新型并行计算机的体系结构、集群式计算机体系结构，体新型并行计算机的体系结构、集群式计算机体系结构，体新型并行计算机的体系结构、集群式计算机体系结构，体系结构的可扩展性、任务级并性、指令级并行性、动态可系结构的可扩展性、任务级并性、指令级并行性、动态可系结构的可扩展性、任务级并性、指令级并行性、动态可系结构的可扩展性、任务级并性、指令级并行性、动态可改变结构等方面的内容，也有一些内容还不成熟

35、，正在发改变结构等方面的内容，也有一些内容还不成熟，正在发改变结构等方面的内容，也有一些内容还不成熟，正在发改变结构等方面的内容，也有一些内容还不成熟，正在发展之中。展之中。展之中。展之中。o高起点的软件开发方法学的主要基础是新一代计算机体高起点的软件开发方法学的主要基础是新一代计算机体系结构、高等逻辑、形式语义学、计算模型理论以及算系结构、高等逻辑、形式语义学、计算模型理论以及算法基础。这实际上也指出了新一代计算机体系结构与软法基础。这实际上也指出了新一代计算机体系结构与软件开发方法学（包括并行与分布式计算机系统、人工智件开发方法学（包括并行与分布式计算机系统、人工智能计算机系统、并行与分布

36、式软件开发方法学等）是计能计算机系统、并行与分布式软件开发方法学等）是计算科学界需要长期努力奋斗的工作重点。算科学界需要长期努力奋斗的工作重点。本讲稿第二十七页，共一百七十八页第第5章计算学科的内容章计算学科的内容 与方法与方法5.5 计算学科中的数学方法5.5.1 数学的基本特征本讲稿第二十八页，共一百七十八页数学方法数学方法o是是指指解解决决数数学学问问题题的的策策略略、途途径径和和步步骤骤，它它是是计算学科中最根本的研究方法。计算学科中最根本的研究方法。o理理论论上上，凡凡能能被被计计算算机机处处理理的的问问题题均均可可以以转转换换为为一一个个数数学学问问题题，换换言言之之，所所有有能能

37、被被计计算算机机处处理的问题均可以用数学方法解决理的问题均可以用数学方法解决；o反反之之，凡凡能能以以离离散散数数学学为为代代表表的的构构造造性性数数学学方方法法描描述述的的问问题题，当当该该问问题题所所涉涉及及的的论论域域为为有有穷穷，或或虽虽为为无无穷穷但但存存在在有有穷穷表表示示时时，这这个个问问题题也也一一定能用计算机来处理。定能用计算机来处理。本讲稿第二十九页，共一百七十八页数学的基本特征数学的基本特征o高度的抽象性高度的抽象性：量的关系和空间的形式：量的关系和空间的形式 o逻辑的严密性逻辑的严密性：严格遵守形式逻辑的基本法则，：严格遵守形式逻辑的基本法则，充分保证逻辑的可靠性，才能

38、保证结论的正确充分保证逻辑的可靠性，才能保证结论的正确性。性。o普遍的适用性普遍的适用性：数学的高度抽象性决定了它的：数学的高度抽象性决定了它的普遍适用性。普遍适用性。本讲稿第三十页，共一百七十八页 数学方法的作用数学方法的作用o为科学技术研究提供简洁精确的形式化语言为科学技术研究提供简洁精确的形式化语言 o为科学技术研究提供数量分析和计算的方法为科学技术研究提供数量分析和计算的方法o为科学技术研究提供了逻辑推理的工具为科学技术研究提供了逻辑推理的工具 本讲稿第三十一页，共一百七十八页5.5计算学科中的数学计算学科中的数学 方法方法5.5.2 为什么说数理逻辑和代数是计算科学的主要基础本讲稿第

39、三十二页，共一百七十八页为什么什么说数理数理逻辑和代数是和代数是计算科学的主要基算科学的主要基础？oo(1)(1)(1)(1)首先，从计算模型和可计算性的研究来看，可计算函数首先，从计算模型和可计算性的研究来看，可计算函数首先，从计算模型和可计算性的研究来看，可计算函数首先，从计算模型和可计算性的研究来看，可计算函数和可计算谓词（一种能够能行判定其真值的断言或逻辑公和可计算谓词（一种能够能行判定其真值的断言或逻辑公和可计算谓词（一种能够能行判定其真值的断言或逻辑公和可计算谓词（一种能够能行判定其真值的断言或逻辑公式）是等价的，相互之间可以转化。这就是说，计算可以式）是等价的，相互之间可以转化。

40、这就是说，计算可以式）是等价的，相互之间可以转化。这就是说，计算可以式）是等价的，相互之间可以转化。这就是说，计算可以用函数演算来表达，也可以用逻辑系统来表达。作为计算用函数演算来表达，也可以用逻辑系统来表达。作为计算用函数演算来表达，也可以用逻辑系统来表达。作为计算用函数演算来表达，也可以用逻辑系统来表达。作为计算模型可以计算的函数恰好与可计算谓词是等价的，而且，模型可以计算的函数恰好与可计算谓词是等价的，而且，模型可以计算的函数恰好与可计算谓词是等价的，而且，模型可以计算的函数恰好与可计算谓词是等价的，而且，数理逻辑本身的研究也广泛使用代数方法，同时，逻辑系数理逻辑本身的研究也广泛使用代数

41、方法，同时，逻辑系数理逻辑本身的研究也广泛使用代数方法，同时，逻辑系数理逻辑本身的研究也广泛使用代数方法，同时，逻辑系统又能通过自身的无矛盾性保证这样一种计算模型是合理统又能通过自身的无矛盾性保证这样一种计算模型是合理统又能通过自身的无矛盾性保证这样一种计算模型是合理统又能通过自身的无矛盾性保证这样一种计算模型是合理的。由此可见，作为一种数学形式系统，图林机及其与它的。由此可见，作为一种数学形式系统，图林机及其与它的。由此可见，作为一种数学形式系统，图林机及其与它的。由此可见，作为一种数学形式系统，图林机及其与它等价的计算模型的逻辑基础是坚实的。等价的计算模型的逻辑基础是坚实的。等价的计算模型

42、的逻辑基础是坚实的。等价的计算模型的逻辑基础是坚实的。本讲稿第三十三页，共一百七十八页为什么什么说数理数理逻辑和代数是和代数是计算科学的主要基算科学的主要基础？o(2)(2)实际计算机的设计与制造中，使用数字实际计算机的设计与制造中，使用数字逻辑技术实现计算机的各种运算的理论基础逻辑技术实现计算机的各种运算的理论基础是代数和布尔代数。布尔代数只是在形式演是代数和布尔代数。布尔代数只是在形式演算方面使用了代数的方法，其内容的实质仍算方面使用了代数的方法，其内容的实质仍然是逻辑。依靠代数操作实现的指令系统具然是逻辑。依靠代数操作实现的指令系统具有（原始）递归性，而数字逻辑技术和集成有（原始）递归性

43、，而数字逻辑技术和集成电路技术只是计算机系统的一种产品的技术电路技术只是计算机系统的一种产品的技术形式。形式。本讲稿第三十四页，共一百七十八页为什么什么说数理数理逻辑和代数是和代数是计算科学的主要基算科学的主要基础？o(3)(3)从计算机程序设计语言方面考察，语言从计算机程序设计语言方面考察，语言的理论基础是形式语言、自动机与形式语义的理论基础是形式语言、自动机与形式语义学。而形式语言、自动机和形式语义学所采学。而形式语言、自动机和形式语义学所采用的主要研究思想和方法来源于数理逻辑和用的主要研究思想和方法来源于数理逻辑和代数。程序设计语言中的许多机制和方法，代数。程序设计语言中的许多机制和方法

44、，如子程序调用中的参数代换、赋值等都出自如子程序调用中的参数代换、赋值等都出自数理逻辑的方法。此外，在语言的语义研究数理逻辑的方法。此外，在语言的语义研究中，四种语义方法最终可归结为代数和逻辑中，四种语义方法最终可归结为代数和逻辑的方法。这就是说，数理逻辑和代数为语言的方法。这就是说，数理逻辑和代数为语言学提供了方法论的基础。学提供了方法论的基础。本讲稿第三十五页，共一百七十八页为什么什么说数理数理逻辑和代数是和代数是计算科学的主要基算科学的主要基础？o(4)(4)在计算机体系结构的研究中，象容错计在计算机体系结构的研究中，象容错计算机系统、算机系统、TransputerTransputer计

45、算机、阵列式向量计算机、阵列式向量计算机、可变结构的计算机系统结构及其计计算机、可变结构的计算机系统结构及其计算模型等都直接或间接与逻辑与代数密不可算模型等都直接或间接与逻辑与代数密不可分。如容错计算机的重要基础之一是多值逻分。如容错计算机的重要基础之一是多值逻辑，辑，TransputerTransputer计算机的理论基础是计算机的理论基础是CSPCSP理论，理论，阵列式向量计算机必须以向量运算为基础，阵列式向量计算机必须以向量运算为基础，可变结构的计算机系统结构及其计算模型主可变结构的计算机系统结构及其计算模型主要采用逻辑与代数的方法。要采用逻辑与代数的方法。本讲稿第三十六页，共一百七十八

46、页为什么什么说数理数理逻辑和代数是和代数是计算科学的主要基算科学的主要基础？o(5)(5)从计算机各种应用的程序设计方面考察，从计算机各种应用的程序设计方面考察，任何一个可在存储程序式电子数字计算机上任何一个可在存储程序式电子数字计算机上运行的程序，其对应的计算方法首先都必须运行的程序，其对应的计算方法首先都必须是构造性的，数据表示必须离散化，计算操是构造性的，数据表示必须离散化，计算操作必须使用逻辑或代数的方法进行，这些，作必须使用逻辑或代数的方法进行，这些，都应体现在算法和程序之中。此外，到现在都应体现在算法和程序之中。此外，到现在为止，程序的语义及其正确性的理论基础仍为止，程序的语义及其

47、正确性的理论基础仍然是数理逻辑，或进一步的模型论。然是数理逻辑，或进一步的模型论。本讲稿第三十七页，共一百七十八页为什么什么说数理数理逻辑和代数是和代数是计算科学的主要基算科学的主要基础？o 高等代数和一般抽象代数只解决了个体对高等代数和一般抽象代数只解决了个体对象为简单个体的论域上的大量运算问题，但象为简单个体的论域上的大量运算问题，但是对具有结构特征和属性成分的复杂个体的是对具有结构特征和属性成分的复杂个体的论域上的运算问题，表达和处理是不方便的，论域上的运算问题，表达和处理是不方便的，常常是有困难的。针对这类对象的运算操作常常是有困难的。针对这类对象的运算操作及其正确性等语义学问题，有必

48、要发展泛代及其正确性等语义学问题，有必要发展泛代数和高阶逻辑理论。数和高阶逻辑理论。本讲稿第三十八页，共一百七十八页5.5计算学科中的数学计算学科中的数学 方法方法5.5.3 计算学科中常用的数学概念和术语本讲稿第三十九页，共一百七十八页集合集合o n构造性数学方法的基础。构造性数学方法的基础。n集合就是一组无重复的对象的全体。集合就是一组无重复的对象的全体。n集合中的对象称为集合的元素。集合中的对象称为集合的元素。n如：计算机专业学生全部必修课程可以组成一个集如：计算机专业学生全部必修课程可以组成一个集合，其中的每门课程就是这一集合中的元素。合，其中的每门课程就是这一集合中的元素。本讲稿第四

49、十页，共一百七十八页函数函数o函数又称映射，是指把输入转变成输出的运算，函数又称映射，是指把输入转变成输出的运算，该运算也可理解为从某一该运算也可理解为从某一“定义域定义域”的对象到的对象到某一某一“值域值域”的对象的映射。函数是程序设计的对象的映射。函数是程序设计的基础，程序定义了计算函数的算法，而定义的基础，程序定义了计算函数的算法，而定义函数的方法又影响着程序语言的设计，好的程函数的方法又影响着程序语言的设计，好的程序设计语言一般都便于函数的计算。序设计语言一般都便于函数的计算。o设设f f为一个函数，当输入值为为一个函数，当输入值为a a时输出值为时输出值为b b，则记作：则记作：本讲

50、稿第四十一页，共一百七十八页关系关系o关系是一个谓词，其定义域为关系是一个谓词，其定义域为关系是一个谓词，其定义域为关系是一个谓词，其定义域为k元组的集合。通常的关系元组的集合。通常的关系为二元关系，其定义域为有序对的集合，在这个集合中，为二元关系，其定义域为有序对的集合，在这个集合中，我们说有序对的第一个元素和第二个元素有关系。如学我们说有序对的第一个元素和第二个元素有关系。如学生选课生选课 学生学生学生学生 课程课程课程课程 成绩成绩成绩成绩 张三张三 文学文学 90 张三张三张三张三 哲学哲学哲学哲学 9595 李四李四李四李四 数学数学数学数学 80 李四李四李四李四 艺术艺术艺术艺术