离散数学教学大纲(本科)

《离散数学教学大纲(本科)》由会员分享，可在线阅读，更多相关《离散数学教学大纲(本科)（12页珍藏版）》请在金锄头文库上搜索。

1、第 - 1 - 页 共 12 页离散数学课程教学大纲一、离散数学课程说明课程英文名称：Discrete mathematics课程类型：考试课课程性质：专业技术基础课总学时： 72学时适用对象：计算机科学与技术专业本科生先修课程：高等数学线性代数（一）课程简介离散数学， 是现代数学的一个重要分支，是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。离散数学内容主要包括: 集合、映射与运算，关系，命题逻辑，谓词逻辑，代数结构，图论，以及几类特殊的图和组合计数. 通过该课程可以培养学生的抽象思维和慎密的概括能力，是计算机专业的必修课。（二）课程性质、目的和任务离散数学

2、 课程是为计算机科学与技术专业的学生开设的一门专业基础课程。随着计算机科学的发展和计算机应用领域的日益广泛，迫切需要适当的数学工具来解决计算机科学各个领域中提出的有关离散量的理论问题，离散数学就是适应这种需要而建立的，它综合了计算机科学中所用到的研究离散量的各个数学课题，并进行系统、 全面的论述， 从而为研究计算机科学及相关学科提供了有利的理论基础和工具。是学习后续专业课程不可缺少的数学工具，如：高级语言、数据结构、编译原理、操作系统、可计算性理论、人工智能、形式语言与自动机、 信息管理与检索以及开关理论等，离散数学也是研究自动控制、管理科学、 电子工程等的重要工具。教学的目的是进一步提高学生

3、的抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。并为后续课程的学习打下良好的基础。（三）与其他课程的联系除要求学生具有矩阵和矩阵运算方面的一些知识外，离散数学基本上是一门体系独立自行封闭的基础数学课程，但由于它内容抽象，理论性较强， 因此它需要学生先期有较好的数学思维的训练。最好将此课程安排在高等数学和线性代数课程之后。第 - 2 - 页 共 12 页本课程为“数据结构” 、 “数据库原理” 、 “操作系统” 、 “编 译 原 理 ” 、 “人 工 智 能 ”等许多其它专业基础课奠定必要的数学基础。（五）对先修课的要求线性代数 ：为本课程提供矩阵和矩阵运算方面的准备；

4、高等数学 ：为本课程提供必要的数学知识。（六）学时数、学分数及学时具体分配学时数： 72 学时学时数具体分配: 教学内容讲授实验 /实践合计第一章集合、映射与运算9 9 第二章关系11 11 第三章命题逻辑11 11 第四章谓词逻辑7 7 第五章代数结构8 8 第六章图论10 10 第七章几类特殊的图10 10 第八章组合计数6 6 合计72 72 （七）教学方式：使用多媒体教室以教师讲解为主的课堂教学方式( 八）考核方式和成绩记载说明考核方式为考试。严格考核学生出勤情况，达到学记管理的旷课量取消考试资格。综合成绩根据平时成绩和期末成绩评定，平时成绩占30，期末成绩占70。二、大纲内容第1章集

5、合、映射与运算1、教学目标：1、正确理解并熟记集合，集合的基数，子集，幂集等概念；2、 能理解映射的有关概念、性质，掌握逆映射和复合映射的计算；3、掌握运算的定义及其性质；4、熟练掌握集合的求并、交、补，差集及对称差的运算；5、了解集合的划分和覆盖概念；第 - 3 - 页 共 12 页6、了解集合对等的定义，掌握集合基数的概念。2、教学内容（考核要求）：1.1 集合的有关概念1.1.1 集合1.1.2 子集1.1.3 幂集1.1.4 n元组1.1.5 笛卡儿积1.2 映射的有关概念1.2.1 映射的定义1.2.2 映射的性质1.2.3 逆映射1.2.4 复合映射1.3 运算的定义及性质1.3.

6、1 运算的定义1.3.2 运算的性质1.4 集合的运算1.4.1 并运算1.4.2 交运算1.4.3 补运算1.4.4 差运算1.4.5 对称差运算1.5 集合的划分与覆盖1.5.1 集合的划分1.5.2 集合的覆盖1.6 集合的对等1.6.1 集合对等的定义1.6.2 无限集合1.6.3 集合的基数1.6.4 可数集合1.6.5 不可数集合1.6.6 基数的比较第2章关系第 - 4 - 页 共 12 页1、教学目标：1、基本概念要清楚；(1)熟练掌握关系的三种表示法；(2)能够判定关系的性质（等价关系或偏序关系）；(3)掌握含有关系运算的集合等式；(4)掌握等价关系、等价类、商集、划分、哈斯

7、图、偏序集等概念；2.以下基本运算要熟练: (1)A B, dom R, ranR, fldR, R1, R S , Rn , r(R), s(R), t(R) ；(2)求等价类和商集A/R；(3)给定 A 的划分，求出所对应的等价关系；2)求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界。3.掌握基本的证明方法：证明涉及关系运算的集合等式、证明关系的性质、证明关系是等价关系或偏序关系。4.给定 f, A, B, 判别 f 是否为从A 到 B 的函数；5.判别函数 f：AB 的性质（单射、满射、双射）；6.熟练计算函数的值、像、复合以及反函数；7.证明函数 f：AB 的性

