《离散数学》课程 复习指导【荐】.docVIP

《离散数学》课程 复习指导 考试题型： （1）单项选择题（每小题3分，本题共15分） （2）填空题（每小题3分，本题共15分） （3）逻辑公式翻译（每小题6分，本题共12分） （4）判断说明题（每小题7分，本题共14分） （5）计算题（每小题12分，本题共36分） （6）证明题（本题共8分） 期末考试采用半开卷笔试形式，卷面满分为100分，考试时间为90分钟。 考试说明： Ⅰ．关于课程考核说明与实施要求 1．考核对象：本课程考核说明适用于中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的学生． 2．考核依据：本考核说明是以本课程的教学大纲（2007年6月审定）和指定的参考教材为依据制定的．本课程指定的参考教材是李伟生主编的、中央广播电视大学出版社出版的《离散数学》． 3．考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式． 4．课程综合成绩的记分方法：形成性考核占课程考核成绩的30%，即形成性考核的成绩满分为30分；终结性考核成绩占课程考核成绩的70%，即终结性考核成绩满分70分．课程考核成绩满分100分，60分以上为合格，可以获得课程学分． 5．形成性考核的说明： 6．终结性考试的说明：终结性考核实行全国统一考核，根据本课程考试说明，由中央电大统一命题，统一评分标准，统一考核时间． (1) 考核要求：本课程考核要求分三个层次，有关概念、性质和定理等理论方面的要求从高到低为理解，了解和知道；有关方法、公式和法则等的要求从高到低为熟练掌握，掌握和会． (2) 组卷原则：终结性考核的考核内容和要求以本考核说明为准，要求考核基本概念、基本原理和基本运算．命题覆盖面可适当宽些，但试题难度要适中，题量要适当．易、中、较难题目在试卷中分配为4：4：2． (4) 考核形式：采用半开卷、笔试方式，试卷满分100分． 半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考． (5) 考核时间：90分钟． 三．重点复习内容 第1章 集合及其运算 1．理解集合的概念，容斥原理． 2．理解集合的包含、子集、相等和幂集等概念，熟练掌握集合的表示方法和集合的并、交、补、差和对称差等运算，会用文氏图表示集合的各种运算． 3．掌握用集合运算基本规律证明集合恒等式的方法． 4．掌握利用容斥原理进行计数的方法． 第2章 关系与函数 1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 2．理解关系的概念：包括二元关系、空关系、全关系、恒等关系．掌握关系的集合表示、关系矩阵和关系图，掌握关系的运算． 3．掌握求复合关系和逆关系的方法． 4．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性)，掌握其判别方法． 5．理解等价关系和偏序关系概念，掌握等价关系、偏序关系的判定，掌握等价类、复盖集的求法和作偏序关系哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界． 6．理解函数概念：函数(映射)，函数相等，复合函数和反函数． 7．理解单射、满射和双射等概念，掌握其判别方法． 第3章 图的基本概念与性质 1．理解图的基本概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、图的同构子图等，理解握手定理． 2．了解通路与回路的概念：简单通路、初级通路和复杂通路，简单回路、初级回路和复杂回路，会求通路和回路的长度． 3．了解无向图的连通性，会求无向图的连通分支．了解点割集、割点、边割集、割边、点连通度、边连通度等概念． 4．了解有向图的强连通性、单向连通性、弱连通性；会判别有向图连通性的类型． 5．理解图的矩阵表示法、邻接矩阵、可达性矩阵的概念，掌握邻接矩阵、可达性矩阵的有关计算． 6．知道最短路径的概念，会最短路径的算法． 第4章 几种特殊图 1．了解欧拉回路、欧拉图的概念及性质，掌握欧拉图的判别方法． 2．了解汉密尔顿回路、汉密尔顿图的概念及性质，掌握汉密尔顿图的判别方法． 3．了解平面图的概念：平面图、面、边界、面的次数和非平面图，掌握平面图的判别方法，掌握欧拉公式的应用． 4．理解平面图与对偶图的关系、对偶图在图着色中的作用，掌握着色算法； 5．掌握图论中常用的证明方法 第5章 树及其应用 及性质及性质Huffman算法． 3．掌握利用最优树产生前缀码的方法． 第6章 命题逻辑 1．理解命题联结词概念，掌握命题公式的翻译（命题符号化）及判断语句是不是命题的方法． 2．熟练掌握求给定公式真值表的方法． 3．掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法．