《离散数学》教学大纲

离散数学PAGE1《离散数学》教学大纲目录一、教学目的和要求 1二、教学中应注意的问题 1三、教学课时分配 1课程名称：离散数学学时：64学时课程类型：必修课程性质：专业基础课开课学期：第2学期先修课程：高等数学适用专业：服务外包方向一、教学目的和要求1、目的《本课程的目标是使学生能够熟练运用离散数学的知识进行软件系统的建模和分析，具体包括：如何清晰、准确地描述系统规范和设计规范（如：系统状态、系统行为、系统约束、前置条件、后置条件、状态不变量等等）。相关的表示工具包含符号逻辑、集合、关系、函数、图等。学习应用这些概念、原理、方法对实际问题和系统进行描述和分析的方法。因此，本课程应包括以下内容：离散结构的描述理论、方法及应用，简单的数学推理和证明技术。2、要求●能够阅读、理解基于典型离散结构的软件规范；●使用典型的离散结构对软件系统进行建模。二、教学中应注意的问题1、集合及其计算是关系和函数的基础，需要熟练掌握。在讲授时应该强调关系和函数在实际问题中的应用。2、符号逻辑是形式化表示的重要工具。构造命题公式的真值表是命题逻辑的基本技术，必须准确掌握。有效推理的主要技术包括：真值表技术、蕴含式技术、形式证明方法。应该通过证明技术的学习帮助学生初步建立形式推理的思想与方法。讲授时宜多举例。三、教学课时分配（1）函数、关系与集合基本学时：18学时教学内容●集合的表示、集合的基本运算和幂集（3学时）●序偶与笛卡尔积（1学时）●二元关系的概念与表示（2学时）●二元关系的性质（1学时）●二元关系的运算及闭包（4学时）●等价关系与序关系（4学时）●函数定义与性质（1学时）●复合函数与逆函数（2学时）重点集合的基本运算，幂集的定义与计算，二元关系的表示与性质，等价关系与序关系，函数的定义与性质。难点集合相等的证明，幂集的计算，二元关系的运算及闭包的性质，偏序关系的哈斯图及特殊元。讲授提示集合及其计算是关系和函数的基础，需要熟练掌握。在讲授时应该强调关系和函数在实际问题中的应用。习题要求对本单元知识的掌握程度关系到后续单元的学习。因此，应当适度多布置习题。（2）基本逻辑基本学时：19学时教学内容●命题、联结词与语句形式化（2学时）●重言式、可满足式与矛盾式（1学时）●等价式、蕴含式（2学时）●范式与联接词的规约（5学时）●有效推理与形式证明（5学时）●个体词、谓词、量词与语句形式化（3学时）●谓词公式的真值及其永真式（1学时）重点命题、联接词与语句形式化；范式，命题逻辑推理；个体词、谓词、量词与语句形式化。难点语句形式化，重言式、可满足式与矛盾式的判别，命题逻辑推理。讲授提示本单元是符号逻辑的基础，是形式化表示的重要工具。构造命题公式的真值表是命题逻辑的基本技术，必须准确掌握。有效推理的主要技术包括：真值表技术、蕴含式技术、形式证明方法。应该通过证明技术的学习帮助学生初步建立形式推理的思想与方法。讲授时宜多举例。习题要求应当适度多布置习题。特别是，语句的形式化表示，等价置换和推理。使学生对几种常见的证明技术有所体会。（3）图与树基本学时：20学时教学内容●图的基本概念（1学时）●有向图、图的最短路径与关键路径（4学时）●图的矩阵表示（2学时）●树的定义与性质（4学时）●生成树（2学时）●根数及应用（3学时）●特殊的图（4学时）重点握手定理，图的连通性，图的矩阵表示，树的定义与性质，生成树的求法与应用，根树的应用。难点图论知识的理解与应用。讲授提示图和树是两种重要的建模工具，又是两种广泛应用的数据结构。在教学中通过实例强化对知识的理解和应用。例如航班安排、文件存储结构、通信网络等。习题要求在习题安排中，注意训练学生利用图和树表示问题、解决问题等数学建模能力。（4）证明技术通过各知识单元引入各类常见的证明技术，包括：-归纳法证明技术（主要应用于集合、关系、函数、图论）-构造法证明技术（主要应用于图论）-反证法证明技术（主要应用于图论）有关证明技术的教学安排可以与其它知识单元的讲授中同步进行。（5）代数系统简介基本学时：3学时教学内容●代数系统的基本概念（1学时）●群、环、域、格和布尔代数（2学时）重点代数系统的基本概念，布尔代数。难点代数系统的基本概念讲授提示在形式化开发方法中，有时采用代数方法描述软件系统，由于本教程没有把重点放在形式化方法中，所以对代数系统只做简介介绍。代数系统的内容比较抽象，需要通过较多的实例进行说明。可以利用形式化开发的例子说明其应用，如Specware，VDM，Z等。习题要求习题中可选择少量的计算和判断题，以布尔代数为主。（6）初等数论基本学时：4学时教学内容●整除与素数（1学时）●最大公约数与最小公倍数（1学时）●同余与一次同余式（1学时）●欧拉定理与费马小定理（1学时）重点全部内容。难点全部内容讲授提示可结合代数系统引入同余概念和运算，可以介绍初等数论在信息安全密码学中的应用。习题要求习题中可以选择适当数量的计算题。四、考试要求（1）考题设计建议考试内容有4部分组成：①选择题和填空题：30%②分析或计算题：40%③证明题：10%④综合应用题：20%（2）成绩构成成绩评定以期末成绩与平时成绩（作业、小测验等）综合评定，期末成绩占60%。（3）考试形式闭卷笔试。五、学时分配表教学内容总课时数课堂教学课内练习课外作业函数、关系与集合1