8、质（单射、满射、双射）；8.给定集合 A, B，构造双射函数f：AB 。2、教学内容（考核要求）：2.1 关系的概念2.1.1 n 元关系的定义2.1.2 2 元关系2.1.3 关系的定义域和值域2.1.4 关系的表示2.1.5 函数的关系定义2.2 关系的运算2.2.1 关系的集合运算2.2.2 关系的逆运算第 - 5 - 页 共 12 页2.2.3 关系的复合运算2.2.4 关系的其他运算2.3 关系的性质2.3.1 自反性2.3.2 反自反性2.3.3 对称性2.3.4 反对称性2.3.5 传递性2.4 关系的闭包2.4.1 自反闭包2.4.2 对称闭包2.4.3 传递闭包2.5 等价关

9、系2.5.1 等价关系的定义2.5.2 等价类2.6 相容关系2.6.1 相容关系的定义2.6.2 相容类2.7 偏序关系2.7.1 偏序关系的定义2.7.2 偏序集的哈斯图2.7.3 偏序集中的特殊元素第3章命题逻辑1、教学目标：1、理解命题和逻辑联结词的基本概念；2、掌握公式分类和真值表构造。3、理解命题等值关系式；4、掌握公式的析取范式和合取范式；5、了解联结词的完备集。6、掌握重要的重言蕴涵式第 - 6 - 页 共 12 页7、理解推理的形式结构和自然推理系统P2、教学内容（考核要求）：3.1 命题的有关概念3.2 逻辑联结词3.2.1 否定联结词3.2.2 合取联结词3.2.3 析取

10、联结词3.2.4 异或联结词3.2.5 条件联结词3.2.6 双条件联结词3.2.7 与非联结词3.2.8 或非联结词3.2.9 条件否定联结词3.3 命题公式及其真值表3.3.1 命题公式的定义3.3.2 命题的符号化3.3.3 命题公式的真值表3.3.4 命题公式的类型3.4 逻辑等值的命题公式3.4.1 逻辑等值的定义3.4.2 基本等值式3.4.3 等值演算法3.4.4 对偶原理3.5 命题公式的范式3.5.1 命题公式的析取范式及合取范式3.5.2 命题公式的主析取范式及主合取范式3.6 联结词集合的功能完备性3.6.1 联结词的个数3.6.2 功能完备联结词集第 - 7 - 页 共

11、 12 页3.7 命题逻辑中的推理3.7.1 推理形式有效性的定义3.7.2 基本推理规则3.7.3 命题逻辑的自然推理系统第4章谓词逻辑1、教学目标：1、掌握谓词、全称量词、存在量词等概念学会使用它们符号化一些命题，并能够构成一些较复杂的命题。2、掌握谓词公式的概念，并能够判定给定公式是否为谓词的合适公式3、掌握约束变量、自由变量的概念，并能够正确的使用换名规则4、掌握永真公式、永假公式可满足公式等概念。5、掌握谓词公式的等价蕴含等概念，熟记基本的等价式、蕴含式会证明更复杂的等价式蕴含式。6、掌握前束范式的概念，并能够将一谓词公式化成与之等价的前束范式；7、掌握谓词演算的推理理论，并能够正确

