《离散数学》说课稿.doc

离散数学说课稿数学教研室 雷志金2010年6月一、教材分析1. 课程性质现代数学可分为两大类，一类是研究连续现象的，如分析、方程等；另一类就是研究离散现象的离散数学.离散数学是现代数学的一个新分支，并随着信息技术的进步得到了蓬勃的发展。在信息的处理技术、计算机软硬件的设计等领域都有着广泛应用。离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。由于离散数学在计算机科学中的重要作用，国内外几乎所有大学的计算机类专业的教学计划中都将其列为核心课程进行重点建设，它是其他骨干课程，如数据结构、操作系统、人工智能、计算机网络、软件工程、编译原理等的先修课程，国内许多大学将其作为计算机专业类研究生入学考试的内容。随着现代信息技术的发展，计算机学科的发展也非常迅速，离散数学作为计算机科学与技术专业的专业基础课程也随之不断发展变化。该课程是于1977年被IEEE确定为计算机专业核心主干课程，2001年又被IEEE和ACM确定为计算机专业第一核心主干课程。随着CC2001和CCC2002、CCC2004教程的问世，教学课程体系逐步走向成熟，离散数学的教学内容被进一步更新，其内容框架也越来越趋于成熟，基本上核心内容主要包含四大分支：数理逻辑、集合论、近世代数、图论。2. 教材建设(1)教材：大连理工大学出版社2008年出版的“高职高专计算机基础教育系列规划教材” 离散数学（主编：王宗传 ）。 (2)教材优点：基本能体现以应用为目的，以“必需，够用”为度的要求，减少理论推导，注重学生基本运算能力和分析能力的培养，基本符合我院学生实际。 (3)教材不足：在理实结合，工学结合方面略显不够，理论推导还可进一步淡化，关联专业方面的实例较少。3. 课程重点、难点分析一、数理逻辑 数理逻辑是用数学的方法研究关于推理、证明等问题的学科，也叫做符号逻辑。它的本质是研究如何通过利用纯粹的公理系统和符号演算以及推理方法来代替人们思维中的逻辑推理过程，并由此将整个的数学建立在这样一个逻辑基础之上。由于历史上诸多数学家的努力和推动，尤其是莱布尼茨、布尔、希尔伯特、罗素、图灵、哥德尔等人的工作，部分地实现了数学家们的这一形式化数学的梦想，但同时，也由于哥德尔的工作，揭示了数学基础本身存在的巨大困难。如何解决这些问题和困难，仍然是今天的数理逻辑学家面临的重大挑战。 数理逻辑基础包括两个最基本的也是最重要的组成部分，就是“命题演算”和“谓词演算”。 命题演算是研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。如果我们把命题看作运算的对象，如同代数中的数字、字母或代数式，而把逻辑连接词看作运算符号，就象代数中的“加、减、乘、除”那样，那么由简单命题组成复和命题的过程，就可以当作逻辑运算的过程，也就是命题的演算。命题演算的一个具体模型就是逻辑代数。谓词演算也叫做命题涵项演算。在谓词演算里，把命题的内部结构分析成具有主词和谓词的逻辑形式，由命题涵项、逻辑连接词和量词构成命题，然后研究这样的命题之间的逻辑推理关系。 数理逻辑近年来发展特别迅速，主要原因是这门学科对于数学其它分支如集合论、数论、代数、拓扑学等的发展有重大的影响，特别是对计算机科学的发展起了推动作用。反过来，其他学科的发展也推动了数理逻辑的发展。 在本课程“数理逻辑”部分的教学过程中，在强调重点的基础上，将具体讨论命题，逻辑联结词，命题公式、真值函数；重言式，矛盾式，命题公式、真值函数；命题公式的推理理论；对偶与范式；谓词，与命题的关系；谓词合式公式，客体变元的约束；谓词合式公式的等价与蕴涵；谓词演算的推理理论；前束范式与斯柯伦范式；形式化进一步讲论；可靠性和完备性等方面的问题。 二、集合论 集合论是德国著名数学家康托尔于19世纪末创立的。康托对于无穷集元素个数问题进行了卓越的研究，引领数学研究进入了一个全新的领域。他提出用一一对应准则来比较无穷集元素的个数，将元素间能建立一一对应的集合称为个数相同（也称作等势）。并证明了无穷集的势之间存在着差别，有着不同的数量级，可分为不同的层次。随之建立了关于无限的所谓阿列夫谱系。康托尔的成果影响深远，被称为“对无限最深刻的洞察、数学天才的最优秀作品、人类纯智力活动的最高成就之一”。 随着时间的推移，康托的朴素集合论受到“罗素悖论”的挑战，为了解决可能存在悖论的问题，集合论进一步发展，形成了公理集合论，它是对朴素集合论的严格处理和进一步发展。这个过程看来永远不会终结。 在本课程“集合论”部分的教学过程中，主要会涉及到集合、关系等的基本概念、运算、性质和分类。 具体包括：集合基本概念和并、交、 补、差运算；对称差运算和幂集，笛卡尔积；关系及其表示法、关系的运算和性质，闭包运算；等价关系与集合的分类，分类的加细，集合的覆盖与分划，等价类与商集等等；序关系与哈斯图 ；偏序关系与全序关系、置换、单射、满射和双射等等；可数集与不可数集，基数与连续统猜想等等。三、近世代数 近世代数中最基础的部分是群论，这一重要的现代数学思想有多个起源：1）来源于数论（主要源于欧拉和高斯等人关于同余类以及二次型的分类等有重要意义的工作）2）来源于几何学（主要来源于多种几何学的分类、特征描述，特别是克莱因著名的爱尔朗根纲领）3）来源于方程论（求高于四次的方程的根式解是诱导群论的一个直接和重要的原因，在这方面，拉格朗日作了先驱性的总结工作，提出了他的猜想，而两位英年早逝的天才数学家阿贝尔和伽罗华则先后给出了这个问题的部分以及完整的解答，并由此产生了群论以及近世代数这一现代数学分支） 本课程中近世代数这一部分主要涉及到的内容包括群、环、域、格、布尔代数等。 在群的初步理论中，首先将介绍群、子群、 群同构的概念及有关性质，接着讨论几类最常见的群。然后对群论中某些重要的概念作专题讨论。首先定义并讨论群的子集的运算，随后引出并讨论子群陪集的概念与性质以及著名的拉格朗日定理及其应用；接下来定义并讨论正规子群与商群的概念与性质，并由此证明群同态基本定理，从而对群的同态象做出了系统的描述。这部分内容是群论中最基本的内容。最后介绍群的理论在研究阶较小的有限群时的某些应用。 在本课程“近世代数”的后半部分，进行的是环、域等方面的一个初步的介绍和讨论。具体包括环和域、同态与同构等基本概念。 近世代数这部分理论内容相当丰富，有巨大的课外学习空间，我们将在数学选修课以及不定期举行的讲座中向学生介绍其中的部分内容以及它们的应用。 四、图论 “图论”是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部份，它起源于著名的柯尼斯堡七桥问题。欧拉在1736年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问题（得到一个“图”）。欧拉证明了柯尼斯堡七桥问题是无解的，并推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这使得欧拉成为图论及拓扑学的创始人。 类似的，图论的历史上还有许多著名、有趣、寓意深刻的问题，如哈密顿问题、四色猜想等等。运筹学、计算机科学和编码理论中的很多问题都可以转化成为图论问题，而后者对图的着色理论、图的计数理论、平面图理论、代数拓扑图论等诸多分支的发展也起到了巨大的推动作用。图论的广泛应用，促进了它自身的发展。20世纪40-60年代，拟阵理论、超图理论、极图理论，以及代数图论、拓扑图论等都有很大的发展。 在本课程的“图论”部分，除了讲授欧拉图、哈密顿图及其应用外，还涉及到图的基本概念与矩阵表示；连通性；树的生成树，构造与计数；根树及其应用；平面图与对偶图等方面的内容。离散数学自身研究方面的进展随着计算机的发展而深入，特别在研究智能推理的非经典逻辑方面，在代数结构的深入探讨方面，在图论与群论相互结合的理论方面都有大量的新成果出现。随着计算机科学的发展，离散数学在上述各方面的研究将更加深入，且更具吸引力。新的，具有创造性的研究成果将会层出不穷，其研究无论是理论方向还是应用方向，其前景都是无限宽广且光明的。本课程是计算机科学和数学等各专业的专业基础课，为高级语言程序设计、数据结构和计算机组成原理等课程教学的顺利完成奠定了坚实基础。二、教学目标 1. 知识目标任教学生是软件专业的。本专业培养具有大学专科文化程度，以计算机软件开发技术为根本，让学生具备扎实的基础理论知识 2. 能力目标培养学生的抽象思维和严格推理的能力，使学生掌握信息技术领域中的一些基本数学工具和方法。通过定期的企业项目实训，让学员掌握企业项目的实际开发模式和方法，从而具备较为丰富的项目经验和较强动手能力 3. 情感目标养成规范的软件开发习惯和团队协作精神的高素质技能型人才，以适应社会信息化需求。三、教学内容本课程共分 章/或单元/或模块，安排 学时，其中理论学时 ，实践学时。 每章/或单元/或模块教学的内容以及要达到的教学效果（知识内容和要求、技能内容和要求）。大纲要求，主要知点，课时分配专业培养目标要：学生应具有的基础知识、基本理论和基本运算技能。各教学章节学时分配如下表所示：章节内容学 时第一章 命题逻辑8第二章 谓词逻辑6第三章 集合2第四章 二元关系和函数12合 计（含复习2节）30四、教学设计 第一章 命题逻辑 本章是数理逻辑中的最基本内容，是下一章的基础.本章主要讲述命题与联结词、命题公式、恒真命题、等价式、蕴涵式及范式等基本内容；能将自然语言符号化；能用等价式、蕴涵式等进行命题演算和推理；能用逻辑推理的方法解决一些实际问题. 第一节 命题与逻辑联结词 l 本节的主要内容有:1.给出了命题的概念,即命题是能判断真假的陈述句；2.命题的判断结果称为命题的真值；3. 一个命题若不能再分割成更小的命题,则该命题称为原子命题,否则称为复合命题.第二节 命题公式与解释 本节主要内容有:1.用递归的方法定义了命题公式；2.给出了命题的解释或赋值的概念；3.定义了公式的真值表；4.给出了恒真、恒假及可满足公式的定义.第三节 公式的等值演算1.给出了两个命题公式等值的概念；2.24个基本的等值式;3.给出了命题逻辑的两个简单的实际应用.第四节 联结词全功能集与对偶原理1. 介绍了3个逻辑联结词,即异或、与非、或非；2. 真值函数；3. 逻辑联结词的全功能集与极小全功能集、常用的、也是最基本的有3个,即非、析取、合取等；4. 对偶式、对偶原理.第五节 命题公式的范式 l 范式指的是命题公式规范的表示形式,有两种范式,即析取范式与合取范式, 概念和结论有:1.简单析取式、简单合取式、析取范式、合取范式、主析取范式、主合取范式、极大项、极小项的定义;2.任一公式必有与之等价的合取范式和析取范式;3.任意公式都存在惟一的与之等价的主析取范式;4.析取范式、合取范式、主析取范式、主合取范式的求法及范式的简单应用第六节 命题逻辑中的推理 本节给出了形式演绎的三个规则及举例说明这三个规则的灵活应用;l 规则P：在演绎过程中可以随便使用前题集合中任一公式;l 规则T：在演绎过程中可以随便使用前面演绎出来的某些公式的逻辑结果;l 规则CP：如果需要演绎出的公式具有PQ的形式，则可以将P做为附加前题使用，设法演绎出Q来.l 证明的三种方法，即真值表法，直接证法和间接证法. 本章小结 本章首先引入命题及逻辑联结词，并在此基础上定义了公式以及公式的等价、蕴涵、范式等，然后用等价式、蕴涵式等进行命题演算和推理.本章将初步体现数理逻辑的基本观点和方法，为将来从事计算机工作打下良好的基础. 第二章 谓词逻辑本章可视为前一章的深入和提高；由于命题逻辑的局限性我们必须引入谓词逻辑.学习本章时要求掌握好谓词与命题的关系、量词、辖域、公式等概念.比较谓词公式的等价、蕴涵与命题公式相应的概念的异同；能将自然语言符号化；能用谓词逻辑进行推理；理解前束范式的意义. 第一节 谓词与量词 l 本节的主要内容有:1.给出了谓词与量词两个概念,其中量词又分为全称量词与存在量词；2.给出许多自然语言符号化的例子；3.初步体会到应用谓词与量词后,逻辑表达能力大为加强.第二节 公式与解释 本节主要内容有:1.给出了4种符号,即常量符号、变量符号、函数符号、谓词符号的定义;2.在4种符号的基础上,定义了项,在项和谓词的基础上定义原子,在原子的基础上用递归的方法定义了公式；3.公式的指导变元、辖域、约束变元、自由变元及变元的改名规则;4.命题的解释或赋值的概念；4.恒真、恒假公式的定义;第三节 等价与蕴涵 与命题逻辑一样，一阶逻辑也有等价与蕴涵的问题,考虑了下列问题: 1.量词与否定联结词之间的关系 ;2.量词辖域的扩张与收缩规律； 3.量词与联结词之间的13个基本等价式；4.5个基本蕴涵式； 5.改变公式的两个量词排列次序的变化规律； 6.对偶式的概念与对偶原理第四节 前束范式 l 范式是解决公式的标准表示形式问题.在一阶逻辑性中同样有范式的概念并且范式也不只一种.但我们仅介绍一种范式前束范式1.前束范式的定义；2.前束范式的存在性,即一阶逻辑中的任意公式，都存在一个与之等价的前束范式；3.前束范式的求法,见书中给出的例子.第五节 谓词演算的演绎与推理 与命题逻辑中的推理一样,谓词逻辑中的推理也是利用公式间的各种等价关系，蕴涵关系.通过一些推理规则，从已知的公式推出某些新的公式.且命题逻辑的推理规则在谓词逻辑中仍可使用,但由于谓词逻辑中引进了个体词，谓词和量词，因此我们还必须添加一些与量词有关的推理规则,1.添加的推理规则是:全称特定规则、存在特定规则、全称推广规则、存在推广规则;2.此外本节给出许多例子说明推理方法. 本章小结本章讨论问题的方式与前一章基本上是平行的，首先认识到前一章的命题的局限性进而引入了谓词，并在此基础上定义了公式以及公式的解释、等价、蕴涵、前束范式等，然后用等价式、蕴涵式等进行推理，与命题逻辑相比，谓词逻辑的内容较为丰富也较为复杂.第三章 集合 l 集合是现代数学各分支的共同基础，当然也是本书的基础，读者应熟练地掌握本章的全部内容，本章的一些内容，如集合的并、交、Venn图等已在中学及大学的其他课程中学习过，但为了内容的完整及这些内容基础地位，我们没有省略这些内容. l 本章主要讲述集合的基础理论、基本方法和应用.第一节 集合及其表示法 l 本节用描述性的定义给出了集合的定义及其表示方法主要概念有: 1.集合、元素、属于、有限集 2.集合表示的两种方法:即列举法和描述法第二节 子集与幂集 l 本节研究集合的子系统，即子集合,本节的主要内容有: 1.集合的子集合、集合的包含关系、真包含、集合的相等、集合的幂集等. 2.用二进制数的方法来表示幂集中的元素,这实际上就是集合在计算机中的表示方法第三节 集合的基本运算 l 本节讨论集合的基本运算,主要内容有: 1.集合的并、交、差运算; 2.全集与补集、集合的几何图形表示法Venn图; 3.有限集合的容斥定理.第四节 集合的运算性质 l 本节我们主要把集合的并，交，差，补运算的性质进行整理，通过这些性质可以更深刻地掌握集合代数的规律，同时这些规律也是我们后面要介绍的布尔代数的模型.另外本节给出较多的例子.l 本节给出了集合的对称差及集合的特征函数的定义,通过特征函数可以简化许多证明过程.书上已给出一个这方面的例子.本章小结l 本章我们讨论了集合的基本概念及其集合的基本运算，主要有子集、空集、幂集、集合的并、交、补、差、对称差、Venn图、有限集合的容斥定理及有限集的子集的表示方法等，特别我们还给出了特征函数的定义，利用特征函数可简化集合的运算性质的证明.第三节 集合的基数简介第三章 集合的基数l 本章讨论集合论中较为困难的问题集合的基数问题；但只限于对基数作一简单介绍；如学时较少可不讲本章或对本章作恰当的删减.l 本章主要概念为:集合的等势、有限集与无限集、可数集与不可数集及较为常见的集合的基数.l 前二节我们初步认识了集合的三种基数；即有限集合的基数、自然数集的基数及实数集的基数,本节定义了基数之间的大小关系,结论有:1.设A,B是两个集合，则|A|=|B|,|A|B|及|A|B|三条中有且仅有一条成立；2.Bernstein定理:设A,B是两个集合,若|A|B|且|A| |B|,则集合A,B等势;3.设A是任意集合,P(A)为A的幂集,则P(A)的基数大于A的基数.第二章 二元关系 本章讨论的关系是我们通常的诸如大小关系、整除关系、上下级等关系的共同的数学模型，掌握关系运算极其关系运算的性质、实际意义.深入理解关系、关系图、关系矩阵之间的联系，熟练地掌握两类特殊的关系等价关系与偏序关系；熟练地用Warshall算法求关系的传递闭包；理解映射的意义，本章为第三、六、七章的基础.第一节 序偶与笛卡尔积 l 本节是通过n元有序组的概念来定义序偶与笛卡尔积的概念，主要讨论两个集合的笛卡尔积，它是讨论二元关系的基础.得出笛卡尔积的一些最基本的结论.第二节 关系的概念 本节在笛卡尔积的基础上给出二元关系定义,并推广成n元关系,不过我们以讨论二元关系为主.主要内容为:1.一些特殊的关系,如空关系、恒等关系、全关系;2.关系的运算,如关系的并、交、补、差、对称差极其运算规律;3.有限集合上的二元关系的两种表示方法(即关系矩阵与关系图),4.为了用关系矩阵来研究关系,我们定义了布尔矩阵的概念及布尔矩阵的三种运算(即布尔非、布尔与、布尔或).第三节 复合关系与逆关系 l 本节讨论关系的复合运算与逆运算极其性质;主要考虑了下列问题:l 1.关系的复合是否满足交换律、结合律、关系的复合对于集合的并(交)是否有分配律;l 2.关系的复合运算与逆运算在关系图和关系矩阵上的反应;l 3.关系的复合运算与关系的逆运算之间的运算规律.第四节 关系的性质 l 本节我们讨论关系的一些常见性质，主要内容是: 1.给出了关系的自反性、对称性、反对称性、传递性的定义; 2.给出了关系的自反性、对称性、反对称性、传递性等在关系矩阵及关系图上的反应，其中用关系矩阵及关系图来判断传递性较为困难; 3.讨论了关系的各种运算对上述特性的影响.第五节 关系的闭包(1)我们希望某个关系具有比较好的性质，比如我们希望它具有自反性，对称性，传递性.但如果该关系又不具有上述性质，那么我们就要对该关系进行适当的改造，即在该关系中适当添加一些元素得到一个新的关系，使这个新关系具有我们需要的性质，同时新关系与原来的关系不要相差得太多，这样就要求我们添加的元素既要使新关系满足要求又要尽可能地少添加元素.通过适当添加元素来扩充原关系,使得到的具有我们需要的性质的新关系称为原关系的闭包，我们通常考虑关系的三种闭包，即自反闭包，对称闭包，传递闭包.第五节 关系的闭包(2)l 本节的内容较丰富,主要有: 1.给出了关系的自反闭包、对称闭包、传递闭包的定义; 2.从理论上证明了自反闭包、对称闭包、传递闭包的存在性，其中传递闭包较为复杂，是本节重点; 3.给出了上述三种闭包的具体计算公式; 4.Warshall算法是求有限集合上的二元关系的传递闭包的有效算法; 5.考虑了关系的闭包与关系的其它运算的联系.第六节 等价关系l 等价关系是一类最为重要的关系，因为等价关系与集合的分类密切相关,内容有 1.以同余关系为例给出等价关系的定义; 2.给出了商集的概念 3.主要结论是:等价关系与集合的分类相互惟一确定;第七节 偏序关系 l 数的大小，集合中元素的排列次序，计算机程序的执行顺序等都牵涉到次序关系，这些在数学上都表现为序关系的研究,本节主要内容有:1.具有自反性、反对称性、传递性的关系称为偏序关系;2.偏序关系的简化关系图哈斯图,哈斯图与原图的关系是一种压缩与解压缩的关系;3.由两个偏序关系构造新的偏序关系方法(如书中定理2.7.1);4.偏序集中的一些特殊元素,如最大、最小元,极大、极小元,上界、下界等;5.一些特殊的偏序关系,如全序关系,良序关系等.第八节 映射 l 映射是高等数学中所研究的单值函数的推广，因此映射也称为函数，这里我们把映射视为一种特殊的二元关系,内容有: 1.映射的定义、象与原象、定义域与值域、映射的相等、映射的限制与扩充; 2.一些特殊的映射,如满射、单射、双射.第九节 复合映射与逆映射 l 映射的复合就是关系的复合,须注意的是复合的次序,主要内容有:1.映射的复合具有结合律,但不符合交换律;2.区分了左逆与右逆；给出里左逆、右逆与单射、满射之间的关系；3.可逆与左、右逆之间的关系.本章小结1.本章我们给出笛卡尔积的定义，并在此基础上抽象出关系的概念、给出了关系的表示方法及关系的运算；特别是关系的复合、关系的闭包、关系的性质极其在关系图上，矩阵上的反映.在讨论关系的闭包时，传递闭包较为复杂、Warshall算法是求有限集合上的二元关系的传递闭包的有效算法. 2.本章还介绍了两类特殊的关系等价关系与偏序关系，这两类关系在第六、七章中将会被用上.映射是作为特殊的关系引进的，它是高等数学所讨论的单值函数的推广，也是第六、七章所不可缺少的.第六章 代数结构代数结构的主要研究对象是各种各样的代数系统，即具有一些元运算的集合,本章介绍的群就是具有一个二元运算的代数系统. 本章以群为例讨论代数结构，它的思想和方法已经渗透到现代科学的许多分支、它的结果已应用到计算机的不少方面，因此计算机科学工作者应初步掌握其基本的理论和方法.读者通过对群的学习应初步掌握对代数系统研究的一般方法，从简单到复杂、从具体到一般，从而发现代数系统的一般规律.本章的内容较为抽象、难学.可根据具体情况删减一些内容.第一节 代数结构概述 l 我们在前面已经研究过集合，那时没有过多地考虑一个集合内部元素之间的联系.现在我们要在一个集合的内部引入运算，并研究其运算规律,主要内容为:l 1.代数系统的定义,然后用例子说明代数系统的丰富性;l 2.代数系统的运算的常用记法和运算表的概念.第二节 置换(1) l 群论的研究始于置换群.置换群在群论里有重要的地位.例如，五次以上方程不能用根号求解的问题的证明就用到置换群.置换概念本身在计算机科学中也起作重要作用.同时置换群的记法简单，运算方便.l 本节的概念有:置换、循环置换、不相交置换、对换、奇置换、偶置换等;第二节 置换(2) l 本节的结论有:1.置换的乘法(即合成)满足结合律;2.两个不相交的循环置换的乘法满足交换律;3.任意置换均可惟一地分解成不相交循环置换的乘积(不考虑因子的次序) ；4.每个置换都能分解成对换的乘积，且偶置换只能分解成偶数个对换的乘积，奇置换只能分解成奇数个对换的乘积；5.在n个元素的所有置换中,奇偶置换各半.第三节 群 l 本节给出了群 的定义及群 的简单性质.l 主要概念有:左(右)单位元、单位元、左(右)逆元、逆元、可除条件、消去律、有限群、无限群、交换群;l 主要结论有:1.群的定义中条件(2) 、(3)可分别用左单位元、左逆元替代,也可分别用右单位元、右逆元替代,还可以用可除条件替代;2.任意群中消去律成立.第四节 子群 l 与集合的子集、向量空间的子空间一样.群也有子群的概念.子群作为群的一部分.它的结构对群的结构有重要影响.l 主要概念有:平凡子群、非平凡子群、由某个元素生成的子群、循环群、生成元、元素的周期.l 讨论了一个群的非空子集构成子群的条件;在某个元素生成的子群的基础上定义循环群,把循环群的结构研究清楚了.第五节 陪集与正规子群 l 本节利用群G的一个子群H来作G的一个分类，并由这样的分类来引入正规子群的概念. 1.利用群G的一个子群H,定义了G的一个等价关系,这个等价关系决定了G的一个分类,每个类Ha称为右陪集,类似地也定义了左陪集; 2.在左、右陪集的基础上定义了群的正规子群,并讨论了子群为正规子群的条件,正规子群是群的一类重要子群,有很好的代数性质,应很好掌握它.第六节 拉格朗日定理 l 拉格朗日定理反映了有限群的元数与其子群的元数之间的关系.是群论的最基本定理之一. l 拉格朗日定理是:设G是有限群,H是G的子群,则有公式|G|=|H|(G:H).l 本节给出了拉格朗日定理的两个推论及几个应用拉格朗日定理的例子.第七节 群的同态(1) l 同态是两个代数系统间的一种联系，通过这种联系，可以把一个代数系统的运算转移到另一个代数系统.使得在一个代数系统中较难解决的问题转移到另一个代数系统中成为较易解决的问题.例如，我们常用的对数，实际上，它就是正实数的乘法群到实数的加法群的一个同态.利用对数，我们实现了把较难的乘法运算转化成较易的加法运算，因此，同态是代数系统间十分重要的关系 第七节 群的同态(2)l 主要概念有:同态、单同态、满同态、同构、零同态、同态象、同态核.l 主要结论有:1.设f是群G到群G的同态映射，则G的单位元的象是G的单位元；且G的子群H在f下的象f(H)是G的子群;2.设f是群G到群G的同态映射,则同态核是G的正规子群;第八节 商群 l 正规子群之所以重要，是因为这种子群的陪集,对于与原来的群有密切关系的某种代数运算来说作成群；l 主要结论有:设N是群G的正规子群,N的所有陪集按照以下的乘法 (aN)(bN)=abN 构成一个群(称为G对N的商群,记作G/N),且商群G/N是群G的同态象.第九节 同态定理 l 设f:GG是群同态,于是可以构造商群G/Kerf,同态定理是:同态基本定理设:f:GG是群同态,则: G/KerfG第十节 环(1)l 前面讨论的都是只有一个代数运算的代数系统,本节我们介绍有两个代数运算的代数系统环 .环的两个被称为加法、乘法的代数运算是我们最为熟悉的代数运算,由于本课程的限制,我们对环仅作极其初步,简单的介绍.l 学习本节时,可以把整数、有理数、实数、复数的加法、乘法运算与环的两个运算加以对照.第十节 环(2)l 本节的基本概念有: 环、环的运算表、交换环、有单位元的环、零因子、左零因子、右零因子、无零因子环、整环、除环、域、四元数等;本节介绍了与环有关的最基本的结论本章小结l 本章在简单地介绍了代数系统的概念后，较为详细地讨论置换（它实际上是为讨论群作准备）.然后我们就给出群的定义，接着我们又讨论子群、陪集、正规子群、商群、同态、同构等.最后一节我们还极其简单地介绍了具有两个代数运算的系统环.这些内容对于抽象思维能力和逻辑推理能力的培养很有帮助.第九章 树与平面图 树是一类结构较为简单的图，是用途极为广泛的离散数学模型，特别是二叉树，它在计算机科学中用得最多.因此在学习时应很好地掌握好诸如树的充要条件、生成树、最优生成树、根树、树的各种算法、及二叉树的访问次序等内容.平面图是实际背景很强的一类图，能用本章介绍的方法判断一个图是否为平面图. 第一节 树的概念 l 本节介绍树的一些最基本的概念与结论.1.概念有:树,树叶,分支点(或内点),森林,平凡树等2.结论: 设G是n阶无向图，则下列条件等价：（1）G是树；(2）G连通并且删去G的任一边，所得之图都不连通；(3）对G中的任意两点u,v(uv)，恰有一条从u到v的简单路；(4）G不含回路，且G有n-1条边；(5）G连通，且G有n-1条边. 第二节 生成树与最优支撑树 l 本节讨论连通图的生成树与连通权图的最优生成树(或称为最优支撑树).1.基本概念:生成树,余树,树枝,最优(小)生成树等;2.定理:图G有生成树当且仅当G是连通的；3.算法:(1)无向连通图可采用破坏回路与不形成回路两种方法寻找生成树； (2)权图中求最优生成树的两种算法,即克鲁斯卡尔算法与管梅谷的破圈法.第三节 有向树与根树(1) l 有向树是有向图中结构最为简单的一类图. 它是一种典型的非线性结构，在计算机算法分析、数据结构等方面有广泛的应用；在有向树中，根树最为重要，我们主要考虑根树.1.概念:有向树,根树,树叶,内点,分支点,层数,树高,祖先,后代,父亲,儿子,兄弟,有序树,m叉树,完全m叉树,根子树,左子树,右子树,带权二叉树,最优二叉树,前缀,前缀码,二元前缀码,二叉树遍历等;第三节 有向树与根树(2)2.定理: 设T是一棵根树，r是T的树根,则对于T的任一顶点v,存在唯一的有向路从r到v；3.算法:最优二叉树的Huffman算法;4.前缀码问题:前缀码与二叉树的对应关系；5.二叉树的遍历:三种遍历方法,即先根遍历,中根遍历,后根遍历法.第四节 平面图 l 平面图是很多实际问题的模型. 例如在集成电路的布线设计中就遇到了平面图的问题. 1.基本概念:平面图,平面嵌入,面,无限面(外部面),内部面,边界,次数等;2.基本非平面图:K3,3与K5；3.平面图的欧拉公式；4.平面图的判定:库拉图斯基定理. 本章小结 l 本章我们介绍树与平面图，但以介绍树为主.给出树的定义及树的充要条件，生成树、最优生成树及最优生成树的克鲁斯卡尔算法，特别是二叉树，我们讨论了二叉树的Huffman算法、前缀码、二叉树的遍历等问题.最后介绍了一类实际背景很强的一类图平面图.第八章 图的基本概念 图是一类相当广泛的实际问题的数学模型，有着极其丰富的内容，是数据结构等课程的先修内容.学习时应掌握好图论的基本概念、基本方法、基本算法；善于把实际问题抽象为图论的问题，然后用图论的方法解决问题.第一节 图的概念 l 本节介绍图的一些最常用的概念,主要有:无向图,有向图,边,顶点(或结点,点),弧(或有向边),顶点集,边集,n阶图,有限图,关联,多重图,简单图,完全图,二分图(或偶图),完全二分图,母图,子图,支撑子图(或生成子图),导出子图,补图,图的同构,入度,出度,度,孤立点等.主要定理:握手定理.第二节 路与回路(1) l 本节介绍图中有关路的基本概念，同时作为路在权图中的应用，我们给出求权图最短路的迪克斯特拉算法. 1.基本概念有:路,路的起点,路的终点,路的长度,开路,闭路,简单路,回路,基本路,圈,连通,连通分支,连通图,两点间的距离,可达,强连通图,单向连通图,弱连通图,权图,权,迪克斯特拉算法等；第二节 路与回路(2)2.主要结论: 设G=(V,E)是图，且|V|=n,若存在结点u到v的路，则必存在u到v的长度不超过n-1的路. 3.算法:迪克斯特拉(Dijkstra)算法,迪克斯特拉算法是图论中最基本的算法,应很好地掌握. 第三节 矩阵与图 l 本节主要考虑三种矩阵，即邻接矩阵，可达矩阵与关联矩阵.邻接矩阵反映的是顶点与顶点之间的关系；可达矩阵反映了图的联通情况；关联矩阵反映的是顶点与边（弧）的关系. 分有向图与无向图来讨论.第四节 关系与图 l 在讨论集合的二元关系时，我们就给出了关系的图形表示，即关系图.这里用图论的方法给出关系图的严格定义. l 关系中的很多性质可以在关系图上反映出来 ,可以通过图来研究关系,也可以通过关系来研究图.第五节 欧拉图(1) l 欧拉图是一类非常著名的图，之所以如此，不仅是因为欧拉是图论的创始人，更主要是欧拉图具有对边（弧）的“遍历性”. 1.概念有:欧拉路,欧拉图,半欧拉路,半欧拉图,割边等；第五节 欧拉图(2)2.结论有:(1)无向连通图G是欧拉图的充要条件是G中每个顶点的度均为偶数； (2)设G是无向连通图，则G是半欧拉图的充要条件是G恰含有两个奇数度点. 3.算法:在欧拉图中找欧拉路的Fleury算法.第六节 哈密尔顿图(1) l 哈密尔顿图是一类实际背景很强的图论模型,与欧拉图不同，哈密尔顿图感兴趣的是遍历图中的诸顶点.1.主要概念:哈密尔顿路,半哈密尔顿图,哈密尔顿回路,哈密尔顿图,图的闭包；2.主要结论:哈密顿图的判定，至今也还没有令人满意地结果.下面的一些哈密顿图的结果都只是充分条件或必要条件，而非充要条件. 第六节 哈密尔顿图(2)(1)设G=(V,E)是哈密尔顿图，则对V的任意非空子集S均有W(G-S) |S|,其中G-S表示在G中删除S中的点以及以S为端点的边后所构成的图；W(G-S)表示G-S的连通分支数;(2)设G=(V,E)是n阶无向简单图，若对G中任意不相邻的顶点u,v都有d(u)+d(v) n-1,则G存在哈密尔顿路，因此G是半哈密尔顿图；(3)设G是n阶简单图，则是哈密尔顿图当且仅当其闭包是哈密尔顿图. 第七节 二分图(1)l 二分图也是一类实际背景很强的图论模型,在1已给出了二分图的定义,二分图与图的匹配有密切关系.1.基本概念:二分图,匹配,最大匹配,饱和,非饱和,完美匹配,交错路,可扩路,邻集等;2.结论:(1)设G是无向简单图,则G是二分图的充要条件是它的所有回路的长度为偶数;第七节 二分图(2)(2)图G的匹配M是最大匹配当且仅当G不含M的可扩路;(3)设G=(V,E)为二分图,顶点划