《离散数学(II)》课程教学大纲
一、课程基本信息
课程名称
离散数学(II)
课程英文名称
Discrete
Mathematics(II)
总学时
40
讲课学时
34
实验学时
上机学时
习题课学时
6
周学时
3
学分
2.5
开课单位
计算机软件与理论研究所
先修课程
离散数学(I)
课程性质
数学与自然科学基础
课程类型
必修课
选用教材
屈婉玲、耿素云、张立昂.离散数学.北京：高等教育出版 . 2008
[1]左孝凌等编著.离散数学.上海：上海科学技术文献出版 . 1982
[2]屈婉玲、耿素云、张立昂.离散数学学习指与习题解析.北京：高等教育出版 . 2008
[3] Kenneth
H. Rosen (美)著.袁崇义，屈婉玲，王捍贫，刘田译.离散数学及其应用.北京：机械工业出版 . 2007
本课程地位
(作用)和任务
《离散数学》的第二部分内容，主要学习与代数结构及图论有关的基本概念、基本理论和基本方法，以第一部分相同，本课程是讨论在计算机科学研究中所用到的数学基础，它是计算机科学与技术专业的重要的理论基础课，也是计算机专业的主干课。所不同的是，本课程更注重理论联系实际，很多内容都源于实际问题，因而相应知识具有很强的应用前景。通过本课程的教学，除了使学生掌握代数结构及图论等基本知识外，还能培养学生抽象的逻辑思维和严密的逻辑推理能力，以及应用理论知识解决实际问题的能力，为学习好后继课以及将来进一步从事计算机科学的研究、发展计算机科学技术打下坚实的理论基础。
6基础组合计数(6学时)
6.1加法法则和乘法法则掌握两个基本的计数原则：加法法则和乘法法则，可以用它们求解许多不同的计数问题。
6.2排列和组合掌握通过计数解决有穷极不同个体的无序选择和有序安排的技术。
6.3二项式定理与组合恒等式掌握二项式幂展开系数的性质及重要的组合恒等式。
6.4多项式定理掌握多项式系数的性质，理解多项式系数的组合意义。
7代数结构(12学时)
7.1代数系统的概念掌握二元运算、N元运算、代数系统的定义、有限代数系统、同类型的代数系统和子代数系统的基本概念。
7.2二元运算的性质掌握二元运算的十个基本性质，即封闭性、交换律、可结合律、幺元、零元、幂等元、逆元可消去性、可分配律和吸收律。
7.3代数系统的同态与同构
⑴掌握基本概念：代数系统同态、满同态、单一同态、同构、自同构的定义、同态像、同态核。
⑵理解代数系统间的同构关系是等价关系
⑶掌握同构的代数系统性质的保持特征：保持交换律、可结合律、幺元、零元、幂等元、逆元、可消去性，并掌握同态、同构的代数系统性质的保持
7.4半群与独异点掌握半群与独异点的定义、半群与独异点的有关性质、可交换半群与可交换独异点、子半群与子独异点。
7.5群
⑴掌握群的定义、交换群、有限群。
⑵掌握群的性质：满足可消去性、群方程可解性、无零元、除幺元外无其它幂等元、有限群的运算表的特点。
⑶掌握群的阶、群的元素的阶及其有关性质。
7.6置换群与循环群
⑴了解群的置换、置换的复合运算(左复合、右复合)、置换群、对称群、置换群与有限群的关系
⑵掌握循环群的定义、循环群的循环周期、两个重要的循环加法群(，)。
7.7子群
⑴掌握子群的定义、平凡子群、真子群。
⑵掌握子群的证明方法。
⑶掌握子群的陪集及其性质。
⑷掌握并能够应用拉格朗日(Lagrange)定理及其推论。
7.8环与域
⑴掌握环的定义、环的运算法则(公式)、交换环、含幺环、零因子、含零因子环、无零因子环的判定、整环。
⑵掌握域的定义及其性质。
8格与布尔代数(8学时)
8.1格的概念
⑴掌握格的定义、平凡格、由格诱导的代数系统、子格。
⑵掌握格的对偶原理。
⑶掌握格的性质。
⑷掌握格的同态与同构。
8.2几个特殊格
⑴掌握分配格：定义、两个重要的五元素的非分配格、分配的判定、分配格的性质。
⑵掌握有界格的基本概念：格的全上界、格的全下界、有界格的定义。
⑶掌握有补格的基本概念：元素的补元、有补格定义。
⑷掌握布尔格(有补分配格)的定义。
8.3布尔代数
⑴掌握布尔代数的定义
⑵掌握布尔代数的性质：交换律、结合律、幂等律、吸收律、分配律、同一律、零律、互补律、对合律、底－摩根定律。
⑶掌握布尔代数的同构
⑷掌握有限布尔代数的元素个数定理(Stone定理)，并能够灵活应用。
8.4布尔表达式与布尔函数掌握布尔表达式定义、对布尔表达式赋值、布尔函数定义、布尔表达式相等、布尔表达式的范式.
8.5应用能够应用范式进行基本逻辑设计。
9图论(14学时)
9.1图的基本概念掌握图中的基本概念：图的定义、有向图、无向图、混合图、零图、平凡图、邻接点、邻接边、环(自回路)、平行边、结点的度、图的最小度与最大度、结点的出度与入度、简单图、多重图、无向完全图、有向完全图、有向简单完全图、K-正则图、子图与生成子图、相对补图与绝对补图(补图)、图的同构。
9.2路与回路
⑴掌握基本定义：路、回路、迹、闭迹、通路、圈。
⑵掌握无向图的连通性：两个结点是连通的、结点间的连通关系、连通分支与连通分支数、无向连通图定义、无向连通图的判定、点割集与割点、点连通度、边割集与割边、边连通度。
⑶掌握有向图的连通性：结点间可达性、结点间距离、图的直径、单侧连通、强连通、弱连通、单侧分图、强分图、弱分图。
9.3赋权图掌握赋权图的路长、赋权图两点间的距离，掌握赋权图求两点间最短路长的Dijkstra算法和求关键路径的算法。
9.4图的矩阵表示掌握邻接矩阵、有向图的可达矩阵、完全关联矩阵。
9.5欧拉图与汉米尔顿图
⑴掌握欧拉路与欧拉回路、欧拉图定义、欧拉路与欧拉回路的判定定理、求欧拉回路的算法
⑵掌握汉米尔顿路与汉米尔顿回路、汉米尔顿图的判定定理、求汉米尔顿回路算法。
9.6平面图掌握平面图定义、平面图的面、欧拉公式、平面图的判定定理。
9.7着色与偶图掌握平面图的正常着色、偶图的定义、偶图的判定定理、偶图的应用。
9.8树与生成树
⑴掌握树的定义、叶结点、分支结点、森林、与树定义等价的几个命题。
⑵掌握生成树定义、赋权图的最小生成树及其算法。
9.9根树及其应用
⑴掌握基本概念：有向树、根树、树根、叶结点、内结点(分支结点)、父结点、儿子结点、祖先结点、后裔结点、叶结点的层次、根树的高度。
⑵掌握常用的根树例子：语法树、判定树、搜索树、竞赛树、家谱树等等
⑶掌握有序树的概念。
⑷掌握Ｍ叉树、完全Ｍ叉树。
⑸掌握最优树、最优树的画法。
⑹掌握前缀码设计
三、教学要求表述说明
根据教学要求的程度不同，在表述上采用了“掌握”、“理解”、“了解”、“能够”等文字，其涵义分别描述如下：
关于理论知识：对要求“掌握”和“理解”的内容，要做到概念清楚，原理明白，方法熟练，并应当对有关知识形成较长时间的记忆。相比较而言，“理解”在要求程度上要弱一些。对要求“了解”的内容，应当知道有关的名词、概念和相关知识，并能正确地进行表述。
关于方法与应用技术：对要求“掌握”和“能够”的内容，要做到全面认识应用对象，能运用基本理论分析和解决实际问题，掌握相关的计算和电路设计方法，相比较而言，“能够”在要求程度上要弱一些。对要求“了解”的内容，应当概念清楚，知道相应方法的理论依据和有关的结论。
四、教学安排及方式
总学时40学时，讲课34学时，习题课6学时。
⑴本课程平均周学时为3。
⑵采取平时和期末考试综合评定成绩，其中，平时成绩不低于总成绩的10%。
⑶针对本课程学时少，内容多，理论性强的特点，应采取精讲多练和启发式教学。
⑷本课程涉及概念多且比较抽象，所以要有一定课时的习题课并配有相当数量的课外习题作业。
⑸本课程是计算机专业的数学基础课，要达到合格的工科学生必须具备的有关要求，还有待于在后续课程、生产实习、毕业设计等教学环节中继续培养和提高。
文章知识点与官方知识档案匹配，可进一步学习相关知识Java技能树首页概览92418 人正在系统学习中 相关资源：1stopt数据拟合软件_曲线拟合软件-深度学习文档类资源-CSDN文库
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！