离散数学 复习.ppt

《离散数学 复习.ppt》由会员分享，可在线阅读，更多相关《离散数学 复习.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学西安交通大学西安交通大学电子与信息工程学院电子与信息工程学院计算机系计算机系1离散数学 第一章第一章 集集 合合 重点要求重点要求 w掌握集合、子集、全集、空集、单元素集等概念掌握集合、子集、全集、空集、单元素集等概念,掌握集合的四掌握集合的四大性质大性质:任意性任意性(抽象性抽象性)、确定性、无序性、无重复性、确定性、无序性、无重复性,熟悉常用熟悉常用的表示集合的方法以及用文氏图来表示集合的方法的表示集合的方法以及用文氏图来表示集合的方法,能够判定元能够判定元素与集合素与集合,集合与集合之间的关系集合与集合之间的关系.理解两个集合间的包含关系和理解两个集合间的包含关系和相等关

2、系相等关系(外延性原理外延性原理)的定义和性质的定义和性质,能够利用这些定义、性质能够利用这些定义、性质来证明两个更复杂的集合的包含和相等。来证明两个更复杂的集合的包含和相等。w掌握幂集的定义及计算有限集的幂集所含元素个数，所使用的掌握幂集的定义及计算有限集的幂集所含元素个数，所使用的计算、证明的方法和思想。计算、证明的方法和思想。w理解理解差别在于级别差别在于级别!的判定集合间关系的思想。的判定集合间关系的思想。w掌握集合的五种基本运算掌握集合的五种基本运算:交、并、余交、并、余(补补)、差和对称差、差和对称差(环和环和)的定义的定义,并熟记集合运算的基本定理并熟记集合运算的基本定理(公式公

3、式),能够熟练的利用它们能够熟练的利用它们来证明更复杂的集合公式。来证明更复杂的集合公式。2离散数学 第二章第二章 关关 系系 重点要求重点要求 w掌握序偶和笛卡尔积的概念掌握序偶和笛卡尔积的概念。w掌握二元关系的形式定义及其各种表示方法：序偶，矩阵，关掌握二元关系的形式定义及其各种表示方法：序偶，矩阵，关系图等；能正确使用集合表达式，关系距阵，关系图等表示给定系图等；能正确使用集合表达式，关系距阵，关系图等表示给定的关系，并要求能够从一种形式写出另一种形式。的关系，并要求能够从一种形式写出另一种形式。w特殊关系：全关系、空关系、幺关系特殊关系：全关系、空关系、幺关系w掌握关系的运算，包括集合

4、运算以及关系的复合和关系的逆运掌握关系的运算，包括集合运算以及关系的复合和关系的逆运算。算。w掌握二元关系的各种特殊性质：自反，反自反，对称，反对称，掌握二元关系的各种特殊性质：自反，反自反，对称，反对称，传递等，并理解这些性质如何反映在关系图上，关系矩阵上等。传递等，并理解这些性质如何反映在关系图上，关系矩阵上等。3离散数学w掌握集合中二元关系的闭包的意义和其基本性质，能求出有限掌握集合中二元关系的闭包的意义和其基本性质，能求出有限集上的二元关系的闭包。集上的二元关系的闭包。w掌握等价关系的概念，并掌握覆盖、划分、等价类、商集的定掌握等价关系的概念，并掌握覆盖、划分、等价类、商集的定义和基本

5、性质，弄清楚等价关系与划分之间的关系。牢记等价关义和基本性质，弄清楚等价关系与划分之间的关系。牢记等价关系的系的分类分类作用。作用。w掌握半序、半序集、全序、良序等概念，以及半序集的可比较掌握半序、半序集、全序、良序等概念，以及半序集的可比较性、极大元、极小元、最大元、最小元、上界、下界、最大下界、性、极大元、极小元、最大元、最小元、上界、下界、最大下界、最小上界、直接后继等概念。牢记半序关系的最小上界、直接后继等概念。牢记半序关系的非线性非线性特性。特性。w能画出有限半序集的哈斯图能画出有限半序集的哈斯图,并根据图讨论半序集的某些性质。并根据图讨论半序集的某些性质。4离散数学 第三章第三章

6、函函 数数 重点要求重点要求 w要求掌握函数的基本概念要求掌握函数的基本概念,弄清单射弄清单射、满射满射、双射之间的区别双射之间的区别。给定一个函数给定一个函数,要能够确定它是否是单射要能够确定它是否是单射、满射满射、双射等双射等。w掌握逆函数和复合函数的定义和性质掌握逆函数和复合函数的定义和性质,并弄清楚它们存在的条件并弄清楚它们存在的条件。w理解元素及集合的象及原象的定义及相关的性质理解元素及集合的象及原象的定义及相关的性质。给定一个函给定一个函数数,能够确定一个点的象能够确定一个点的象,一个一个集合集合的象的象,能够确定一个点的原象能够确定一个点的原象,一个一个集合集合的原象的原象,能够

