资源描述:
《计算学科中的数学方法.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第5章计算学科中的数学方法理论上,凡能被计算机处理的问题均可以转换为一个数学问题,凡能以离散数学为代表的构造性数学方法描述的问题,当该问题所涉及的论域为有穷,或者为无穷但存在有穷表示时,这个问题也一定能用计算机来处理。一、数学的基本特征及数学方法的作用(P97-P98)二、计算学科中常用的数学概念和术语集合(已讲)函数和关系论域:一定场合(语境)中思考和议论所涉及的对象的范围。即某一范围内被论及对象的全部所构成的集合。个体:可以独立存在的物体。谓词:用来刻画个体的性质,或关系的词,刻画一个个体性质的词为一元谓词,刻画几个个体之间关系的词称为n元谓词。(1
2、)谓词:充当谓语(说明主语“怎么样”,“是什么”)和能同副词结合的动词、形容词(辞海)。(Predicate,谓词、断言)命题:一个能分辩真假的陈述句称作一个命题量词:全称量词:所有的存在量词:存在(2)谓词逻辑:将命题分解为主词、谓词和量词,研究其形式结构,导出有关的逻辑形式和规律的逻辑理论(辞海)。(3)函数(映射):把输入变成输出的运算,f(a)=b(4)关系定义,(见上次课)A1×A2×…×An中的任一子集称为A1,A2,…,An的一个几元关系。二元关系:A1×A2的一个子系。有序对。P100,例,选课关系:R={(张,文),(张,哲),(李
3、,数),(李,艺),(王,史),(王,文)}}二元关系中的特例:集合A上的关系:A×A(A到A自身的关系),A2。例A={0,1,2,3},则={(0,0),(03),(20),(2,1),(2,3),(3,2)}是A上的一个关系。例实数集R,1={(x,y)
4、(x,y)R2,x<y},1是R上的“小于”关系,x1y。集合A上的关系性质设是集合A上的关系。①若对于所有的aA。有aa,则称是自反的。②对于所有的a,bA,若每当有ab就有ba,则称是对称的。③对于所有的a,b,cA,若每当有ab和bc就有ac,则称是可传递
5、的。等价关系:集合A上的关系,如果它是自反、对称且可传递的,则称为A上的等价关系。如:集合元素中的相等关系,直线之间的平行关系,三角形的相似关系,位同一条街的居民之间的关系等。等价类设是A上的等价关系,若ab成立,则a等价于b(在下)。定义:设是A上的等价关系,则A中等价于a的全体元素的集合称为a所生成的等价类。记为[a]={b
6、bA,ab}例5.6,“同余关系”是等价关系例5.7,“并发关系”是非等价关系字母、字符和语言。布尔逻辑(P102-P103)蕴含:命题P与命题Q组成的复合命题,PQ:“如果…那么”,“如果…必须”,“必须
7、…以便”P:前件,Q:后件。PQ真值表:当P为假时,Q无论真假,PQ总为真。定义、定理和证明。PQ01011011PQ101000=1(1)01=1(1)10=0(0)11=1(1)三、证明方法直接证明与间接证明反证法归纳法。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,…递归是算法和程序设计的一种实现技术,数学归纳法是递归的基础。递归的定义
8、功能例,文法G的生成式(规则)S0A1。A01,递归基础A1=01A0A1递归步骤An=0An-11L(G)={0n1n
9、n≥1}定义一种语言例,阿克曼函数n+1若m=0A(m,n)=A((m-1),1)若n=0A(m-1,A(m,n-1))若m,n>03.迭代反复替换迭代程序递归程序转换五、公理化方法公理系统的要求例(P110)元矛盾性独立性完备性六、形式化方法符号化+抽象公理化