课程名称: 离散数学
一、课程概况
所属专业 |
计算机科学与技术 |
开课单位 |
大数据与人工智能系 |
课程类型 |
学科基础课程 |
课程代码 |
38410330 |
开课学期 |
2 |
学分 |
4 |
学时 |
总学时 |
课堂讲授 |
实验 |
核心课程 |
是 |
68 |
68 |
|
先修课程 |
线性代数、高等数学 |
后续课程 |
数据结构、操作系统、算法分析与设计 |
撰写人员 |
刘燕 |
课程 负责人 |
刘燕 |
审核人 |
张广海 |
教学院长 |
吴彬 |
撰写时间 |
2018年6月 |
修订时间 |
2020年1月 |
拟使用教材：
耿素云、屈婉玲.离散数学（第五版）. 北京：清华大学出版社. 2019.
学习参考教材：
1. 专著教材类
[1] 肯尼思H.罗森（Kenneth H.Rosen）著, 徐六通, 杨娟, 吴斌译, 陈琼改编. 离散数学及其应用. 北京：机械工业出版社. 2016.
[2] 耿素云、屈婉玲. 离散数学教程. 北京：北京大学出版社. 2017.
[3] 陈志奎. 离散数学. 北京：人民邮电出版社. 2015.
[4] 孙道德, 王敏生. 离散数学. 合肥：中国科学技术大学出版社. 2010.
[5] 孙道德, 王敏生. 离散数学. 北京：清华大学出版社. 2013.
[6] 左孝陵. 离散数学. 上海：上海科学技术文献出版社. 2010.
[7] 左孝陵. 离散数学理论分析题解. 上海：上海科学技术文献出版社. 1988.
2. 期刊类
[1] 离散数学杂志(美), 工业与应用数学会, ISSN:0895-4801
[2] Open Journal of Discrete Mathematics, ISSN:2161-7635
[3] 计算机学报, ISSN 0254-4164
[4] 计算机研究与发展, ISSN: 11-1777/TP
3. 网络资源类
[1] MOOC(慕课)中国：https://www.mooc.cn
[2] 刘铎. 离散数学_北京交通大学_中国大学MOOC(慕课)
[3] 王丽杰. 离散数学_电子科技大学_中国大学MOOC(慕课)
[4] 希赛网：http://www.educity.cn
[5] 爱课网：http://www.loveke.net
[6] 慕课网：https://www.imooc.com
二、课程描述
《离散数学》课程是计算机科学与技术专业的核心课程，是研究离散量的结构和相互关系的一门理论学科。通过本课程的学习，培养学生的抽象思维、严密的逻辑推理和创新能力，本课程涉及数理逻辑、集合论、图论和代数系统简介及其它五方面内容，结合具体教学安排情况，学习数理逻辑、集合论、图论三方面内容，为进一步学习相关专业课打好理论基础，并为学生今后处理离散信息，提高专业理论水平，从事计算机的实际工作提供必备的数学工具和思维动手能力，注重培养学生自主学习和逻辑推理的能力。
三、课程目标
通过离散数学的学习，能够掌握集合的概念、运算及应用，集合内元素间的关系以及集合之间的关系，掌握图论学科的基本理论知识和相关应用，注重理论、方法和实例的有机结合，努力使学生对于离散数学课程逐渐形成较为完整的知识体系，对于一些概念、性质、方法有更加深刻的理解，建立正确的形式逻辑和辩证逻辑，提高分析问题、解决问题的能力。
离散数学为今后的程序设计和开发奠定基础，是培养计算机相关专业人才的重要必修课程，希望学生务必认真学好这门课程。
不仅能为学生的相关专业课学习及将来从事的软、硬件开发打下坚实的基础，同时也能培养他们抽象思维和严格逻辑推理能力，借助离散数学形式化的描述手段，培养学生数学建模、数据分析和逻辑推理等方面的能力，进一步完善学生的自学、理解能力，为其他专业课程奠定扎实的基础知识。具体目标如表1所示。
表1 课程目标
课程目标 |
对应的专业毕业要求二级指标 |
毕业要求 |
CO1：能够利用离散数学的概念、理论和方法等基本知识，为计算机领域的具体对象建立数学模型并求解。 |
GR1.2 能针对计算机领域的具体对象建立数学模型并求解。 |
GR1 工程知识 |
CO2：以离散数学的知识点为载体，具备运用数学语言有条理、准确和系统地描述与表达复杂工程问题的能力，能够逐步形成对复杂问题进行离散建模的能力。 |
GR2.2 能基于数学、自然科学和工程科学的相关原理和数学模型方法，对计算机领域复杂工程问题进行正确描述与表达。 |
GR2 问题分析 |
CO3：综合运用形式化数理逻辑思维、离散结构建模与应用、计算与算法思维、数学抽象思维与概括等基本思想和方法，并借助文献研究，针对具体离散数学问题，调研和分析不同的解决方案。 |
GR4.1 能够基于计算机科学原理，通过文献研究或相关方法，调研和分析计算机领域复杂工程问题的解决方案。 |
GR4 研究 |
四、教学要求和方法
离散数学课程的具体教学过程中，以社会主义核心价值观为灵魂和主线，以专业技能知识为载体，深入挖掘课程蕴含的思想政治教育资源，将思想政治教育融入本课程教学过程，引导学生认识个体和集体之间的关系、透过现象看本质、树立正确的全局观念，强调理论对实践的指导作用，锻炼学生运用唯物主义辩证法分析和解决问题的能力，构建符合社会主义核心价值观的关于离散数学课程专业知识的世界观、价值观和人生观。离散数学与高等数学、线性代数等其他公共数学课程不同，但是对于学生而言，往往误把它作为同高等数学一样的公共数学课，仅仅认识到离散数学的理论公式部分，看不到其在实际在应用价值。由于学时被压缩，离散数学的特点是概念多、理论性强和高度抽象，学生学习起来往往比较困难，任课教师可以重点介绍知识的内在联系，循序渐进，相互依存，为同学们介绍命题逻辑、一阶逻辑、集合的基本概念和运算、二元关系和函数、图的基本概念、一些特殊的图和树等内容，努力做到简明扼要、深入浅出介绍最基本、最重要的内容，保持各章体系的独立性，又展现出它们的密切联系，通过大量的实例从不同的角度对一些抽象的概念进行诠释，使其易于被学生接受和理解，将同类且对比鲜明的概念或结论集中阐述，并通过典型的实例进行对比说明，使学生深刻理解它们的区别与联系，熟练掌握离散数学的课程内容和学习重点，力求提供培养学生抽象思维、缜密概括和严密的逻辑推理能力知识的同时，注重展现离散数学在计算机科学及信息科学中的应用，从而增强学生使用离散数学知识分析问题和解决问题的能力。
通过一个学期的离散数学课程学习，使学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后处理离散信息以及计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。
在教学方法上，课堂讲授采用启发式教学和探究型教学，依托知识载体，传授相关的思想和方法，引导学生探索技术前沿，激发学生主动学习的兴趣，培养学生独立思考、分析问题和解决问题的能力，引导学生主动自学获得自己想学到的知识。采用电子教案，多媒体教学与传统板书教学相结合，提高课堂教学信息量，增强教学的直观性。采用案例教学，理论教学与工程实践相结合。采用互动式教学，课内讨论和课外答疑相结合。
在学习方法上，重视对基本理论的钻研，并将理论和应用相结合。训练发现问题、解决问题的能力。明确学习各阶段的任务，认真听课，积极思考，高质量完成作业和课外阅读，并通过测验巩固所学知识。通过教材和参考资料，强化对知识点的认识。
表2 教学要求和方法
序号 |
教学内容 |
教学目标和要求 |
教学方法 |
推荐学时 |
对应的课程目标 |
1 |
概述 |
(1) 对课程名称的由来、课程简介、离散数学的发展历史、教学内容进行解读。 (2) 让学生了解为什么要学习离散数学，离散数学与其他专业课程的关联，使学生对课程学习产生兴趣，并要求学生在课外查找相关资料，补充知识。 (3) 怎么样学好离散数学，离散数学学习的方法和特点，独立自主完成课后作业及课外自主学习的要求，利用互联网上离散数学慕课进一步的自我学习。 |
线上（√） 线下（√） 讲授（√） 案例（ ） 研讨（ ） 实验（ ） 实践（ ） 双语（ ） 调研（√） 自主（√） 其它（ ） |
2 |
CO1 |
2 |
命题逻辑 |
(1) 数理逻辑中命题和联结词的概念，命题公式的含义，24个重要等值式的诠释，范式存在的意义。 (2) 根据24个等值式灵活的进行等值演算，使学生能够理解真值函数与数学函数的数同异，逻辑值与二进制的巧妙联系。 (3) 通过对推理理论的学习，在课堂上对例题的一题多解，培养学生分析问题和处理问题、思考问题的能力，学会从多种角度去分析问题和解决问题。 |
线上（√） 线下（√） 讲授（√） 案例（ ） 研讨（ ） 实验（ ） 实践（ ） 双语（ ） 调研（√） 自主（√） 其它（ ） |
26 |
CO1 CO2 CO3 |
3 |
一阶逻辑 |
(1) 主要讲述一阶逻辑三要素：个体词、谓词和量词，教会学生如何把命题用三要素表示，最终来解决命题逻辑无法解决的问题。 (2) 在教学过程中，应注意各种运算方法的特点及性能分析，对于复杂的二元谓词分析引导学生理解相关概念，并给出各中解决的方法。 (3) 补充介绍一阶逻辑推理理论，让学生学会简单推理证明，推理规则的使用技巧。 |
线上（√） 线下（√） 讲授（√） 案例（ ） 研讨（ ） 实验（ ） 实践（ ） 双语（ ） 调研（√） 自主（√） 其它（ ） |
12 |
CO1 CO2 CO3 |
4 |
集合概念、运算与一阶逻辑的关系 |
(1) 利用一阶逻辑概念解释集合的知识，把集合的五种运算和逻辑运算建立起关联。 (2) 让学生把集合的运算律和逻辑运算的24个等值式等同起来，拓宽知识面。 (3) 运用集合的包含排斥原理解决实际问题。 |
线上（√） 线下（√） 讲授（√） 案例（ ） 研讨（ ） 实验（ ） 实践（ ） 双语（ ） 调研（√） 自主（√） 其它（ ） |
4 |
CO1 CO2 |
5 |
二元关系 |
(1) 二元关系的定义，三个特殊的二元关系，关系的三种表示方法。 (2) 关系的运算和五种性质的判定方法，重要的等价关系、偏序关系的定义和区分，等价类和划分作用，哈斯图的画法和意义。 (3) 二元关系和函数之间存在什么关系，知识体系内部又有哪些关联。 |
线上（√） 线下（√） 讲授（√） 案例（ ） 研讨（ ） 实验（ ） 实践（ ） 双语（ ） 调研（√） 自主（√） 其它（ ） |
12 |
CO1 CO2 |
6 |
图的基本概念 |
(1) 图论的内容十分丰富，应用相当广泛，在计算机科学、运筹学、信息论、控制论、网络理论、博弈论等都有应用。 (2) 无向图和有向图的定义和表示，图的矩阵表示，图论中最重要的握手定理，简单通路和初级通路的概念、最短路径问题及标号法（Dijkstra算法），关键路径（项目网络图）的应用和着色问题。 (3) 学生通过图论的基本概念知识的学习，掌握图论在计算机专业课的重要地位，在分析问题、算法选择有很大的提高。 |
线上（√） 线下（√） 讲授（√） 案例（ ） 研讨（ ） 实验（ ） 实践（ ） 双语（ ） 调研（√） 自主（√） 其它（ ） |
4 |
CO1 |
7 |
特殊的图 |
(1) 二部图的判定与匹配问题的解决，欧拉图与哥尼斯堡七桥问题，哈密顿图和周游世界问题，平面图与地图着色问题。 (2) 让学生利用所学习的理论书本上的内容解决具体实际问题，分析二部图、欧拉图、哈密顿图之间的特点。 |
线上（√） 线下（√） 讲授（√） 案例（ ） 研讨（ ） 实验（ ） 实践（ ） 双语（ ） 调研（√） 自主（√） 其它（ ） |
4 |
CO1 |
8 |
树 |
(1) 无向树及生成树的定义与判断，根树及其应用。 (2) 求解最小生成树Kruskal算法（避圈法）的步骤，最优二叉树之Huffman算法及应用，即最佳前缀码的使用和行遍或周游根树的方法。 |
线上（√） 线下（√） 讲授（√） 案例（ ） 研讨（ ） 实验（ ） 实践（ ） 双语（ ） 调研（√） 自主（√） 其它（ ） |
4 |
CO1 CO2 CO3 |
五、考核方式及要求
为检验课程目标达成度，评价学生学习成果，本门课程采用过程性考核和期末终结性考核结合的方式进行考核。过程性考核包括课堂测试、课程作业、课程测验。期末终结性考核为闭卷考试。各考核环节主要考核方式及要求如表3和表4所示。
表3 课程考核方式
考核方式 |
考核环节 |
考核/评价细则 |
过程性考核 |
课堂测试 |
(1) 主要通过课堂提问或讨论等测试环节考核学生对课堂学习知识点的理解和掌握程度。 (2) 每次测试按100分制单独评分，取各次成绩的平均值按比例折算后作为课堂测试成绩。 |
课程作业 |
(1) 主要考核学生对每章节知识点的复习、理解和掌握程度。 (2) 每次作业按100分制单独评分，取各次成绩的平均值按比例折算后作为课堂作业成绩。 (3) 作业次数不少于8次。 |
课程测验 |
(1) 主要考核学生对阶段性知识点的复习、理解和掌握程度。 (2) 测验以笔试闭卷形式进行，测验题型为单项选择题、计算题、证明题等。 (3) 每次测验按100分制单独评分，取各次成绩的平均值按比例折算后作为课程测验成绩。 |
终结性考核 |
期末闭卷考试 |
(1) 主要考核离散数学基础知识的掌握程度，是对学生学习情况的全面检验。考试强调对离散数学基本概念、基本方法和技术的掌握，并通过分析、计算和证明等综合型题目考核学生运用所学方法解决问题的能力。 (2) 考核1-7章知识点及综合运用能力。 (3) 考试以笔试闭卷形式进行，考试题型为选择题、简答题、计算题、论述题、证明题等。 (4) 卷面成绩100分。卷面成绩按比例折算后计入课程总评成绩。 |
表4 课程目标达成情况评价依据
课程目标 |
课程目 标权重 |
评价依据（百分制） |
课堂测试 |
课程作业 |
课程测验 |
期末考试 |
CO1 |
52% |
8% |
16% |
10% |
18% |
CO2 |
30% |
|
|
6% |
24% |
CO3 |
18% |
|
|
|
18% |
合计 |
100% |
8% |
16% |
16% |
60% |
注：各考核环节对课程目标的支撑细则见课程考核审批表，其所占比例可根据实际教学情况进行微调。
六、课程内容
第一单元 命题逻辑的基本概念
教学重点：5种常用联结词的含义，“相容或”与“排斥或”，命题公式的分类，
命题、简单命题（原子命题），真值表，掌握命题基本概念与联结词的含义。
教学难点：蕴涵联结词与析取联结词；真值表。
主要内容：(1) 命题符号化及联结词
(2) 命题公式及分类
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成命题符号化、5种常用联结词以及命题公式等知识点练习题。
第二单元 命题逻辑的等值演算
教学重点：等值含义，24个基本等值式及置换、极小项、极大项的定义及主析取范式与主合取范式。
教学难点：等值式的定义，等值演算，极大项与极小项。
主要内容：(1) 等值演算
(2) 范式
(3) 联结词全功能集
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成等值演算、范式以及联结词全功能集等知识点练习题。
第三单元 命题逻辑的推理理论
教学重点：判断推理是否正确的三种方法，8条推理定律，11条推理规则及构造证明的直接证明法、附加前提证明法、归谬法。
教学难点：推理的形式结构理解和判断，11条推理规则的内容及名称。
主要内容： (1) 推理的形式结构
(2) 自然推理系统
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成推理规则及构造证明法等知识点练习题。
第四单元 一阶逻辑基本概念
教学重点：一阶逻辑的三要素，谓词公式与解释。
教学难点：一阶逻辑的三要素及符号化，谓词公式分类的概念。
主要内容：(1) 一阶逻辑命题符号化
(2) 一阶逻辑合式公式及其解释
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成一阶逻辑命题符号、合式公式及其解释等知识点练习题。
第五单元 一阶逻辑等值演算与推理
教学重点：一阶逻辑中的等值式、置换规则、换名规则、代替规则，补充介绍
一阶逻辑推理理论及增加4条推理规则。
教学难点：一阶逻辑的重要的等值式，使用置换规则、换名规则、代替规则求出给定公式的前束范式。
主要内容：(1) 一阶逻辑等值式与置换规则
(2) 一阶逻辑前束范式
(3) 一阶逻辑推理理论
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成一阶逻辑等值式、置换规则、前束范式以及推理理论等知识点练习题。
第六单元 集合
教学重点：集合的两种表示法，集合的基本运算及有穷集合的计数方法；
教学难点：集合的基本概念和运算；集合元素中的计数问题。
主要内容：(1) 集合的基本概念
(2) 集合的基本运算
(3) 有穷集的计数
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成集合的表示法，集合的基本运算及有穷集合的计数方法等知识点练习题。
第七单元 二元关系
教学重点：有序对，二元关系，关系的表示法，关系的运算，关系的性质和两种重要的二元关系。
教学难点：二元关系的运算；关系的闭包；等价关系与划分；偏序关系与哈斯图。
主要内容：(1) 集合的笛卡儿积与二元关系
(2) 关系的运算
(3) 关系的性质
(4) 关系的闭包
(5) 等价关系与偏序关系
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成二元关系表示法、运算方式、性质以及等价关系与偏序关系等知识点练习题。
第八单元 函数
教学重点：函数和关系的联系。
教学难点：函数的复合与反函数；双射函数。
主要内容：(1) 函数的定义和性质
(2) 函数的复合和反函数
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成函数的定义、复合函数以及反函数等知识点练习题。
第九单元 图的基本概念
教学重点：无向图与有向图的定义和图的相关概念、握手定理。
教学难点：图的基本概念；通路、回路和图的连通性；图的矩阵表示。
主要内容：(1) 图
(2) 通路与回路
(3) 图的连通性
(4) 图的矩阵表示
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成图的基本概念、通路与回路、图的连通性以及图的矩阵表示等知识点练习题。
第十单元 特殊的图
教学重点：二部图，欧拉图，哈密顿图的定义和判定；
教学难点：欧拉图的概念、性质及判断方法；哈密顿图的判别。
主要内容：(1) 二部图
(2) 欧拉图
(3) 哈密顿图
(4) 平面图
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成二部图、欧拉图、哈密顿图以及平面图等知识点练习题。
第十一单元 树
教学重点：无向树、有向树的判定及最小生成树和最优二叉树算法。
教学难点：无向树和根树的区别，最小生成树和最优二叉树算法。
主要内容：(1) 无向树及生成树
(2) 根树及其应用
学习方法：课堂认真听讲、小组学习讨论。
课后作业：完成无向树、生成树、根树、最小生成树算法以及最优二叉树算法等知识点练习题。
七、持续改进
1、根据2016版人才培养方案执行情况，对于本科阶段的学生，所开设的《离散数学》内容中知识点较多，基础知识涉及面广，在2018版人才培养方案中增加学生线上学习的环节，采用线上线下混合教学方法。
2、本课程在每轮授课过程中，根据学生的课堂测试、课程作业、课程测验等过程性评价结果以及学生反馈、教学督导等人员的听课反馈情况，及时在本轮教学过程中对不足之处进行改进。使学生能提高分析问题、解决问题和读书理解能力，课程结束后，对课程教学目标达成情况进行分析，根据分析结果，同时结合毕业生、校友、社会第三方的问卷调查、座谈会、调查报告等形式的反馈，在本课程后面轮次的教学中改进提高。
所属专业 |
计算机科学与技术 |
开课单位 |
计算机与信息学院 |
课程类型 |
专业基础课程 |
课程名称 |
离散数学 |
开课学期 |
2 |
学分 |
4 |
学时 |
总学时 |
理论学时 |
实验学时 |
核心课程 |
是 |
68 |
68 |
|
撰写人员 |
刘燕 |
课程负责人 |
刘燕 |
课程负责人检查意见： (1) 课程描述是否合理？ A.合理（√ ） B.较为合理（ ） C.不合理（ ） (2) 课程目标设置是否符合学校办学定位和人才培养目标，坚持立德树人？ A.符合（√ ） B.基本符合（ ） C.不符合（ ） (3) 课程目标是否能支撑对应的专业毕业要求二级指标？ A.能支撑（√ ） B.基本能支撑（ ） C.不能支撑（ ） (4) 教学内容及要求是否能支撑课程目标达成? A.能支撑（√ ） B.基本能支撑（ ） C.不能支撑（ ） (5) 课程考核方式是否能评价课程目标达成? A.能评价（√ ） B.基本能评价（ ） C.不能评价（ ） (6) 课程内容安排是否合理? A.合理（√ ） B.较为合理（ ） C.不合理（ ） (7) 持续改进是否符合要求？ A.符合（√ ） B.基本符合（ ） C.不符合（ ） 课程负责人总体意见： 该大纲总体符合计算机专业培养方案中的相关要求。 课程负责人（签名）： 日 期：2019.7.16 |
专业负责人检查意见： 同意课程负责人意见。 专业负责人（签名）： 日 期：2019.8.25 |