7、确定两个函数的复合函数等能够确定两个函数的复合函数等。w掌握掌握集合集合的势的势、可数集、不可数集等概念、可数集、不可数集等概念。5离散数学 第四章第四章 代数系统代数系统 重点要求重点要求 w掌握代数系统的概念掌握代数系统的概念,定义定义:运算的封闭性运算的封闭性、幺元幺元、零元零元、逆元逆元及及相关的结论有清晰的理解相关的结论有清晰的理解。给定集合和集合上的运算能够判断该给定集合和集合上的运算能够判断该集合对运算是否封闭集合对运算是否封闭;能够通过运算表确定幺元、能够通过运算表确定幺元、零元零元、逆元等逆元等(如果存在的话如果存在的话);对交换律对交换律、结合律结合律、分配律分配律、吸收律

8、吸收律、消去律、消去律等等的表示要十分清楚的表示要十分清楚;给定集合和二元运算表能够判断运算是否满足给定集合和二元运算表能够判断运算是否满足结合律等等结合律等等。w掌握代数系统的同态和同构的定义能判断两个给定代数系统间的掌握代数系统的同态和同构的定义能判断两个给定代数系统间的某个映射是否为同态同构映射某个映射是否为同态同构映射。w掌握半群及含幺半群等概念掌握半群及含幺半群等概念。6离散数学w掌握群的概念掌握群的概念,并能灵活运用群的一些基本性质并能灵活运用群的一些基本性质,理解群的同态和理解群的同态和同构同构。给定一个代数系统及其运算给定一个代数系统及其运算,能够判断是否为半群能够判断是否为半

9、群、含幺半含幺半群群、群等群等。w掌握子群的概念并清楚其判别方法掌握子群的概念并清楚其判别方法。w掌握环掌握环、整环整环、除环、除环的定义的定义,并熟悉环的基本性质并熟悉环的基本性质。给定集合及两给定集合及两个二元运算能够判断其是否为环个二元运算能够判断其是否为环、整环整环、除环、除环等等。w牢记消去律牢记消去律、无零因子、有逆元三者间的俩层关系及其运用、无零因子、有逆元三者间的俩层关系及其运用。w掌握域的定义掌握域的定义,熟悉它们的判别定理熟悉它们的判别定理。7离散数学 第六章第六章 图图 论论 重点要求重点要求 w掌握图掌握图、无向图无向图、有向图有向图、结点及边的、结点及边的关联关联、邻

10、接邻接、结点的进结点的进度度、出度出度、度度、一些特殊的图、子图、完全图、同构、路、圈、一些特殊的图、子图、完全图、同构、路、圈、路及圈的长度、结点之间的连通性与可达性、图的连通性与可路及圈的长度、结点之间的连通性与可达性、图的连通性与可达性、强连通性、单向连通性、弱连通性、强连通分图、单向达性、强连通性、单向连通性、弱连通性、强连通分图、单向连通分图、弱连通分图、割边等概念及相关性质连通分图、弱连通分图、割边等概念及相关性质,并能够判定并能够判定或证明图的有关结论或证明图的有关结论。w掌握求图中某一结点到其它任一结点的最短路的掌握求图中某一结点到其它任一结点的最短路的Dijkstra算法算法

11、。w掌握求欧拉图和哈密顿图的掌握求欧拉图和哈密顿图的概念及其判别性定理、判别法，能概念及其判别性定理、判别法，能够利用够利用C.L.Liu算法求欧拉圈，算法求欧拉圈，能够利用能够利用Fleury算法求欧拉路，算法求欧拉路，能够利用能够利用K ning算算法法求哈密顿路或密顿圈，求哈密顿路或密顿圈，能够利用能够利用翻边翻边法法求求有向哈密顿路或有向密顿圈，有向哈密顿路或有向密顿圈，能够利用管氏定理或能够利用管氏定理或Dijkstra算算法求解中国邮路问题法求解中国邮路问题(最优欧拉圈最优欧拉圈)，能够利用能够利用近邻法近邻法、交换法、交换法求解货郎担问题求解货郎担问题(最优哈密顿圈最优哈密顿圈)

12、。8离散数学w掌握偶图掌握偶图、匹配、完美匹配、最大匹配、匹配、完美匹配、最大匹配等等概念，概念，掌握偶图的掌握偶图的判判别性定理及判别法，能够利用别性定理及判别法，能够利用匈牙利匈牙利法以增广路法以增广路求偶图的求偶图的最大最大匹配匹配。w掌握平面图掌握平面图、非、非平面图平面图、区域、区域(面面)等等概念概念。掌握平面图的掌握平面图的欧拉欧拉公式及其必要性判别法、拉边法，了解公式及其必要性判别法、拉边法，了解Kuratowski平面图平面图最后最后定理，并能用其判别一个图的平面性定理，并能用其判别一个图的平面性。9离散数学考试题型和时间w判断题判断题 30%w56道大题道大题 70%形式形式:证明证明 讨论讨论 运用算法运用算法 其中其中:图论图论 12题题 20%等价关系等价关系/半序关系半序关系:20%代数系统代数系统:20%30%w时间：12月21日下午14:3017:00w地点：中三3-3302 3303 330410离散数学祝大家考出 好成绩!11