《离散数学》教学大纲
课程代码 | 045100011 |
课程名称 | 离散数学 |
英文名称 | Discrete Mathematics |
课程类别 | 专业基础课 |
课程性质 | 必修 |
学时 | 总学时:64 实验学时:0 实习学时:0 其他学时:20(Mooc线上学时) |
学分 | 4 |
开课学期 | 第一学期 |
开课单位 | 计算机科学与工程学院 |
适用专业 | 计算机科学与技术、网络工程、信息安全 |
授课语言 | 中文 |
先修课程 | 无 |
课程对毕业要求的支撑 | 本课程对学生达到如下毕业要求有如下贡献: 工程知识:能够将数学、自然科学、工程基础和专业知识用于解决计算机复杂工程问题。 问题分析:能够应用数学、自然科学和工程科学的基本原理,识别、表达、并通过文献研究分析计算机复杂工程问题,以获得有效结论。 设计/开发解决方案:能够设计针对复杂与计算机相关工程问题的解决方案,设计满足特定需求的系统、单元(部件)或工艺流程,并能够在设计环节中体现创新意识,考虑社会、健康、安全、法律、文化以及环境等因素。 |
课程目标 | 完成课程后,学生将具备以下能力: (1)掌握离散数学的基本理论和基本知识; (2)掌握各种离散结构的描述方法、性质、推理证明方法及应用; (3)了解和掌握用离散结构的理论和方法对实际系统进行描述、分析和研究的方法。 |
课程简介 | 离散数学用数学语言描述离散系统的状态、关系和变化过程,是计算机科学与技术的形式化描述语言,是进行逻辑推理和数量分析的工具,学习离散数学可以培养学生的计算思维与逻辑推理能力、综合运用专业知识解决计算机复杂工程问题能力。离散数学是计算机科学与技术领域重要的基础课程,本课程讲授的数理逻辑,集合、函数和关系,图论三部分内容,广泛应用于计算机的后续专业课程中。学习离散数学为掌握计算机专业领域知识,及将来从事计算机科学技术的研究和工程实践打下坚实的理论基础。 |
教学内容与学时分配 | 绪论: 课程目的、意义与内容组织、学时安排介绍 1学时 教学要求:掌握学习离散数学课程的主要目的与任务,了解离散数学课程在国家信息技术发展中的作用,在计算机科学技术发展中的作用。 第一部分 数理逻辑 教学要求: 掌握数理逻辑的基本理论和基本知识,掌握命题演算,谓词演算的基本概念,命题符号化方法,推理证明方法,了解逻辑公理系统。 1、命题演算 10学时 (1)命题与联结词 2学时 (2)命题公式及其分类 1学时 (3)命题演算的关系式 2学时 (4)范式 (5)析取范式和合取范式 1学时 (6)主析取范式和主合取范式 1学时 (7)命题演算的推理 (8)推理理论 1学时 (9)推理证明方法 2学时 重点:命题的概念,联结词的定义,命题的符号化表示,命题逻辑的关系式,命题逻辑的推理理论和证明方法; 难点:命题的符号化表示,命题逻辑的关系式的证明,命题逻辑的推理和证明 2、谓词逻辑 10学时 (1)谓词逻辑的基本概念 2学时 (2)谓词公式 2学时 (3)谓词演算的关系式 3学时 (4)谓词演算的推理 3学时 重点:谓词逻辑的概念,量词,用谓词逻辑表示命题,谓词逻辑的等价式与蕴含式,谓词逻辑的推理。 难点:命题的谓词逻辑符号化表示,谓词逻辑的量词的使用,谓词逻辑的推理。 第二部分 集合、关系和函数 教学要求: 掌握集合论的基本理论和基本知识,掌握集合,关系,函数的基本概念,关系的定义、性质、运算、判定和证明方法,函数的定义,反函数和复合函数,了解集合基数,等势的概念。 1、集合 2学时 (1)集合及其表示,集合间的关系,集合的运算 1学时 (2)自然数,集合的特征函数 1学时 重点:集合间关系的表示,集合运算的表示,集合关系式的证明,集合的幂集,自然数 2、关系 13学时 (1)关系的概念 1学时 (2)关系的表示 1学时 (3)关系的运算 1学时 关系的性质 (4)关系性质 2学时 (5)关系性质的判断和证明 2学时 (6)关系的闭包 2学时 等价关系和等价类 (7)等价关系 1学时 (8)等价类、商集、划分 1学时 偏序关系 (9)偏序关系和哈斯图 1学时 (10)偏序集 1学时 重点:关系的定义和表示,关系的逆运算和复合运算,关系的性质的判断和证明,关系的闭包,等价关系和等价类,偏序关系合偏序集。 难点:关系的定义,关系的性质的判断和证明,关系的运算,等价关系和偏序关系的判断和证明. 3、函数 6学时 (1)函数的基本概念 函数的定义 0.5学时 特殊函数,单射、满射和双射函数 1.5学时 (2)复合函数和反函数 2学时 (3)集合的基数 2学时 重点:函数的概念,单射、满射和双射函数,复合函数,反函数; 难点:函数的定义,单射、满射和双射函数的判断和证明,复合函数和反函数。 第三部分 图论 教学要求: 掌握图论的基本理论和基本知识,掌握图的基本概念及其表示,掌握欧拉图,哈密尔顿图树,平面图,二分图等图模型的定义、性质及判定、证明方法,并了解有关应用。 1、图论 8学时 (1)图的概念 无向图和有向图 0.5学时 度的概念,图论的基本定理 1.5学时 图的分类 1学时 子图和补图 0.5学时 图的同构 0.5学时 (2)通路、回路和连通 通路和回路 1学时 连通的概念 1学时 (3)图的表示 1.5学时 (4)图的运算 0.5学时 重点:度的概念,图论的基本定理,图的表示,图的分类,图的同构,通路、回路和连通的概念 难点:图的概念、各类图的定义,图的同构的判断,图的连通性 2、特殊图 9学时 (1)欧拉图与哈密尔顿图 欧拉图 1学时 哈密顿图 1学时 (2)带权图 旅行商问题 0.5学时 最短路径问题 1学时 中国邮路问题 1学时 (3)匹配和二分图 匹配 0.5学时 二分图 1学时 (4)平面图 平面图的定义 1学时 平面图的欧拉公式 1学时 对偶图与图的着色 1学时 重点:欧拉图、哈密尔顿图、平面图、二分图的定义和判定 难点:欧拉图、哈密尔顿图、平面图和二分图的判定,求最短路径的Dijkstra算法,中国邮路算法。 3、树 5学时 (1)树的定义与特性 1.5学时 (2)生成树 1学时 (3)根树 根树,有序根树的遍历 1学时 (4)根树的应用 前缀码 0.5学时 最优二元树和霍夫曼编码 1学时 重点:树的定义,生成树,最小生成树,根树,有序根树的遍历,最优二元树。 难点: 掌握树的定义和性质,求最优二元树的霍夫曼算法 |
实验教学(包括上机学时、实验学时、实践学时) | 无 |
教学方法 | 课程教学以课堂教学、mooc学习、作业等共同实施。 |
考核方式 | 本课程注重过程考核,考核形式、考核内容、课程目标、成绩比例为: (1)平时作业和课堂表现(占总成绩的20%) 选做教材部分习题,考查学生对基础知识和基本理论的掌握和应用能力;课程目标1、2、3; (2)期中考试和平时测试(占总成绩的30%) 选择在线测验、课堂测验的形式,考查学生对基础知识和基本概念的掌握能力;课程目标1、2 (3)期末考试(闭卷)(占总成绩的50%) 采用笔试闭卷方式,考查学生对基础知识和基本理论的掌握,重点考查运用离散数学理论解决问题的能力;课程目标1、2、3 |
教材及参考书 | 现用教材:陈琼,马千里,周育人等,离散数学及其应用,机械出版社,2014 主要参考资料: [1] 屈婉玲,耿素云,张立昂,离散数学,高等教育出版社,2010 [2] Kenneth N.Rosen, Discrete Mathematics and its applications, 机械工业出版社,2018 |
制定人及制定时间 | 陈琼 陈伟能 马千里 胡劲松 2019年4月8日 |
“Discrete Mathematics” Syllabus
专业课程思政建设内容
课程名称 | 离散数学 |
任课教师 | 陈琼、陈伟能、马千里、胡劲松 |
职称 | 副教授、教授 |
学院 | 计算机科学与工程学院 |
育人目标 | 1.让学生了解离散数学在计算机科学中的作用,在实现中国梦中的作用,树立为中华民族的伟大复兴努力学习、努力奋斗的决心。 2.实现离散数学课程知识教学与立德树人教育的有机融合;激发学生“实干兴邦”的爱国奋斗精神。 |
教学特色 | 介绍离散数学在计算机科学、信息技术、管理科学等的应用,介绍应用离散数学理论知识解决实际问题。通过演绎推理的准确性和严密性,引导学生建立脚踏实地、诚信做人的人生观和价值观。 |
预期成效 | 1.学生能认识离散数学课程对学习计算机科学的重要意义,对科学技术发展的重要作用; 2.了解到人工智能、高科技离不开离散数学,激发学生的爱国情怀,使学生树立正确的价值观和人生观,自觉地为中华民族的复兴而努力学习。 |