离散数学-k8凯发旗舰

教学大纲 teaching syllabus

课程的英文名称:discrete mathematics

总学时:80 学分:5

适用对象:计算机科学与技术专业

先修课程:高等数学

一、课程的性质和目标要求

(1)课程的性质与任务: 离散数学是计算机科学中基础理论的核心课程。离散数学理论体系完整，结构严谨，是学习有关计算机理论与实践的一门必不可少的工具性学科。本课程的教学目的就是通过对离散数学基本理论的学习，使学生能够接受现代数学关于离散结构的观点，从系统结构的研究方法出发，研究事物间的有关属性；同时要应用数形结合方法，使事物论证简洁直观；此外要通过描述方法和缜密思维方法的训练，使学生具有良好的抽象思维和逻辑思维能力。

(2)课程的教学目标要求:离散数学是培养学生抽象思维和缜密概括能力的素质训练课程.它需要使学生紧密结合专业,为其他专业基础课程做好各种数学知识的准备,同时也要使学生兼具开拓能力.本课程总目标是训练学生具有严密的思维方法，严格证明的推理能力，应用自如的解题技巧，以及训练有素的演算能力，使学生能掌握处理各种离散结构事物的描述工具与方法，以适应学习其他专业课程的各种需要。

二、课程的教学内容、重点和难点

离散数学课程内容主要包括数理逻辑、集合论、图论、代数系统等四个部分。数理逻辑的重点是公式演算与推理证明；集合论的重点是关系理论与映射的描述；图论着重于数形结合的描述以及各种实际应用；代数系统则主要是从系统宏观的代数方法去研究客观事物的各种性质与特征。

表1:教学内容重点与难点

序号	教学内容	教学重点	教学难点
1	数理逻辑	命题符号化；公式的递归定义；谓词公式的解释；命题逻辑公式演算与推理证明；一阶逻辑公式演算与推理证明性。	命题逻辑与谓语逻辑的演绎推理。
2	集合论	二元关系的性质:自反、反自反、对称、反对称、传递、反传递；判断法:序偶，关系图，关系矩阵；关系的运算:复合关系，逆关系，混合运算，关系的闭包；其他特殊关系:等价关系，偏序关系；函数的生成与复合运算。	关系闭包；等价关系与偏序关系。
3	图论	图的表示；子图、生成子图与补图；握手定理；图的同构；图的连通性；生成树与最小生成树；根树遍历算法；最优树与哈夫曼树；欧拉图与哈密尔顿图；带权图与最短路径算法。	欧拉图与哈密尔顿图的判定方法；带权图的最短路径算法；根树的递归遍历算法。
4	代数系统	代数系统的定义及分类；代数系统的同态、同构关系；半群与幺半群的定义与性质；群的定义与性质；循环群的生成元及子群；群同态与同构；格的定义及性质；几种特殊的格（分配格、有补格、布尔格）；环和域的定义。	群的性质及其应用；格及其性质。

表2:教学内容知识矩阵:

知识块	一级知识点	二级知识点	掌握程度	评价标准	备注
数理逻辑	命题逻辑	命题、联结词与命题符号化:命题的概念，联结词,命题符号化；	掌握	1.掌握命题和公式的定义，公式的分类； 2.要求能够对语句进行形式化，并对公式熟练进行演算； 3.至少学会运用两种办法求公式的主析取（合取）范式形式。	讲授、练习
		命题公式:变元与常元，公式递归定义，指派与真值表；	熟练掌握
		重言式:重言式，矛盾式，可满足式；逻辑等价式，代入原理，替换原理，有效推理，对偶式及对偶原理；	熟练掌握
		范式:析取范式，合取范式，极大（极小）项，主析取范式，主合取范式；	熟练掌握
		联结词归约:联结词扩充，完备联结词。	掌握
	谓词逻辑	谓词与量词:个体变元（常元），个体域，谓词的定义与元数，全称量词，存在量词，量词的辖域，约束变元与自由变元；	熟练掌握	1.掌握谓词的定义及谓词公式的定义； 2.能熟练运用演算的方法求公式的前束范式； 3.能熟练对命题符号化基本技能并能够进行有效推理。	讲授、练习作业1
		谓词公式:递归定义，特性谓词，命题符号化基本技能；	熟练掌握
		谓词公式的真值:解释，逻辑等值式，有效推理；	掌握
		几个基本原理:代入原理，替换原理，对偶式及对偶原理，改名原理。	了解
