《华中科技大学-计算机科学与技术方法论-5计算学科中的数学方法》由会员分享，可在线阅读，更多相关《华中科技大学-计算机科学与技术方法论-5计算学科中的数学方法(15页珍藏版)》请在人人文库网上搜索。
1、第5章 计算学科中的数学方法,理论上，凡能被计算机处理的问题均可以转换为一个数学问题，凡能以离散数学为代表的构造性数学方法描述的问题，当该问题所涉及的论域为有穷，或者为无穷但存在有穷表示时，这个问题也一定能用计算机来处理。,一、数学的基本特征及数学方法的作用(P97-P98) 二、计算学科中常用的数学概念和术语,集合(已讲) 函数和关系,论域：一定场合(语境)中思考和议论所涉及的对象的范围。即某一范围内被论及对象的全部所构成的集合。,个体：可以独立存在的物体。 谓词：用来刻画个体的性质，或关系的词，刻画 一个个体性质的词为一元谓词，刻画几个 个体之间关系的词称为n元谓词。,(1)谓词：充当谓语。
2、(说明主语“怎么样”，“是什么”) 和能同副词结合的动词、形容词(辞海)。 (Predicate，谓词、断言),命题：一个能分辩真假的陈述句称作一个命题 量词：全称量词 ：所有的 存在量词 ：存在,(2)谓词逻辑：将命题分解为主词、谓词和量词，研究 其形式结构，导出有关的逻辑形式和规 律的逻辑理论(辞海)。,(3)函数(映射)：把输入变成输出的运算，f (a)=b (4)关系,定义，(见上次课)A1A2 An中的任一 子集称为A1, A2, , An的一个几元关系。 二元关系： A1A2 的一个子系。有序对。 P100，例，选课关系：R=(张, 文)，(张, 哲)， (李, 数)，(李, 艺)。
3、，(王, 史)，( 王, 文),二元关系中的特例：集合A上的关系：AA (A到A自身的关系)，A2。 例 A=0, 1, 2, 3，则 =(0, 0), (0 3), (2 0), (2, 1), (2, 3), (3, 2)是A 上的一个关系。 例 实数集R，1=(x, y)|(x, y) R2, xy, 1是R 上的“小于”关系，x1y。,集合A上的关系性质 设是集合A上的关系。 若对于所有的 a A。有aa，则称是自反的。 对于所有的 a, b A，若每当有ab就有ba， 则称 是对称的。 对于所有的a, b, c A，若每当有ab和bc就有 ac，则称是可传递的。,等价关系：集合A上的。
4、关系 ，如果它是自反、对 称且可传递的，则称为A上的等价关系。 如：集合元素中的相等关系，直线之间的平行关 系，三角形的相似关系，位同一条街的居民 之间的关系等。,等价类 设是A上的等价关系，若ab成立，则a等价 于b(在下)。 定义：设是A上的等价关系，则A中等价于a 的全 体元素的集合称为a所生成的等价类。 记为a=b|bA, ab 例 5.6，“同余关系”是等价关系 例 5.7，“并发关系”是非等价关系,字母、字符和语言。 布尔逻辑(P102-P103),蕴含：命题P与命题Q组成的复合命题，P Q ：“如果 那么”，“如果必须”，“必须 以便” P ：前件，Q：后件。 P Q真值表：,当P为假时，Q无论真假，PQ总为真。,定义、定理和证明。,三、证明方法,直接证明与间接证明 反证法 归纳法。P (1) (n) (P(n) P(n+1) nP(n). 构造性证明,四、递归和迭代,定义：P106 复习汉诺塔h(n)=2h(n-1)+1,(3)递归过程：调用自身的过程。 (4)递归算法：包含递归过程的算法。 an= can-1+ g(n) , n=2, 3, 4, 递归是算法和程序设计的一种实现技术，数学归纳法是递归的基础。,五、公理化方法,六、形式化方法,符号化 + 抽象公理化。
科学技术方法论在计算机 华中科技大学-计算机科学与技术方法论-5计算学科中的数学方法...
