离散数学-复习省公开课一等奖全国示范课微课金奖PPT课件.pptx

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,离散数学,西安交通大学,电子与信息工程学院,计算机系,1,第1页,离散数学,第一章 集 合,重点要求,掌握集合、子集、全集、空集、单元素集等概念,掌握集合四大性质:任意性,(抽象性),、确定性、无序性、无重复性,熟悉惯用表示集合方法以及用文氏图来表示集合方法,能够判定元素与集合,集合与集合之间关系.了解两个集合间包含关系和相等关系,(外延性原理),定义和性质,能够利用这些定义、性质来证实两个更复杂集合包含和相等。,掌握幂集定义及计算有限集幂集所含元素个数，所使用计算、证实方法和思想。,了解,差异在于级别!,判定集合间关系思想。,掌握集合五种基本运算:交、并、余,(,补,),、差和对称差,(环和),定义,并熟记集合运算基本定理,(,公式,),能够熟练利用它们来证实更复杂集合公式。,2,第2页,离散数学,第二章 关 系,重点要求,掌握序偶和笛卡尔积概念,。,掌握二元关系形式定义及其各种表示方法：序偶，矩阵，关系图等；能正确使用集合表示式，关系距阵，关系图等表示给定关系，并要求能够从一个形式写出另一个形式。,特殊关系：全关系、空关系、幺关系,掌握关系运算，包含集合运算以及关系复合和关系逆运算。,掌握二元关系各种特殊性质：自反，反自反，对称，反对称，传递等，并了解这些性质怎样反应在关系图上，关系矩阵上等。,3,第3页,离散数学,掌握集合中二元关系闭包意义和其基本性质，能求出有限集上二元关系闭包。,掌握等价关系概念，并掌握覆盖、划分、等价类、商集定义和基本性质，搞清楚等价关系与划分之间关系。切记等价关系,分类,作用。,掌握半序、半序集、全序、良序等概念，以及半序集可比较性、极大元、极小元、最大元、最小元、上界、下界、最大下界、最小上界、直接后继等概念。切记半序关系,非线性,特征。,能画出有限半序集哈斯图,并依据图讨论半序集一些性质。,4,第4页,离散数学,第三章 函 数,重点要求,要求掌握函数基本概念,搞清单射,、,满射,、,双射之间区分,。,给定一个函数,要能够确定它是否是单射,、,满射,、,双射等,。,掌握逆函数和复合函数定义和性质,并搞清楚它们存在条件,。,了解元素及集合象及原象定义及相关性质,。,给定一个函数,能够确定一个点象,一个集合象,能够确定一个点原象,一个集合原象,能够确定两个函数复合函数等,。,掌握集合势,、可数集、不可数集等概念,。,5,第5页,离散数学,第四章 代数系统,重点要求,掌握代数系统概念,定义:运算封闭性,、,幺元,、,零元,、,逆元,及相关结论有清楚了解,。,给定集合和集合上运算能够判断该集合对运算是否封闭;能够经过运算表确定幺元、,零元,、,逆元等(假如存在话);对交换律,、,结合律,、,分配律,、,吸收律,、消去律,等表示要十分清楚;给定集合和二元运算表能够判断运算是否满足结合律等等,。,掌握代数系统同态和同构定义能判断两个给定代数系统间某个映射是否为同态同构映射,。,掌握半群及含幺半群等概念,。,6,第6页,离散数学,掌握群概念,并能灵活利用群一些基本性质,了解群同态和同构,。,给定一个代数系统及其运算,能够判断是否为半群,、,含幺半群,、,群等,。,掌握子群概念并清楚其判别方法,。,掌握环,、,整环,、除环,定义,并熟悉环基本性质,。,给定集合及两个二元运算能够判断其是否为环,、,整环,、除环,等,。,切记消去律,、无零因子、有逆元三者间俩层关系及其利用,。,掌握域定义,熟悉它们判别定理,。,7,第7页,离散数学,第六章 图 论,重点要求,掌握图,、,无向图,、,有向图,、结点及边,关联,、,邻接,、,结点进度,、,出度,、,度,、一些特殊图、子图、完全图、同构、路、圈、路及圈长度、结点之间连通性与可达性、图连通性与可达性、强连通性、单向连通性、弱连通性、强连通分图、单向连通分图、弱连通分图、割边等概念及相关性质,并能够判定或证实图相关结论,。,掌握求图中某一结点到其它任一结点最短路Dijkstra算法,。,掌握求欧拉图和哈密顿图,概念及其判别性定理、判别法，能够利用,C.L.Liu算法求欧拉圈，,能够利用,Fleury算法求欧拉路，,能够利用,K ning算,法,求哈密顿路或密顿圈，,能够利用,翻边,法,求有向哈密顿路或有向密顿圈，,能够利用管氏定理或,Dijkstra算法求解中国邮路问题(最优欧拉圈)，,能够利用,近邻法,、交换法,求解货郎担问题(最优哈密顿圈),。,8,第8页,离散数学,掌握偶图,、匹配、完美匹配、最大匹配,等,概念，,掌握偶图,判别性定理及判别法，能够利用,匈牙利,法以增广路,求偶图,最大匹配,。,掌握平面图,、非,平面图,、区域(面),等,概念,。,掌握平面图,欧拉公式及其必要性判别法、拉边法，了解,Kuratowski平面图,最终定理，并能用其判别一个图平面性,。,9,第9页,离散数学考试题型和时间,判断题 30%,56道大题 70%,形式:证实 讨论 利用算法,其中:图论 12题 20%,等价关系/半序关系:20%,代数系统:20%30%,时间：12月21日下午14:3017:00,地点：中三3-3302 3303 3304,10,第10页,离散数学,祝大家考出,好成绩!,11,第11页,