《离散数学》课程考试大纲

《离散数学》课程考试大纲一、考试对象本课程考试大纲适用于计算机科学与技术（含卓越工程师班）、信息管理与信息系统、信息安全、软件工程、网络工程、数字媒体技术专业的学生。二、考试依据本课程考试大纲是以本课程的教学大纲和指定的教材为依据制定的。本课程指定的教材为古天龙等主编的、清华大学出版社出版的《离散数学》。三、考核知识点和考核要求第1章集合考核知识点:1．集合，元素，集合的表示，全集，空集2．集合的包含、相等，子集，幂集3．集合的并、交、补、差、对称差等运算及其运算律4．容斥原理考核要求:1．理解集合的概念，容斥原理．2．理解集合的包含、子集、相等和幂集等概念，熟练掌握集合的表示方法和集合的并、交、补、差和对称差等运算，会用文氏图表示集合的各种运算．3．掌握用集合运算基本等值式证明集合恒等式的方法．4．掌握利用容斥原理进行计数的方法.第2章关系考核知识点:1．有序对和笛卡儿积2．关系及其运算性质3．二元关系的矩阵与图4．复合关系与逆关系5．二元关系的性质6．等价关系与等价类7．偏序关系与哈斯图，极大(小)元，最大(小)元，上(下)界，上确界，下确界考核要求:1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算．2．理解关系的概念：包括二元关系、空关系、全关系、恒等关系．掌握关系的集合表示、关系矩阵和关系图，掌握关系的运算．3．掌握求复合关系和逆关系的方法．4．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性)，掌握其判别方法．5．理解等价关系和偏序关系概念，掌握等价关系、偏序关系的判定，掌握等价类、划分的求法和作偏序关系哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、最小上界和最大下界．第3章函数考核知识点：函数、函数的逆运算、函数的复合运算单射、满射和双射考核要求：1．理解函数概念：函数，函数的复合运算和函数的逆运算．2．理解单射、满射和双射等概念，掌握其判别方法．第4章代数系统考核知识点：1.运算、运算的封闭性2.代数系统、子代数系统3.交换律、结合律、分配律、吸收律、等幂律、消去律4.等幂元、幺元、零元、逆元、可消去元5.同构、同态、同态核、同态的基本性质考核要求：1.掌握代数系统的基本概念：运算、运算的封闭性、交换律、结合律、分配律、吸收律、等幂律、消去律、等幂元、幺元、零元、逆元、可消去元．2.理解代数系统、子代数系统的概念．3.掌握同构、同态的定义及基本性质；理解同态核．第5章典型的代数系统考核知识点：1.半群、子半群、独异点、子独异点、群、子群2.元素的阶、群的阶、群的性质、子群的性质3.交换群、生成元、循环群考核要求：掌握半群、子半群、独异点、子独异点、群、子群的定义及基本性质.掌握群的阶、元素的阶、生成元；掌握子群的判定方法.理解交换群的定义，掌握循环群的定义与性质.第6章图考核知识点:1.图、简单图、完全图、子图、生成子图、导出子图2.顶点的度数、握手定理、图的同构、通路、回路、图的连通性、图的操作、关联矩阵、邻接矩阵、可达矩阵、边权矩阵、赋权图、最短路径，Dijkstra算法3.欧拉图、哈密顿图、二部图考核要求:掌握图的基本概念：图、简单图、完全图、子图、生成子图、导出子图的定义.掌握顶点的度数、握手定理的应用；掌握图的同构；掌握通路、回路、图的连通性的概念及基本性质.理解图的操作；掌握关联矩阵、邻接矩阵，理解可达矩阵、边权矩阵；掌握赋权图及最短路径的概念，掌握用Dijkstra算法求赋权图中的最短路径；掌握欧拉图、哈密顿图的定义及判定定理；理解二部图的定义及判定定理.第7章树考核知识点:无向树、赋权树、生成树、最小生成树、求最小生成树的算法、有向树、根树、有序树、根树的遍历、二叉树、最优树、前缀码、最佳前缀码、Huffman算法考核要求:掌握无向树的定义及性质；掌握赋权树、生成树、最小生成树的定义及求最小生成树的算法.掌握有向树的定义及性质；掌握根树、有序树的定义，理解根树的遍历；掌握二叉树的定义及性质；掌握最优树、前缀码、最佳前缀码的定义，Huffman算法及其应用.第8章命题逻辑考核知识点：1．命题与联结词(否定、析取、合取、蕴含、等价)，真值与真值表2．命题公式的等值式与蕴涵式，等值演算3．析取范式、合取范式、极小(大)项，主析取范式、主合取范式的概念与求法4．命题逻辑的推理理论考核要求：1．理解命题联结词概念，掌握命题符号化及判断语句是不是命题的方法．2．熟练掌握求给定公式真值表的方法．3．掌握基本等值式以及用真值表法和等值演算法判别公式类型和公式等值的方法．4．了解析取(合取)范式概念，理解极小(大)项的概念和主析取(合取)范式概念，熟练掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法．5．掌握命题逻辑推理的的直接证明方法与间接证明方法．第9章谓词逻辑考核知识点：1．谓词，量词，个体词，个体域，变元2．谓词公式的解释3．前束范式的概念与求法4．谓词公式的等值式与蕴涵式5．谓词逻辑的推理理论考核要求：1．理解谓词、量词、个体词、个体域、全域、原子公式、谓词公式和变元等概念．掌握谓词公式的符号化.2．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．3．掌握谓词演算的等值式和重言蕴含式