集合论	集合论基础	基本概念:集体的概念，集合表示，集合的包含与相等；	掌握	1．掌握集合的基本运算及性质； 2．要求熟练运用幂集计算方法进行问题求解。	讲授、练习
		集合运算:集合的交、并、补、差、对称差、广义交、广义并，集合运算的性质；	熟练掌握
		幂集:幂集的定义与计算，幂集运算的性质。	掌握
	关系及其性质	二元关系的概念:序偶与笛卡儿积，二元关系的定义，二元关系的表示；	掌握	1．掌握二元关系的概念及其性质，以及关系与集合的关系； 2．要求灵活运用二元关系的五种性质； 3．要求熟练掌握等价关系与偏序关系的判别条件和表示方法，清楚地理解偏序关系的特殊元之间的联系以及哈斯图的应用。
		二元关系的性质:自反、反自反、对称、反对称、传递、反传递；判断法:序偶，关系图，关系矩阵；	熟练掌握
		关系的运算:复合关系，逆关系，混合运算，关系的闭包；	熟练掌握
		其他特殊关系:等价关系，偏序关系。	掌握
	函数与集合基数	函数的基本概念:函数定义，单射、满射、双射；	掌握	1．理解函数的概念以及函数与关系的区别与联系； 2．要求熟练掌握函数的复合运算与逆函数运算。
	函数与集合基数	函数运算:复合函数、逆函数；	掌握	1．理解函数的概念以及函数与关系的区别与联系； 2．要求熟练掌握函数的复合运算与逆函数运算。
图论	图的基本概念	图的定义与表示:结点，边（有向边和无向边），端点，孤立点，环，邻接，关联，零图，平凡图，（n,m）图，图的集合（图形、矩阵）表示法；	掌握	1．掌握图的基本概念与图的分类； 2．熟练运用握手定理及其推论进行分析图的性质； 3．掌握把实际问题转化成为图的形式并运用图的性质进行分析。	讲授、练习
		图的分类:无向图与有向图，简单图与多重图，无权图与有权图；	掌握
		子图与补图:子图和真子图，生成子图，导出子图，完全图，补图；	掌握
		结点度数与握手定理:结点的度数（有向图与无向图），握手定理及其推论，度数序列；	熟练掌握
		图的同构:图同构的定义与判断。	掌握
	图的连通性	通路与回路:通路与回路的定义，通路长度，简单通路与简单回路，基本通路与基本回路，距离，通路和回路的基本性质，可达和可达矩阵，可达性的判断；	掌握	1．掌握有向图和无向图中的连通性的基本概念； 2．学会运用图的矩阵表示，分析图的性质，如求两点间路径数目等。
	图的连通性	无向连通与连通分支，有向连通图（强连通、单向连通、弱连通）。	掌握	1．掌握有向图和无向图中的连通性的基本概念； 2．学会运用图的矩阵表示，分析图的性质，如求两点间路径数目等。
	特殊的图	欧拉图:欧拉通路、欧拉回路，欧拉图的判定定理及其推论，桥与割边；	熟练掌握	1．掌握欧拉图、哈密顿图、偶图、平面图的基本概念及其判断定理； 2．学会运用图模型表示和解决实际问题，如中国邮路问题、资源分配问题、排课表问题等。
		哈密顿图:哈密顿通路，哈密顿回路，哈密顿图及判定定理；	熟练掌握
		偶图:偶图定义，完全偶图，偶图的判定定理，匹配、匹配的判断定理:霍尔定理和t条件；	了解
		平面图:平面图与非平面图，面、边界、次数，欧拉公式及其应用，平面图的判定定理，对偶图。	了解
	树	树的定义与性质:树，叶子，分支点，内部结点，森林，平凡树；	掌握	1．掌握树的定义和性质，生成树的定义，根树的定义与应用； 2．熟练掌握向种算法:最小生成树算法，树的遍历算法，哈夫曼算法。	讲授、练习
		生成树:生成树、树枝和弦、生成树的补、生成树的求法（避圈法、破圈法）、最小生成树及其算法（kruskal算法和 prim算法）。	掌握
		根树:根树的定义，根树的分类，根树遍历算法，根树转化为二元树，森林转化为二元树，最优树与哈夫曼算法。	熟练掌握

三、教学形式与学时分配

章节	主要内容	学时分配
章节	主要内容	讲授	练习	测验	讨论	考察	自学	合计
	集合论基础	2
	二元关系及其性质	12
	函数	2
二	命题逻辑	10
二	谓词逻辑	10	2
三	图的基本概念	4
	图的连通性	2
	特殊图	8
	树	8	2
四	代数系统	4
	半群与群	6
	格	2
	布尔代数	2	2
合计		72	6	2				80

四．考核方法

总评成绩由平时成绩和期末考试成绩两部分构成，均按100分制计分，由任课教师评分，其中平时成绩占40%，期末考试占60%。不及格者按学校教学管理要求进行补考或重修。

	权重	评分人	考核标准	分数（100分制）
平时成绩	40%	任课教师	考勤、课堂表现、作业、期中测验	a
期末成绩	60%	任课教师	期末闭卷考试	b
总评成绩				a40% b60%

五．建议使用教材和教学参考资料

1．教材:

屈婉玲，耿素云，张立昂，离散数学，清华大学出版社，2008

2．教学参资料:

[1]古天龙,常亮,离散数学,清华大学出版社,2012.7

[2]左孝凌，离散数学，上海科学技术文献出版社，2008

[3] 徐洁磐，朱怀宏，宋方敏, 离散数学及其在计算机中的应用, 人民邮电出版社,2008

[4]bernard kolman,robert c.busby,sharoncutler ross.discrete mathematical structures(fifth edition)[m].beijing:highereducation press,2009.