《离散数学》是应计算机科学的发展而形成和组合起来的一门新型交叉课程,涵盖了计算机科学对数学的一些基本要求。通过该课程的学习能为计算机科学相关的后继课程打下必备的数学基础。
《离散数学》作为一门数学课程,它具有数学的严谨性,但相对一般数学课程就理论而言它比较浅显,同学们也只需要具备中学数学知识即可学习;作为计算机科学的基础,它又具有应用数学的特点。
本课程负责人金贤安教授先后在厦门大学数学科学学院、软件学院和信息学院从事该课程教学工作十余年,课程团队还包括目前任职台湾屏东大学的罗元勋博士和厦门大学数学科学学院杨维玲博士以及两位研究生助教。
本课程我们将只介绍我们认为的《离散数学》最基础和最核心的内容:包括数理逻辑、集合论和图论三大部分,每个部分包括引言和9讲。适合数学类、计算机类各专业大学生和其它专业感兴趣的大学生选修。我们将根据大家的反馈,适时推出该课程的提高部分。
通过课程学习,使学生了解离散数学所涵盖的内容及背景;掌握离散数学的基本概念,离散数学常用的基本方法、手段、技巧,具备较强的分析论证能力和一定的数学抽象思维能力,能将常用的离散数学思想方法运用到计算机科学中解决相关的实际问题。
完成课程全部学习任务。每部分学习结束提供两份单元测试卷,每份分数占比5%,平时成绩10%,期末考试分数占比60%。
只需中学数学和矩阵知识。
1. 屈婉玲,耿素云,张立昂,离散数学,高等教育出版社,第二版,2015年。
2. R. Johnsonbaugh, Essential Discrete Mathematics, Macmillan Publishing Company, 1987.
3. D. J. Velleman, 怎样证明数学题,人民邮电出版社,2009。
4. J.A.邦迪,U.S.R.默蒂,图论及其应用,科学出版社,1984。
5.王义和,离散数学引论,哈尔滨工业大学出版社,2019.
《离散数学》课程说明
一、课程基本情况
课程名称 | 离散数学 | |||
Discrete Mathematics | ||||
课程类别 | □核心 √必修 □任选 □限选 | 课程代码 | 10822603 | |
学 分 | 4 | 执行学期 | 第2学期 | |
开课单位 | ||||
适用专业 | 数据科学与大数据技术 | 专业集群 | 工程教育类 | |
先修课程 | 线性代数 | |||
后续课程 | 高级语言程序设计、操作系统、计算机组成原理、数据结构与算法、数据库原理及应用、面向对象程序设计、大数据应用开发语言 |
二、课程性质与作用
《离散数学》是为数据科学与大数据技术专业一年级开设的一门专业必修课程。主要介绍集合论、代数系统、图论、数理逻辑等方面的基本知识,使学生掌握处理离散问题常用的方法,进一步增强学生运用数学的方法识别、表达、分析复杂工程问题的能力。
三、课程目标
本课程根据数据科学和大数据技术专业的需要,以离散量为研究对象,内容丰富,涉及面较宽。课程概念多、定理多、推理多,部分内容较为抽象。但离散数学的大部分概念与人们的自然思维习惯很接近,容易理解。利用归纳、类比、猜测、推演等数学方法讲授定理定义的内涵和外延。
具体目标如下:
目标1:掌握离散数学中的基本知识与基本原理;
目标2:具备一定的逻辑思维能力和抽象思维能力;
目标3:具备用离散数学的方法表达、分析工程问题的初步能力;
目标4:养成科学严谨的态度。
一级指标 | 二级指标 | 课程培养要求(三级指标) |
1.能够将数学、自然科学、工程基础和数据科学与大数据技术专业知识,用于解决所面临的复杂工程问题。 | 1.1 能够应用数学与自然科学的基本知识正确表述复杂工程问题 | 1.1.1掌握离散数学的基本知识与基本原理 |
1.1.2 熟悉离散数学演算的基本能力和基本技巧 | ||
1.1.3掌握一定的逻辑思维能力和抽象思维能力 | ||
1.1.4具备将离散数学理论与实际问题联系的能力 | ||
1.1.5具备科学严谨态度 | ||
1.2 能够针对一个系统或者过程建立数学模型并进行求解 | 1.2.1能对简单的实际问题进行分析并建立数学模型。 | |
1.2.2根据数学模型设计算法。 | ||
1.2.3能进行简单算法的优化与改善。 | ||
2.能够应用数学、自然科学和数据科学与大数据技术领域的基本原理,识别、表达、分析复杂工程问题及其解决方法,以获得有效结论。 | 2.4 掌握应用数学、自然科学和数据科学的基本原理,证实问题识别和表达的合理性 | 2.4.1具备较好的数学原理应用能力。 |
2.4.2具备良好的逻辑推理能力。 | ||
2.4.3 能够应用数学的基本原理验证解决方案的合理性。 | ||
4.能够针对复杂数据科学与大数据技术问题,依据科学原理设计和实施工程实验,并能够对实验结果进行分析处理,采用科学分析方法对复杂问题进行研究,并通过信息综合得到合理有效的结论。 | 4.1 能够运用数据科学的设计思路和基本原理,设计实验,并对实验结果进行科学有效的分析 | 4.1.1能根据现实问题建立数学模型。 |
4.1.2能根据数学知识对程序执行结果,分析实验数据的有效性。 |
四、课程培养标准
五、课程教学内容与学时分配
(一)、总体安排
模块 名称 | 主要内容 | 学时 | 教学方法 | 评价要点 | 备注 |
集合论 (20学时) | 1.集合的基本概念 | 2 | 讲授 | 1.理解计算思维; 2.熟练掌握集合的基本概念; 3.理解并掌握几个特殊集合的定义。 | 进行集合论模块的答疑和单元测试 |
2.集合的运算 | 2 | 讲授 | 1.理解和掌握幂集这一基本概念; 2.熟练掌握集合的并、交、差、补、对称差运算; | ||
3.△笛卡尔积与关系的基本概念 | 2 | 讲授 | 1.理解笛卡尔积的定义; 2.理解笛卡尔积这种新的集合运算的本质; 3.理解和掌握关系的基本概念。 | ||
4.★关系的表示 | 2 | 讲授 | 1.掌握关系图; 2.掌握关系矩阵。 | ||
5. ★△关系的复合运算 | 2 | 讲授 | 1.关系的复合运算的定义和运算方法; 2.用关系矩阵的乘法(布尔乘法)运算求复合关系; 3.用关系图求定义在一个集合A上关系的复合运算。 | ||
6.关系的基本性质和关系的闭包运算 | 4 | 讲授 | 1.理解关系的性质; 2.掌握关系性质的特点; 3.理解掌握关系的闭包运算。 | ||
7.★△等价关系与偏序关系 | 4 | 讲授 | 1.掌握等价关系的定义; 2.理解并掌握等价关系与等价分划之间的对应关系。 3.掌握偏序关系的定义; 4.理解并掌握偏序关系的性质; 5.理解并掌握描述偏序关系的图示——哈斯图。 | ||
8. 函数 | 2 | 课堂讨论 | 1.掌握判断任意给定的关系是否是函数的一般判断方法; 2.理解和掌握函数的分类。 | ||
代数 系统 (12学时) | 1.代数系统 | 2 | 讲授 | 1.理解狭义运算到广义运算的变迁; 2.理解运算和运算表的基本定义; 3.理解并掌握与运算相关的四种特殊元素。 |
|
2.代数系统的基本概念 | 2 | 讲授 | 1.理解并掌握代数系统的基本概念; 2.理解抽象代数系统的基本概念; 3.理解并掌握整环这一抽象代数系统的定义及使用方法。 | ||
3.★△同态和同构 | 2 | 讲授 | 1.理解并掌握同态的基本概念及使用方法; 2.理解并掌握同构的定义及应用; 3.理解如何站在计算机专业的角度引入同构这个概念的重要意义。 | ||
4.群的基本概念与分类 | 2 | 讲授 | 1.理解并掌握二元代数——群的定义; 2.理解并掌握阿贝尔群、循环群的基本概念; 3.理解并掌握置换群的基本定义。 | ||
5.群的基本性质 | 2 | 讲授 | 1.理解并掌握群的基本性质; 2.理解并掌握群的周期性质。 3.理解并掌握子群以及与子群相关的一些基本概念。 | ||
6.★△子群与正规子群 | 2 | 讲授 | 1.理解并掌握正规子群的定义; 2.理解并掌握拉格朗日定理; 3.理解并掌握能用满同态关联起来的两个群所应当满足的性质。 | ||
图论 (16学时) | 1.图的基本概念 | 2 | 讲授 | 理解并掌握与图相关的全部基本概念; | 进行代数系统和图论模块的答疑单元测试 |
2.★图的表示 | 2 | 讲授 | 1.理解图的表示 2.掌握图的四种矩阵表示方法以及它们各自的优缺点 | ||
3.图的连通性 | 3 | 讲授 | 1.理解并掌握与图的连通性相关的一系列基本概念和定义; 2.理解并掌握连通度的基本概念及其定义。 | ||
4.★特殊的图 | 5 | 讲授 | 1.理解并掌握欧拉图的基本概念和基本性质(怎样判断一个图是否是欧拉图); 2.了解汉密尔顿图的基本概念和基本性质。 | ||
5.△树 | 4 | 讲授 | 1.理解并掌握树和森林的基本定义和基本概念; 2.理解并掌握树的基本性质。 3.掌握求无向带权树的最小生成树的算法。 4.理解并掌握有向树的基本概念。 5.了解有向二元树的三种遍历方式——先根遍历、中根遍历、后根遍历; 6.理解并掌握完全二元树的性质; 7.了解最优二元树的构造方法。 | ||
命题 逻辑 (14学时) | 1.★△命题与命题联结词 | 2 | 讲授 | 1.了解命题的基本概念; 2.理解并掌握命题联结词及它们的使用方法; 3.掌握命题的符号化。 | 进行命题逻辑和谓词逻辑两模块的答疑和单元测试 |
2.★命题公式及命题公式的等值关系 | 2 | 讲授 | 1.理解命题公式的递归定义; 2.理解并掌握命题公式的分类; 3.掌握命题公式的等值演算。 | ||
3.命题公式的蕴含关系 | 2 |
| 1.掌握命题公式的第二种关系——蕴含关系; 2.理解蕴含关系的本质; 3.理解并掌握怎样利用蕴含关系模拟逻辑推理过程。 | ||
4.★命题公式的范式 | 4 |
| 1.掌握合取范式和析取范式的定义及应用; 2.理解和掌握主合取范式与主析取范式的定义及应用。 | ||
5.△命题演算的推理理论 | 4 |
| 1.理解命题演算推理的基本方法; 2.理解并掌握用形式证明的方法实现命题演算的推理。 | ||
谓词 逻辑 (10学时) | 1.谓词、个体与量词 | 2 | 讲授 | 1.理解谓词、个体和量词的定义和使用方法; 2.掌握使用谓词、个体与量词实现对自然语言描述的命题进行符号化。 | |
2.★谓词逻辑公式及其解释 | 4 | 讲授 | 1.理解并掌握一阶语言(谓词逻辑公式)的递归定义; 2.理解并掌握约束变元与自由变元的基本概念; 3.掌握使用换名规则与代入规则的方法和用法。 | ||
3.范式 | 2 | 讲授 | 1.了解两个谓词公式是等值的证明方法; 2.了解前束范式。 | ||
4.△谓词演算的推理理论 | 2 | 讲授 | 1.理解并掌握谓词逻辑的推理规则; 2.理解并掌握谓词演算的形式证明方法。 | ||
合计 学时 | 各项教学内容的学时总数应为该门课程的总学时数,讲授比例原则上不超过总学时数的80% |
注:★表示重点内容,△表示难点内容
(二)、教学过程
六、实践教学内容与安排
实验序号 | 实践名称 | 实践内容 | 实践学时 | 实践类型 | 每组人数 | 备注 |
1 | XX | XX |
|
|
|
|
七、项目教学内容与安排
项目序号 | 项目名称 | 项目内容 | 项目学时 | 项目类型 | 每组人数 | 备注 |
1 | XX | XX |
|
|
|
|
八、课程培养标准实现矩阵(三级矩阵)
《离散数学》课程培养要求实现矩阵(三级矩阵)
课程模块 课程培养要求 | 集合论 | 代数 系统 | 图论 | 数理 逻辑 |
1.能够将数学、自然科学、工程基础和数据科学与大数据技术专业知识,用于解决所面临的复杂工程问题。 |
|
|
|
|
1.1 能够应用数学与自然科学的基本知识正确表述复杂工程问题 |
|
|
|
|
1.1.1掌握离散数学的基本知识与基本原理 | H | H | H | H |
1.1.2 熟悉离散数学演算的基本能力和基本技巧 | H | H | H | H |
1.1.3掌握一定的逻辑思维能力和抽象思维能力 | M | H | L | H |
1.1.4具备将离散数学理论与实际问题联系的能力 |
| L | M |
|
1.1.5具备科学严谨态度 | L | M |
| H |
1.2 能够针对一个系统或者过程建立数学模型并进行求解 |
|
|
|
|
1.2.1能对简单的实际问题进行分析并建立数学模型。 |
| L | M |
|
1.2.2根据数学模型设计算法。 | H | H | H | H |
1.2.3能进行简单算法的优化与改善。 |
| M |
| L |
2.能够应用数学、自然科学和数据科学与大数据技术领域的基本原理,识别、表达、分析复杂工程问题及其解决方法,以获得有效结论。 |
|
|
|
|
2.4 掌握应用数学、自然科学和数据科学的基本原理,证实问题识别和表达的合理性 |
| L | M | M |
2.4.1具备较好的数学原理应用能力。 |
| L |
| L |
2.4.2具备良好的逻辑推理能力。 |
| H |
| H |
2.4.3 能够应用数学的基本原理验证解决方案的合理性。 | M | M | L |
|
4.能够针对复杂数据科学与大数据技术问题,依据科学原理设计和实施工程实验,并能够对实验结果进行分析处理,采用科学分析方法对复杂问题进行研究,并通过信息综合得到合理有效的结论。 |
|
|
|
|
4.1 能够运用数据科学的设计思路和基本原理,设计实验,并对实验结果进行科学有效的分析 |
|
|
|
|
4.1.1能根据现实问题建立数学模型。 | H | H | L |
|
4.1.2能根据数学知识对程序执行结果,分析实验数据的有效性。 |
| L |
| M |
九、课程评价考核方案
表1 离散数学课程考核细则
考核环节 | 考核要求 | 分值比例(%) | ||
分项 | 总评 | |||
平时考核 | 出勤 | 高于95%记10分,90%到95%记5到9分,85%到90%记1到4分,其余0分(教师严格考勤,以教师上课点名册为依据) | 10 | 40% |
平时作业 | 布置5次作业,每次2分 (注:教师批阅作业后,部分以电子作业或以纸质作业扫描后上交学院留存) 第1次作业主要以集合论的相关知识点为主要内容; 第2次作业主要以代数系统的相关知识点为主要内容; 第3次作业主要以图论的相关知识点为主要内容; 第4次作业主要以命题逻辑和谓词逻辑的相关知识点为主要内容; 第5次作业主要以期末总结为主要内容。 | 10 | ||
课堂表现 | 包括回答问题、讨论、学生向老师请教问题等(以老师的课堂记录本为依据) | 10 | ||
单元测试 | 四次模块测试,共10分 (注:测试结束后,教师通过自己批阅或平行班级学生之间相互批阅的形式完成,以电子作业或以纸质作业扫描后上交学院留存) 第1次测试重点集合论相关知识点; 第2次测试重点为代数系统相关知识点; 第3次测试重点为图论相关知识点; 第4次测试重点为命题逻辑和谓词逻辑相关知识点。 | 10 | ||
期末考核 | 闭卷考试 | 60 | 60% |
表2 《离散数学》课程培养标准三级指标对应的考核环节
考核指标 | 考核环节 | |||||
作业 | 课堂 表现 | 期末 总结 | 单元 测试 | 期末 考试 | ||
1.能够将数学、自然科学、工程基础和数据科学与大数据技术专业知识,用于解决所面临的复杂工程问题。 |
|
|
|
|
| |
1.1 能够应用数学与自然科学的基本知识正确表述复杂工程问题 |
|
|
|
|
| |
1.1.1掌握离散数学的基本知识与基本原理 | √ | √ | √ | √ | √ | |
1.1.2 熟悉离散数学演算的基本能力和基本技巧 | √ | √ | √ | √ | √ | |
1.1.3掌握一定的逻辑思维能力和抽象思维能力 | √ | √ |
|
| √ | |
1.1.4具备将离散数学理论与实际问题联系的能力 |
| √ |
| √ |
| |
1.1.5具备科学严谨态度 | √ | √ |
|
| √ | |
1.2 能够针对一个系统或者过程建立数学模型并进行求解 |
|
|
|
|
| |
1.2.1能对简单的实际问题进行分析并建立数学模型。 | √ |
|
| √ |
| |
1.2.2根据数学模型设计算法。 | √ | √ |
| √ | √ | |
1.2.3能进行简单算法的优化与改善。 |
| √ |
|
|
| |
2.能够应用数学、自然科学和数据科学与大数据技术领域的基本原理,识别、表达、分析复杂工程问题及其解决方法,以获得有效结论。 |
|
|
|
|
| |
2.4 掌握应用数学、自然科学和数据科学的基本原理,证实问题识别和表达的合理性 |
|
|
| √ | √ | |
2.4.1具备较好的数学原理应用能力。 |
| √ | √ | √ | √ | |
2.4.2具备良好的逻辑推理能力。 |
| √ |
| √ | √ | |
2.4.3 能够应用数学的基本原理验证解决方案的合理性。 | √ | √ |
|
|
| |
4.能够针对复杂数据科学与大数据技术问题,依据科学原理设计和实施工程实验,并能够对实验结果进行分析处理,采用科学分析方法对复杂问题进行研究,并通过信息综合得到合理有效的结论。 |
|
|
|
|
| |
4.1 能够运用数据科学的设计思路和基本原理,设计实验,并对实验结果进行科学有效的分析 |
|
|
|
|
| |
4.1.1能根据现实问题建立数学模型。 | √ | √ | √ | √ |
| |
4.1.2能根据数学知识对程序执行结果,分析实验数据的有效性。 |
|
|
|
| √ |
注一:关于成绩的计算。
该课程强调过程考核,计算方法为:
课程总成绩=平时作业10分+模块测试30分+期末考试试卷成绩60分。
1、课程的考核中综合成绩高于60分且试卷成绩低于45分者该课程按不合格处理。
2、为保证教学质量与后续课程的顺利进行,对本课程考核不合格经补考还不及格的同学必须在第二学期立刻开设重修班进行重修学习。
3、为减轻重修学生的学习压力,重修课程考核必须给学生布置适当作业,并以试卷考核为准。重修考试中卷面成绩在50分(不含50分)以下的按实际成绩积分;卷面成绩在50分(含50分)到59分的积分为60分;卷面成绩在60分以上的按实际成绩积分。
注二:关于模块测试。
本课程需进行4次模块测试,第1次测试重点为集合论;第2次测试重点代数系统。第3次测试重点为图论,第4次测试重点为数理逻辑。每次测试学生能在2个小时内完成为宜。
注三:关于期末考试。
试卷组卷方式:试卷按模块组卷,第1模块为集合论模块、第2模块为命题逻辑模块、第3模块为谓词逻辑模块、第4模块为图论模块、第5模块为代数系统模块。每个模块都必须考核,分值在10分以上25分以下。
十、教学方法改革方案
改革课堂教学模式:传统的教学模式的程式是: 定义→性质和定理→运算(方法和技巧) →应用,我们称之为“演绎法”。它以传授知识为主,对学生应用数学知识去解决实际问题的能力没能进行有效的训练,不利于学生创新精神和创造思维能力的培养。要改革这种教学思维模式,就必须构建以探求知识为主的模式,它的基本过程是: 问题→猜想→实验→证明,称为“归纳法”。这是透过现象抓本质的一种教学方法,通过对各种现象的观察、分析和归纳而发现问题、研究问题、解决问题,其最大的优点是有利于激发学生的学习和研究兴趣,培养他们发散思维能力和创新精神,这种思维始于“直觉”(发散思维) 而止于演绎(收敛思维),再现了科学探索和科学发现的过程,符合从具体到抽象的思维转变。
在离散数学融入数学建模的思想:在讲授理论知识时,要选择一些网络、编码、图形处理等现实问题,引导学生进行分析,通过适当的简化和合理的假设,建立简单的数学模型并进行求解,从而去解释现实问题。这样既让学生体会了离散数学在解决现实问题中的重要作用,又利于提高学生分析问题和解决问题的能力,同时也有助于提高学生抽象思维能力。另外,布置课外练习时应加入计算机相关的工程问题,让学生分组合作完成。这样不但是离散数学课程的补充和升华,而且还可以培养学生的团队精神和互相合作的精神。
在讲课中注意黑板与多媒体教学的有机结合。由于离散数学本身逻辑性很强,对于较复杂的理论证明,可以在黑板上进行推导,使学生能跟上老师的思路。而对于离散数学发展史、书写量较大的内容以及一些抽象概念的几何背景等,则可通过多媒体给学生演示。