离散数学集合映射运算省公共课一等奖全国赛课获奖课件.pptx
《离散数学集合映射运算省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《离散数学集合映射运算省公共课一等奖全国赛课获奖课件.pptx(206页珍藏版)》请在咨信网上搜索。
1、离散数学离散数学Discrete Mathematics邓辉文编著邓辉文编著清华大学出版社清华大学出版社普通高等教育普通高等教育“十二五十二五”国家级规划教材国家级规划教材http:/ 孤孤立立:社社会会网网络络(social networks)研研究究人人与与人人之之间间关关系系,Internet研研究究计计算算机机之之间间关系关系,WWW研究网页之间关系研究网页之间关系,第4页离散数学就是研究离散对象及其之间关系离散数学就是研究离散对象及其之间关系学科学科.实际上实际上,科学研究任务就是发觉对象之间内科学研究任务就是发觉对象之间内在关系和规律在关系和规律.第5页本讲内容本讲内容什么是离散数
2、学什么是离散数学1计算机专业为何要学离散数学计算机专业为何要学离散数学2离散数学基本内容离散数学基本内容3学习离散数学方法学习离散数学方法4离散数学学习资源离散数学学习资源5第6页2、计算机专业为何要学离散数学、计算机专业为何要学离散数学第7页(1)当今计算机处理对象均离散当今计算机处理对象均离散:0和和1.(2)为后继专业课程学习作知识上准备为后继专业课程学习作知识上准备.(3)培养各种能力培养各种能力:抽象思维能力抽象思维能力,逻辑思维逻辑思维能力能力,计算思维计算思维(computational thinking,Jeannette M.Wing)能力能力,.(4)(教育部教育部,)离散
3、数学是计算机各专业离散数学是计算机各专业专业专业基础课基础课.第8页程序设计语言程序设计语言离散数学离散数学数据结构与算法数据结构与算法计算机组成原理计算机组成原理计算机网络计算机网络操作系统操作系统数据库数据库软件工程软件工程第9页本讲内容本讲内容什么是离散数学什么是离散数学1计算机专业为何要学离散数学计算机专业为何要学离散数学2离散数学基本内容离散数学基本内容3学习离散数学方法学习离散数学方法4离散数学学习资源离散数学学习资源5第10页3、离散数学基本内容、离散数学基本内容数学世界数学世界http:/ 第11页1.集合与关系集合与关系Chapter 1 集合、映射与运算集合、映射与运算 C
4、hapter 2 关系关系2.数理逻辑数理逻辑Chapter 3 命题逻辑命题逻辑Chapter 4 谓词逻辑谓词逻辑3.代数结构代数结构Chapter 5 代数结构代数结构4.图论图论Chapter 6 图论图论Chapter 7 几类特殊图几类特殊图5.组累计数组累计数(Chapter 8)第12页各章内容之间框架结构各章内容之间框架结构:第13页本讲内容本讲内容什么是离散数学什么是离散数学1计算机专业为何要学离散数学计算机专业为何要学离散数学2离散数学基本内容离散数学基本内容3学习离散数学方法学习离散数学方法4离散数学学习资源离散数学学习资源5第14页4、学习离散数学方法、学习离散数学方
5、法第15页数学学习方法数学学习方法1.预习预习2.听课听课3.复习复习4.作业作业这么就能够专心致志地学好离散数学理论这么就能够专心致志地学好离散数学理论知识知识,在后继课程中有实际应用价值在后继课程中有实际应用价值.第16页本讲内容本讲内容什么是离散数学什么是离散数学1计算机专业为何要学离散数学计算机专业为何要学离散数学2离散数学基本内容离散数学基本内容3学习离散数学方法学习离散数学方法4离散数学学习资源离散数学学习资源5第17页5、离散数学学习资源离散数学学习资源第18页参考文件参考文件(均为国家精品课程均为国家精品课程):屈婉玲屈婉玲,耿素云耿素云,张立昂张立昂,离散数学离散数学,高等教
6、育出高等教育出版社版社,.(108144课时课时)傅彦傅彦,顾小丰顾小丰,王庆先王庆先,离散数学及其应用离散数学及其应用,高等高等教育出版社教育出版社,.(两个学期两个学期)王元元王元元,沈克勤沈克勤,李拥军李拥军,贺汛贺汛,离散数学教程离散数学教程,高高等教育出版社等教育出版社,.Ebooks?第19页相关网络教学资源:相关网络教学资源:(1)Kenneth H.Rosen website:http:/ Mathematics and Its Applications(世界上有世界上有600多所大学使用多所大学使用,有影印本和翻译本有影印本和翻译本)(2)ArsDigita Universi
7、ty:http:/aduni.org/courses/discrete/index.php?view=cw 第20页(3)Harver Mudd College:http:/ Institute of Technology):http:/ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-042JFall-/CourseHome/index.htm 第21页离散数学是计算机相关专业离散数学是计算机相关专业主要专业基础课程主要专业基础课程.好好学习好好学习天天向上天天向上第22页第第1章章 集合、映射与运算集合、映射与
8、运算1.1 集合相关概念集合相关概念第23页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第24页1.1 集合相关概念集合相关概念1 集合集合集合是数学中最基本概念集合是数学中最基本概念,什么是集合什么是集合?在一定范围内在一定范围内,集合集合(set)是其是其含有某种特定含有某种特定性质性质对象聚集成一个整体对象聚集成一个整体,其中每一个对象其中每一个对象都称为该集合元素都称为该集合元素(element).第25页这里所指范围是全集这里所指范围是全集U.在数学中在数学中惯用惯用 表示整体表示整体.能够将考虑离散对象装在集合中能够将考虑离散对象装在集合中第26页(clas
9、sic set)若若x是是集合集合A中中元素元素,则记则记x A,不然不然x A.第27页N是自然数集合是自然数集合,包含数包含数0Z是整数集合是整数集合Z+是正整数集合是正整数集合(N+)Q是有理数集合是有理数集合R是实数集合是实数集合素数集合素数集合P:2,3,5,7,11,13,17,19,23等等.第28页(a)m,n Z,m|n:n=qm,q Z.m是是n因因数数,n是是m倍数倍数.2|6,-2|6,2|-6,-2|-6.m|0,0|0.(b)Dn表示表示n全部正因数组成集合全部正因数组成集合,如如D6=1,2,3,6.(c)设设p 1,若若Dp=1,p,则称则称p为素数为素数(pr
10、ime).第29页表示集合惯用方法表示集合惯用方法:(1)列举法列举法:将集合中元素按一定规律列举将集合中元素按一定规律列举出来出来,如如2,b,s,n,N=0,1,2,3,P?(2)描述法描述法:x|x满足条件满足条件.x|0 x 5,x;0 x 5第30页(3)递归法递归法递归思想递归思想:“知道他过去知道他过去,就知道他现在就知道他现在;知知道他过去和现在道他过去和现在,就知道他未来就知道他未来”.N递归定义递归定义:(a)0 N.(b)若若n N,则则n后继后继n+1 N.(c)有限次使用有限次使用(1)和和(2)得到元素是得到元素是N中仅有中仅有元素元素.其它方法其它方法?第31页R
11、emarks(i)集合中元素能够是任意元素集合中元素能够是任意元素,如集合如集合,比比如如A=a,a,b,b,c.a,b A.(ii)集合之间元素集合之间元素标准上标准上是没有次序是没有次序,如如 A=a,a,b,b,c就是就是 a,b,c,a,b.(iii)集合中元素集合中元素标准上标准上不重复不重复,如如a,a,b,b,b,c还是集合还是集合A=a,a,b,b,c.第32页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第33页2.子集子集(1)A B空集空集是任意集合子集是任意集合子集.“小小”(2)A=B第34页Theorem 1-2(1)A A.(2)A B,B
12、A A=B.(3)A B,B C A C.Theorem 1-3 A=B A B 且且 B A.第35页注意注意 与与 不一样不一样:例例1-2 由由A B,B C可否得出可否得出A C?Solution 不成立不成立,比如比如A=a,b,B=a,b,c,C=a,a,b,c.A B?课堂练习课堂练习:习题习题1.1 4,5.第36页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第37页3.幂集幂集(power set)(X),X=a,b P(X)=,a,b,a,b.为何要考虑幂集为何要考虑幂集(结合其上运算及性质结合其上运算及性质)?第38页P()=.P(P()=P()=
13、,.区分区分:,.第39页有限集合有限集合A元素个数元素个数|A|,card(A).Theorem 1-4 Hint 第40页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第41页4.n元组元组(抽象抽象!)Def 1-4 将将n个个元素元素(?)x1,x2,xn按一定次序按一定次序排列就得到一个排列就得到一个n元元(有序有序)组组(n-tuple).第42页线性代数中线性代数中n维向量维向量(?)元组在数据结构中是一个线性表、栈或队元组在数据结构中是一个线性表、栈或队列列,在数据库中是一条统计在数据库中是一条统计,如如(张三张三,男男,19,重庆重庆).n=2,n=3:
14、第43页 n=2:(x,y).n=3:(x,y,z)4元组元组?普通说来普通说来(x,y)(y,x).第44页2元组常称为有序对元组常称为有序对(ordered pair)或序偶或序偶.(x,y)第45页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第46页5.笛卡儿积笛卡儿积(cross product)解析几何之父笛卡儿解析几何之父笛卡儿(R.Cartesian,1596-1650)是法国数学家是法国数学家,“我思故我在我思故我在”和和“越越学习越发觉自己无知学习越发觉自己无知”是他名言是他名言.第47页例例1-4 设设A=a,b,B=1,2,C=,求求A B,B A
15、,A B C,B C.Solution ABC=(a,1,),(b,1,),(a,2,),(b,2,).BC=(1,),(2,)Remark A=B =.课堂练习课堂练习:习题习题1.1 10第48页Theorem 1-5Hint 第49页小结与作业小结与作业集合就是一些对象组成整体集合就是一些对象组成整体习题习题1.1 6,7,10作业作业A B,A=B第50页第第1章章 集合、映射与运算集合、映射与运算1.2 映射相关概念映射相关概念第51页本讲内容映射定义映射定义1映射性质映射性质2第52页1.2 映射相关概念映射相关概念1.映射定义映射定义映射映射(mapping)=函数函数(func
16、tion).y=f(x)=x2,ceiling function ,floor function ,编写编写C语言程序主要就是编写函数语言程序主要就是编写函数:从从main开始开始.第53页Def 任意给定两个集合任意给定两个集合A和和B,若存在对应法若存在对应法则则f,使得对于使得对于任意任意 x A,均存在均存在唯一唯一y B与与它对应它对应,则称则称f是集合是集合A到到B映射映射,或称其为或称其为A到到B函数函数,记为记为AB第54页为何讨论映射为何讨论映射?集合之间对应关系集合之间对应关系.其它了解方式其它了解方式:第55页映射两个特点映射两个特点:(1)全函数全函数.(2)唯一性唯一
17、性.注意区分函数注意区分函数 f 与与 f(x).y=f(x)?第56页函数符号选取函数符号选取:f,g,F,G,sin,exp,main,add,average,hanoi,delete_string,第57页例例1-5 写出全部写出全部A到到B映射映射.x1x2x3y1y2第58页n元函数元函数(n 1):第59页float average(float array,int n)n=0:C语言中无参函数语言中无参函数?第60页本讲内容映射定义映射定义1映射性质映射性质2第61页2.映射性质映射性质(1)单射单射(injection)第62页例例1-6 设设f:N N,f(x)=2x,则则f是
18、是N到到N单射单射,试证实之试证实之.Proof 对任意对任意x1,x2 A,由由f(x1)=f(x2),可得可得出出2x1=2x2,进而进而x1=x2.第63页(2)满射满射(surjection)第64页例例1-7 说明说明 是是Z到到N满射满射,但不是但不是Z到到Z满射满射.第65页(3)双射双射(bijection,one-to-one correspondence)双射又称为一一对应双射又称为一一对应:既单又满既单又满.例例1-8第66页例例1-9第67页Def 1-11 有限集合有限集合A上本身双射称为上本身双射称为A上置上置换换(permutation).例例1-10第一个方式第
19、一个方式:123123第68页第二种方式第二种方式:A=1,2,3,4上全部置换有多少个上全部置换有多少个?4!主要应用主要应用:置换置换加密加密.第69页小结与作业小结与作业映射映射(函数函数)定义定义单射单射满射满射双射双射(一一对应一一对应)习题习题1.2 1,2,3作业作业第70页第第1章章 集合、映射与运算集合、映射与运算1.3 运算定义及性质运算定义及性质第71页本讲内容运算定义运算定义1第72页1.运算定义A1,A2,An到到Bn元运算元运算(n-ary operation):第73页A1=2,S,N,A2=B,B=2B,SB,NB第74页A到到B(或或A上上)n元运算元运算:A
20、=5角硬币角硬币,1元硬币元硬币,B=打火机打火机,矿泉矿泉水水,雪糕雪糕,智能手机智能手机,平板电脑平板电脑第75页(运算封闭性运算封闭性)A上上n元封闭运算元封闭运算(代数运算代数运算):A=1,2,3,A上取小运算上取小运算min:第76页n元运算就是元运算就是n元函数元函数:n=0?普通处理方式普通处理方式:A到到B一个一个0元运算可元运算可了解为了解为B中某一个元素中某一个元素.第77页考虑运算目标考虑运算目标?运算是由已知对象得出运算是由已知对象得出新对象一个方法新对象一个方法.例例1-15(模运算模运算)f:Z N,f(x)=x(mod m),x=qm+r,0 r 1)表示小于等
21、于表示小于等于n且与且与n互素正整数个数互素正整数个数:第84页(1)=1,(2)=1,(3)=2,(4)=2,(5)=4,(6)=2,第85页D.Euclid算法算法:Solution 第86页第87页Remarks(1)运算符号运算符号(算符算符,算子算子)选取选取函数符号函数符号f,g,F,G,;常见运算符号常见运算符号+,/,;自定义符号自定义符号 ,第88页(2)运算符号位置运算符号位置 第89页(3)运算表运算表A=a,b,c,*:思索思索 A上封闭上封闭1元运算元运算,2元运算和元运算和3元运算元运算个数是多少个数是多少?*a b cabc b a c b c c c a b第9
22、0页运算本质上是映射运算本质上是映射.为何还要研究运算为何还要研究运算?但研究侧重点不一样但研究侧重点不一样,在运算中更重视于运在运算中更重视于运算满足一些运算性质算满足一些运算性质,而依据这些性质能够而依据这些性质能够对一些离散对象分门别类进行讨论对一些离散对象分门别类进行讨论.第91页小结与作业小结与作业n元运算和元运算和n元封闭运算定义元封闭运算定义模模m运算运算gcd(m,n)及及Euclid算法算法,lcm(m,n)运算符号及运算表运算符号及运算表习题习题1.3 2,3,7作业作业第92页第第1章章 集合、映射与运算集合、映射与运算1.3 运算定义及性质运算定义及性质第93页本讲内容
23、运算性质运算性质(常见有常见有11种种)2第94页2.运算性质运算性质(1)对合对合(involutive)性性 Def 1-15 设设*是是A上上1元元代数运算代数运算,例例 第95页(2)幂等幂等(idempotent)性性 幂等元幂等元x:A关于关于*含有幂等性含有幂等性:A中每个元素对于中每个元素对于*都是都是幂等元幂等元.第96页两个例子两个例子:*1 2 3123 1 3 2 2 3 2 3 1 3第97页(3)交换交换(commutative)性性 Def 设设*是是A上上2元代数运算元代数运算,若对于任意若对于任意x,y A,都有都有 则称则称*满足交换律满足交换律.映射复合运
24、算映射复合运算不满足交换律不满足交换律:加法运算加法运算”+”满足交换律满足交换律,而减法运算而减法运算”-”不满足交换律不满足交换律:2 3 3 2.怎样依据定义运算判断运算含有交换性怎样依据定义运算判断运算含有交换性?第98页(4)结合结合(associative)性性 映射复合运算映射复合运算满足结合律满足结合律:加法运算加法运算“+”满足结合律满足结合律,而减法运算而减法运算“-”不满足结合律不满足结合律:(2-3)-5 2-(3 5).第99页(5)幺元律幺元律 Def 1-19 设设*是是A上上2元代数运算元代数运算,若存在若存在e A,对于任意对于任意x A,以下条件均成立:以下
25、条件均成立:则称则称e为集合为集合A关于关于*运算单位元素或幺元素运算单位元素或幺元素第100页例例 Z关于加法运算关于加法运算+单位元素为单位元素为0,而而Z关于关于乘法运算乘法运算“.”单位元素为单位元素为1,Z关于减法运关于减法运算算-没有单位元素没有单位元素.第101页(6)零元律零元律 Def 设设*是是A上上2元代数运算元代数运算,若存在若存在 A,对对于任意于任意x A,以下条件均成立:以下条件均成立:则称则称 为集合为集合A关于关于*运算零元素运算零元素.第102页例例1-28 Z关于加法运算关于加法运算+和减法运算和减法运算-均没有均没有零元素零元素,而而Z关于乘法运算关于乘
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 集合 映射 运算 公共课 一等奖 全国 获奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。