12、使用推理规则进行有效推理并能够判断一推理过程是否正确。2、教学内容（考核要求）：4.1 个体、谓词、量词和函词4.1.1 个体4.1.2 谓词4.1.3 量词4.1.4 函词4.2 谓词公式及命题的符号化4.2.1 谓词公式4.2.2 命题的符号化4.3 谓词公式的解释及类型4.3.1 谓词公式的解释4.3.2 谓词公式的类型4.4 逻辑等值的谓词公式4.4.1 谓词公式等值的定义第 - 8 - 页 共 12 页4.4.2 基本等值式4.5 谓词公式的前束范式4.5.1 谓词公式的前束范式的定义4.5.2 谓词公式的前束范式的计算4.6 谓词逻辑中的推理4.6.1 逻辑蕴涵式4.6.2 基本推

13、理规则4.6.3 谓词逻辑的自然推理系统第5章代数结构1、教学目标：1、判断给定集合和运算能否构成代数系统2、判断给定二元运算的性质和特异元素3、了解同类型和同种代数系统的概念4、了解子代数的基本概念。5、深刻理解和掌握代数系统的基本概念和运算掌握半群和独异点的概念及性质；群的定义及性质；了解子群的概念，子群判定定理；陪集的概念， 拉格朗日定理； 正规子群的概念，正规子群的性质及判定；掌握群的同态概念；循环群的概念，循环群的性质，应用相关定理；置换群的概念，置换群的性质。环的概念及性质；域的概念及性质2、教学内容（考核要求）：5.1 代数结构简介5.1.1 代数结构的定义5.1.2 两种最简单

14、的代数结构: 半群及独异点5.1.3 子代数5.1.4 代数结构的同态与同构5.2 群的定义及性质5.2.1 群的有关概念5.2.2 子群5.2.3 群的同态5.3 环和域第 - 9 - 页 共 12 页5.3.1 环的定义5.3.2 几种特殊的环5.3.3 域的定义5.3.4 有限域5.4 格与布尔代数5.4.1 格的定义和性质5.4.2 分配格5.4.3 有补格5.4.4 布尔代数第6章图论1、教学目标：1、深刻理解握手定理及推论的内容并能灵活地应用它们；2、深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系；3、记住通路与回路的定义、分类及表示

15、法；4、深刻理解与无向图连通性、连通度有关的诸多概念；5、会判别有向图连通性的类型；6、熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵。2、教学内容（考核要求）：6.1 图的基本概念6.1.1 图的定义；6.1.2 邻接6.1.3 关联6.1.4 简单图6.2 节点的度数6.3 子图、图的运算和图同构6.3.1 子图6.3.2 图的运算6.3.3 图同构6.4 路与回路第 - 10 - 页 共 12 页6.4.1 路6.4.2 回路6.5 图的连通性6.5.1 无向图的连通性6.5.2 无向连通图的点连通度与边连通度6.5.3 有向图的连通性6.6 图的矩阵表示6.6.1

16、图的邻接矩阵6.6.2 图的可达矩阵6.6.3 图的关联矩阵6.7 赋权图及最短路径6.7.1 赋权图6.7.2 最短路径第7章几类特殊的图1、教学目标：1、了解二分图与完全二分图掌握二分图中的匹配2、理解欧拉图、半欧拉图的定义及判别定理；3、刻理解哈密顿图、半哈密顿图的定义；4、 哈密顿图的必要条件判断某些图不是哈密顿图. 会用充分条件判断某些图是哈密顿图. 要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件。5、深刻理解无向树的定义及性质；6、熟练地求解无向树；7、准确地求出给定带权连通图的最小生成树；8、深刻理解基本回路、基本割集的概念，并对给定的生成树会求出它们；9、理解根树及其分类等概念；10、会画 n 阶（ n 较小）非同构的无向树及根树（1 n 6） ；11、熟练掌握求最优树及最佳前缀码的方法。2、教学内容（考核要求）：7.1 欧拉图7.1.1 欧拉图的有关概念第 - 11 - 页 共 12 页7.1.2 欧拉定理7.1.3 中国邮递员问题7.2 哈密尔顿图7.2.1 哈密尔顿图的有关概念7.2.2 哈密尔顿图的必要条件