计算科学导论二.ppt
《计算科学导论二.ppt》由会员分享,可在线阅读,更多相关《计算科学导论二.ppt(88页珍藏版)》请在三一文库上搜索。
1、2019/4/25,1,计算科学导论(二) 计算机与信息学院 蒋川群 13002187038 2012年10月,2019/4/25,2,目录,计算学科中的数学方法 数学的基本特征 数学方法的作用 计算学科中常用的数学概念和术语 证明方法 递归和迭代 计算学科中的系统科学方法 系统科学与系统科学方法 软件开发中使用系统科学方法的原因,2019/4/25,3,计算学科中的数学方法,数学有连续数学和离散数学之分,离散数学源于算术,连续数学源于几何。 连续数学以微积分为基础,用连续的观点,对数学进行研究,对自然科学的各种现象进行描述,从而成为人们认识客观世界的一个重要工具。,2019/4/25,4,
2、计算学科中的数学方法,计算学科的根本问题是“能行性”问题,决定了计算机本身的结构和它处理的对象都是离散型的,而连续型的问题只有经过“离散化”的处理后才能被计算机处理。 在计算学科中,采用的数学方法主要是离散数学的方法。,2019/4/25,5,计算学科中的数学方法,理论上,凡是能用离散数学为代表的构造性数学方法描述的问题,当该问题所涉及的论域为有穷或虽为无穷但存在有穷表示时,这个问题一定能用计算机来处理。 凡是能被计算机处理的问题都可以转换为一个数学问题。,2019/4/25,6,计算学科中的数学方法,数学家关心的是“是什么(What is it)”的问题,重点放在数学本身的性质上; 计算学家
3、不仅要知道“是什么”的问题,更要解决“怎么做(How to do it)”的问题。 在计算领域,人们又创造了基于离散数学的“具体”数学的大量概念和方法(如学科中的各种形式化方法)。,2019/4/25,7,数学的基本特征,数学是研究世界的空间形式和数量关系的一门学科。 1)高度的抽象性:抽象是任何一门科学乃至全部人类思维都具有的特性,数学的抽象程度大大超过自然科学中一般的抽象,仅保留其量的关系和空间的形式。,2019/4/25,8,数学的基本特征,数学是研究世界的空间形式和数量关系的一门学科。 2)逻辑的严密性:数学高度的抽象性和逻辑的严密性是紧密相关的;在运用数学工具解决问题时,只有严格遵守
4、形式逻辑的基本法则,充分保证逻辑的可靠性,才能保证结论的正确性。 3)普遍的适用性:数学的高度抽象性决定了它的普遍适用性。,2019/4/25,9,数学方法的作用,1)为科学技术研究提供简洁精确的形式化语言 数学模型就是运用数学的形式化语言在观测和实验的基础上建立起来的,它有助于人们认识和把握超出感性经验之外的客观世界。 2)为科学技术研究提供数量分析和计算的方法 一门科学要从定性分析发展到定量分析,数学方法从中起了杠杆的作用。,2019/4/25,10,数学方法的作用,3)为科学技术研究提供逻辑推理的工具 数学的逻辑严密性这一特点使它成为建立一种理论体系的手段,在这方面最有意义的就是公理化方
5、法。 数学逻辑用数学方法研究推理过程,把逻辑推理形式加以公理化、符号化,为建立和发展科学的理论体系提供有效的工具。,2019/4/25,11,计算学科中常用的数学概念和术语,集合 函数和关系 代数系统 字母表、字符串和语言 定义、定理和证明 必要条件和充分条件,2019/4/25,12,计算学科中常用的数学概念和术语,1、集合 集合是数学的基本概念,它是构造性数学方法的基础。 定义:集合就是一组无重复的对象的全体,集合中的对象称为集合的元素。,2019/4/25,13,计算学科中常用的数学概念和术语,2、函数和关系 函数又称映射,是指把输入转变成输出的运算,该运算也可理解为从某一“定义域”的对
6、象到某一“值域”的对象的映射。 函数是程序设计的基础,程序定义了计算函数的方法,而定义函数的方法又影响着程序语言的设计,好的程序设计语言一般都便于函数的计算。,2019/4/25,14,计算学科中常用的数学概念和术语,3、代数系统 对于一个非空集合A,可以定义,任意一个由AA到A的映射称为集合A上的一个二元运算,An到A的映射则称为集合A上的一个n元运算。 由集合A以及连同若干定义在该集合上的运算:f1,f2,fn所组成的系统称为代数系统,该系统可以形式化的描述为: ,2019/4/25,15,计算学科中常用的数学概念和术语,代数系统 布尔代数是英国数学家和逻辑学家布尔1847年创立的,最初用
7、来研究逻辑思想的法则。 1938年,麻省理工学院香农在他的硕士论文中分析并指出:布尔代数可以用电路来实现,并可指导电路的设计。,2019/4/25,16,计算学科中常用的数学概念和术语,代数系统 香农的分析源于继电器的使用,与传统开关不同,继电器用电来控制开关的闭合,输出的电压是由输入的电压决定的,若设通电为1,断电为0,就能与布尔代数的两个值联系起来。 为了实现布尔代数的“与”、“或”、“非”3种运算,研制和生产了与之相应的3种门电路(与门、或门、非门),2019/4/25,17,计算学科中常用的数学概念和术语,4、字母表、字符串和语言 所有的计算机程序设计语言都是形式语言,其构成基础同一般
8、自然语言一样,也是符号或字母。 常用符号:数字、大小写字母、括号、运算符等 有限字母表指的是由有限个任意符号组成的非空集合,简称为字母表,用表示。字母表上的元素称为字符或符号,用小写字母或数字表示,如:a、b、c、1、2、3等,2019/4/25,18,计算学科中常用的数学概念和术语,字母表、字符串和语言 字母表理解为计算机输入键盘上符号的集合。字母可以理解为键盘上的每一个英文字母、数字、标点符号、运算符号等。 字符串,也称符号串,指的是由字符组成的有限序列,常用小写希腊字母表示。 语言指的是给定字母表上的字符串的集合。,2019/4/25,19,计算学科中常用的数学概念和术语,字母表、字符串
9、和语言 语言、文法以及自动机有着密切的关系。 语言由文法产生,文法是一种数学模型,是建立在有限集合上的一组变换(运算)。 根据代数系统的定义,也可以将文法看作是一种代数系统,而语言正是由这种代数系统产生的。,2019/4/25,20,计算学科中常用的数学概念和术语,字母表、字符串和语言 计算机使用的语言是一种形式语言,形式语言与自动机理论密切相关,并构成计算机科学重要的理论基础。 在形式语言与自动机理论中,语言又可分为:短语结构语言、上下文有关语言、上下文无关语言和正规语言,分别由0型文法、1型文法、2型文法和3型文法产生。,2019/4/25,21,计算学科中常用的数学概念和术语,字母表、字
10、符串和语言 自动机是识别语言的数学模型,各类文法所对应的自动机分别是图灵机、线性有界自动机、下推自动机和有限状态自动机。 语言与数学模型不是一一对应的关系,一种语言可以由不同的文法产生,也可以由不同的自动机识别。,2019/4/25,22,计算学科中常用的数学概念和术语,5、定义、定理和证明 定义、定理和证明是数学的核心,也是计算学科理论形态的核心内容 定义是蕴含在公理系统之中的概念和命题 定理是被证明为真的数学命题 证明是为使人们确信一个命题为真而作的一种逻辑论证,2019/4/25,23,计算学科中常用的数学概念和术语,定义、定理和证明 定义是数学的灵魂,定理和证明是数学的精髓 若能像图灵
11、给出“计算”的形式化定义那样给出“智能”的定义,那么,“智能”的本质将被揭示,“智能”领域也将产生一个质的飞跃,2019/4/25,24,证明方法,直接证明和间接证明法 反证法 归纳法 构造证明法,2019/4/25,25,证明方法,直接证明和间接证明法 直接证明:假设p为真,通过使用公理或已证明的定理以及正确的推理规则证明q也为真,以此证明蕴含式pq为真。 间接证明:因为蕴含式pq与其逆否命题qp等价,因此可以通过证明qp来证明蕴含式pq为真。,2019/4/25,26,证明方法,反证法 首先假定一个与原命题相反的命题成立,然后通过正确的推理得出与已知(或假设)条件、公理、已证过的定理等相互
12、矛盾或自相矛盾的结果,以此证明原命题正确。,2019/4/25,27,证明方法,归纳法 所谓归纳法,是指从特殊推理出一般的一种证明方法。 不完全归纳法是根据部分特殊情况作出推理的一种方法,该方法多用于无穷对象的论证,然而,论证的结果不一定正确。,2019/4/25,28,证明方法,归纳法 完全归纳法也称穷举法,它是对命题中存在的所有特殊情况进行考虑的一种方法,用该方法论证的结果是正确的,然而,它只能用于“有限”对象的论证。 数学归纳法是一种用于证明与自然数n有关的命题正确性的证明方法,该方法能用“有限”的步骤解决无穷对象的论证问题。,2019/4/25,29,证明方法,归纳法 数学归纳法的基本
13、原理 假定对一切正整数n,有一个命题P(n),若以下证明成立,则P(n)为真: 归纳基础:证明P(1)为真; 归纳步骤:证明对任意的i1,若P(i)为真,则P(i+1)为真。,2019/4/25,30,证明方法,构造证明法 存在性证明 存在一个 x 使命题P(x)成立可表示为:存在xP(x)。 构造性证明 通过找出一个使得命题P(a)为真的元素a,从而完成该函数值的存在性证明。 构造性的证明方法,对于要解决的问题,不光要证明该问题解的存在,还要给出解决该问题的具体步骤,这种步骤往往就是对解题算法的描述。,2019/4/25,31,递归与迭代,递归关系 一个数列的若干连续项之间 的关系 递归数列
14、 由递归关系所确定的数列 递归过程 调用自身的过程 递归算法 包含递归过程的算法 递归程序 直接或间接调用自身的程序 递归方法 在有限的步骤内,根据特定 的法则或公式对一个或多个前面的元素进行运算,以确定一系列元素的方法,2019/4/25,32,递归与迭代,数学归纳法是一种论证方法,递归是算法和程序设计的一种实现技术。涉及递归定义的证明通常采用数学归纳法。 递归不仅应用于算法和程序设计之中,它还广泛地应用于定义序列、函数和集合等各个方面。,2019/4/25,33,递归与迭代,“迭代”就是反复替换。 迭代程序都可以转换为与它等价的递归程序,反之,则不然。就效率而言,递归程序的实现要比迭代程序
15、的实现耗费更多的时间和空间。因此,在具体实现时,又希望尽可能将递归程序转化为等价的迭代程序。,2019/4/25,34,计算学科中的系统科学方法,系统科学方法是指利用系统的观点来认识和处理问题的各种方法的总称。 模型方法是系统科学的基本方法,研究系统具体来说就是研究它的模型。模型是对系统原型的抽象,是科学认识的基础和决定性环节。 模型与实现是认识与实践的一种具体体现,在计算学科中,它反映了抽象、理论和设计3个过程的基本内容。模型与实现包括建模、验证和实现3方面的内容。,2019/4/25,35,系统科学和系统科学方法,系统科学起源于对传统数学、物理学和天文学的研究,诞生于20世纪40年代 系统
16、科学的崛起被认为是20世纪现代科学的两个重大突破性成就之一 建立在系统科学基础上的系统科学方法开辟了探索科学技术的新思路,它是认识、调控、改造和创造复杂系统的有效手段,它为系统形式化模型的构建提供了有效的中间过渡模式,2019/4/25,36,系统科学和系统科学方法,现代计算机普遍采用的组织结构,即冯.诺依曼计算机组织结构就是系统科学在计算机领域所取得的应用成果之一 随着计算技术的迅猛发展,计算机软硬件系统变得越来越复杂,因此,系统科学方法在计算学科中的作用也越来越大,2019/4/25,37,系统科学和系统科学方法,系统科学的基本概念 系统科学遵循的一般原则 常用的几种系统科学方法 实例,2
17、019/4/25,38,系统科学和系统科学方法,系统科学的基本概念 系统科学是探索系统的存在和运动变化规律的学问,是对系统本质的理性认识,是人们认识客观世界的一个知识体系。,2019/4/25,39,系统科学和系统科学方法,系统科学的基本概念 系统和子系统 结构和结构分析 层次和层次分析 环境、行为和功能 状态、演化和过程 系统同构,2019/4/25,40,系统科学和系统科学方法,系统科学的基本概念 系统和子系统 系统是指由相互联系、相互作用的若干元素构成的、具有特定功能的统一整体。 S= A表示系统S中所有元素的集合 R表示系统S中所有元素之间关系的集合,2019/4/25,41,系统科学
18、和系统科学方法,系统科学的基本概念 系统和子系统 一个大的系统往往是复杂的,通常可以划分为一系列较小的系统,这些系统称为子系统。 Si= SiS,AiA,RiR,2019/4/25,42,系统科学和系统科学方法,系统科学的基本概念 结构和结构分析 结构是指系统内各组成部分(元素和子系统)之间相互联系、相互作用的框架 结构分析的重要内容就是划分子系统,并研究各子系统之间的相互关系,2019/4/25,43,系统科学和系统科学方法,系统科学的基本概念 层次和层次分析 层次是划分系统结构的一个重要工具,也是结构分析的主要方式。 系统的结构可以表示为各级子系统和系统要素的层次结构形式。 高层次包含和支
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 科学 导论
链接地址:https://www.31doc.com/p-2635224.html