离散数学一夜通.pdf

离散数学一夜通 11 级软工9 班张天意 2012.6.20 Outline： 一．考点分布 二．小知识汇集 三．例题精选 四．中英关键词语对照 一．考点分布 根据以往的的题目分析以及课上老师所强调的 考点分布如下： 1. 集合的定义概念 ，集合的操作分析 （题目给一些集合的关系，让 你判断是否满足，不满足举出反例，满足的话证明）。 2. 合取、析取、谓词，量词的概念；条件陈述、断言、永真式、谬 论、逻辑关系 （否 （尤其注意if 的否定）、逆否）的书写。 3. 笛卡尔积、关系、关系矩阵、关系图、关系的性质：自反、反自 反、对称、反对称、传递性。 4. 等价关系的定义以及证明，等价类，关系的复合运算，关系矩阵 的复合运算，关系的闭包 （传递闭包的算法问题）。 5. 函数的性质：处处有定义、满射、一一映射、双射的证明，置换、 循环置换，变换。 6. 字典序，对偶，偏序关系的定义及证明，画哈斯图，寻找哈斯图 中的极大元 （max）、极小元 （min）、最大元 （greatest ）、最小元 （least），最大下界 （GLB ），最小上界 （LUB）等一系列问题； 格的定义，判断一个图是否为格，分配格的性质。 7 ．树：霍夫曼编码树、树的遍历（先序、中序、后序），最小生成树 的Prime 算法和Kruskal 算法。 8. 欧拉路径和欧拉图，Hamiltonian 路径和Hamiltonian 图（ps ：老师 说太简单，考的可能性不大）。 9. 标定算法 以及用标定算法解决流量问题；二部图的着色问题。 二．小知识汇集 （一些容易忽视的小点 虽然考得可能性不大，但 是感觉对于知识的理解蛮有用的，ps 以防万一） 1.通常使用真值表判断一个式子是否为永真式或者为谬论。 2.命题的否定 Negation of quantifiers 3. p=q is equivalent to (~pV q) 二者逻辑等价 4.笛卡尔积： 5. 关系的运算 关系矩阵运算： 7. 对称、自反、传递的概念以及基本证明 8. 传递闭包的算法：Warshall Algorithm 9. 函数复合： 10. 11.置换的一些基本运算 12.偏序的概念 13.字典序 14. 哈斯图中的一些概念 15.格为何物？ 16.分配格 17.树的遍历 同一个图， 先： 中： 后： 三种方法 三个结果 18.最小生成树 （大致思路）： Prim 算法：从给定点开始，选最小边，直至连通 Kruskal 算法：先选最小边 然后选次小边，直至连通 19.欧拉路径和欧拉图、哈路径和哈图(了解即可) ： To travel a path using each edge of the graph exactly once — Euler Paths and Circuits. To visit each vertex exactly o nce, except the beginning one — Hamiltonian Paths and Circuits. 20.标定算法： 三．例题精选（主要选取09 真题，吴老师的风格和09 的实在是太太太像了） *-*-*-*-**-*-*-*-**-*-*-*-*-*华丽分割线*-*-*-*-**-*-*-*-**-*-*-*-**-* 证明的基本方法 （如何取元素），证明两个集合相等就是证明二者分 别为对方的子集。 例1. Ans ： 友情提醒：证明完二者相互属于对方的子集之后千万别来个 “=”, 应该用 “∴”，这个老师强调了n 次了。 *-*-*-*-**-*-*-*-**-*-*-*-*-*华丽分割线*-*-*-*-**-*-*-*-**-*-*-*-**-* 等价关系是什么?三部走起自反+对称+传递 例2： (1.3)关系R 是传递的 友情提示：一步一个脚印，写好步骤，让老师无