《离散结构》教学大纲

PAGEPAGE3离散结构教学大纲目录一、教学目的和要求………(3)二、教学中应注意的问题…………………(3)三、教学内容………………(3)四、教学课时分配…………(4)五、参考书目………………(4)

一、教学目的和要求离散数学，是现代数学的一个重要分支，是计算机科学与技术一级学科的核心课程，是整个计算机学科的专业基础课。离散数学是以研究离散量的结构和相互间的关系为主要目标，其研究对象是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。离散数学的教学任务是在教给学生离散问题建模、数学理论、计算机求解方法和技术知识的同时，培养学生的数学抽象能力与严密的逻辑推理能力。通过本课程的学习，学生不仅可以掌握进一步学习其他专业课程所必需的理论基础知识，而且可以增强应用离散数学的基本原理和方法分析和解决问题的能力。二、教学中应注意的问题1、突出重点：着重讲解计算机科学中普遍地采用离散数学中的一些基本概念、基本思想。2、重视难点：理论与实践相结合，掌握计算机科学中普遍地采用离散数学中的基本方法，使学生具备解决离散问题的基本能力。3、本课程的前导课应包含高等数学和线性代数。 三、教学内容通过该课程的教学，使学生了解并掌握计算机科学中普遍地采用离散数学中的一些基本概念、基本思想、基本方法，同时使学生具备解决离散问题的基本能力，并且要培养学生的抽象思维能力，为以后课程的学习及科学研究提供坚实的理论基础。数理逻辑与命题逻辑了解命题与联结词的基本概念，掌握命题符号化；理解命题公式及其类型，掌握等值演算；理解析取范式与合取范式，掌握主析取范式及其求法；了解推理的形式结构与推理定律，理解推理方法，掌握构造推理的证明过程的方法。了解谓词与量词，理解谓词逻辑中的符号化；了解谓词公式，了解真与逻辑有效；掌握谓词逻辑的等值演算，掌握前束范式及其求法；掌握谓词逻辑的推理理论。集合论与集合代数了解和掌握集合的基本概念及空集、全集、幂集的概念，了解和掌握集合的运算与性质，了解和掌握文氏图的概念及应用，理解有限集合计数的相容排斥原理。了解和掌握二元关系、有序对与笛卡儿积，了解和掌握关系的运算、关系的性质（自反、对称、传递）、关系的闭包、等价关系、偏序关系以及他们的应用。理解偏序关系、偏序集与哈斯图的概念及性质。了解偏序集中的极值元和最元、上界、下界、上确界、下确界。理解函数、满射、单射、双射的概念，理解并掌握反函数存在性定理，熟练掌握函数的复合运算，了解特征函数的概念。理解计算机科学领域中常见的函数表示法。了解并掌握集合的基数和可数性。(三)图论了解欧拉图和哈密顿图，理解欧拉圈，欧拉链，欧拉图，哈密顿圈，哈密顿链，哈密顿图定义的实质，掌握欧拉图的判别准则并写出欧拉圈。理解二分图、可扩充链、二分图的匹配的定义的实质，能熟练识别二分图。理解平面图的定义和欧拉公式的实质，掌握库拉托夫斯基定理的内容，会用库拉托夫斯基定理证明非平面图。理解树的概念及性质，根树、有序树、完全二元树、生成树、割集概念的实质，熟练掌握有序树转化为位置二元树并求出前缀编码的方法，掌握树的遍历方法，掌握求生成树的破圈算法和求最小生成树的避圈算法，会用Huffman算法求最优二元树。(四)代数结构了解二元运算的概念与性质，了解半群、独异点、群及它们的子代数、同态、同构的基本概念和性质，理解半群的积与商及群的积与商的概念和性质，了解环与域的概念。理解群的同态与同构。四、教学课时分配教学课时分配表教学内容讲授学时辅导学时实验学时上机学时习题课其它数理逻辑与命题逻辑12集合论与集合代数12图论14代数结构10