离散数学学习计划

1 / 30离散数学学习计划湖 北 大 学 学 期 授 课 计 划(2016 2016 学年度第 一 学期)注：1、课程类别指公共基础课、专业基础课、专业课、专业选修课、公共选修课。2、教学时数应填写教学所需的学时数，周学时要与学校课表保持一致。3、教学形式指讲授、实验、习题课、讨论、自学指导、演示、录像示教、辅导答疑、上机实习、实地考察、参观等。4、课外作业指作业类型，如习题、课程论文、调查报告、实验报告、读书报告、查阅文献资料等。 课外辅导应扼要说明辅导形式和内容。5、考核形式：考试、考查。注：1、课程类别指公共基础课、专业基础课、专业课、专业选修课、公共选修课。2 / 302、教学时数应填写教学所需的学时数，周学时要与学校课表保持一致。3、教学形式指讲授、实验、习题课、讨论、自学指导、演示、录像示教、辅导答疑、上机实习、实地考察、参观等。4、课外作业指作业类型，如习题、课程论文、调查报告、实验报告、读书报告、查阅文献资料等。 课外辅导应扼要说明辅导形式和内容。5、考核形式：考试、考查。注：1、课程类别指公共基础课、专业基础课、专业课、专业选修课、公共选修课。2、教学时数应填写教学所需的学时数，周学时要与学校课表保持一致。3、教学形式指讲授、实验、习题课、讨论、自学指导、演示、录像示教、辅导答疑、上机实习、实地考察、参观等。4、课外作业指作业类型，如习题、课程论文、调查报告、实验报告、读书报告、查阅文献资料等。 课外辅导应扼要说明辅导形式和内容。5、考核形式：考试、考查。3 / 30漳 州 师 范 学 院学 期 授 课 计 划离散数学 课程计算机科学与工程 系计算机科学与技术(非师) 专业 10 级用计算机科学与工程 系 计算机软件与理论 教研室任课教师 林宣治教 学 要 求 与 安 排教 学 进 度 表离散数学是计算机科学系所有专业的基础数学课程。一方面有其实用性，另一方面有其本身作为数学基础课的理论4 / 30的严谨性。所以，学习任何一个专题时，首先要精确严格地掌握好概念和术语，正确理解它们的内涵和外延。因为公理、定理或定律的基石都是概念。只有正确地理解了概念，才能把握定理的实质，熟练地将公理、定理应用于解决问题。完全地、精确地掌握一个概念首先要深刻理解概念的内涵，然后举一些属于和不属于该概念外延的正反两方面的实例。如果对一些似是而非的例子也能辨别的话，应该说就是对这个概念真正理解了。对一些重要的概念，能记住一两个实例也很管用，这对牢固掌握一个概念是很有好处的。我觉得应养成一种自觉的学习习惯，就是首先要掌握好基本概念和术语，在此基础上，理解每个基本定理的本质，最后通过学习和借鉴书中提供的例题，独立地完成每一次作业，并且在每次作业完成之后，能自觉地归纳出其中用到的基本解题方法。注意，千万不要在完全理解相关概念和基本定理之前就匆忙去做相应的习题。学习数学的唯一途径是实践。仅看别人怎么做，是不可能学会弹吉他或投篮的，也不可能仅靠阅读本书或听课就能学好离散数学。必须积极主动地思考。在阅读数学书时，应该在手头随时备好笔和纸，以便进行详细的推导和计算。5 / 30在听数学课前，最好先阅读有关的内容，这样，就可以专注于对内容的理解是否与教授的理解相一致，还可以就一些难点提问。本书中有很多习题，有些是纯粹的计算题，有些要测试对概念的理解，有些习题则要求给出论证，建议读者多做习题。学习和理解术语也很重要。在数学中，传统的做法是对一些简单、常见的词汇赋予特殊的含义，如集合、函数、关系、图、树以及网络。这些词都有严格的定义，必须认真学习。离散数学期末复习提要离散数学是中央电大“数学与数学应用专业”的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容，使用的教材为中央电大出版的离散数学和离散数学学习指导书 。离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、6 / 30数据库、操作系统、计算机网络等。 课程的主要内容1、 集合论部分； 2、 数理逻辑部分； 3、 图论部分。 学习建议离散数学是理论性较强的学科，学习离散数学的关键是对离散数学有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 教学要求的层次各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。一、各章复习要求与重点第一章 集 合复习知识点1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算7 / 30及其运算律，文氏图 3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 复习要求1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 本章重点习题P56，4、6； P1415，3、6、7； P20，5、7。疑难解析1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为 2。2、集合恒等式的证明8 / 30通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在A?B?A?B 证明中的特殊作用。 例题分析例 1 设 A，B 是两个集合，A=1，2，3，B=1，2，则?(A)?(B)? 。 解 ?(A)?,1,2,3,1,2,1,3,2,3,1,2,3n?(B)?,1,2,1,2于是?(A)?(B)?3,1,3,2,3,1,2,3 例 2 设A?a,b,?a,b?,?，试求：(1)A?a,b?； (2)A?； (3)A?； (4)?a,b?A； (5)?A； (6)?A。 解 (1)A?a,b?a,b?,? (2)A?A (3)A?a,b,?a,b?9 / 30(4)?a,b?A? (5)?A? (6)?A? 例 3 试证明?A?B?A?B?A?B?A?B? 证明?A?B?A?B?A?B?A?A?B?B?A?A?B?A?A?B?A?B?A?B?A?B?A?B?B?B?第二章 二元关系复习知识点1、关系、关系矩阵与关系图 2、复合关系与逆关系3、关系的性质 4、关系的闭包 5、等价关系与等价类10 / 306、偏序关系与哈斯图、极大/小元、最大/小元、上/下界、最小上界、最大下界 7、函数及其性质 8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 复习要求1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。 2、掌握求复合关系与逆关系的方法。3、理解关系的性质，掌握其判别方法。4、掌握求关系的闭包 的方法。5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。 6、理解函数概念：函数、函数相等、复合函数和反函数。 7、理解单射、满射、双射等概念，掌握其判别方法。 本章重点习题11 / 30P25，1；P3233，4，8，10； P43，2，3，5； P5152，5，6； P59，1，2； P64，3； P7475，2，4，6，7； P81，5，7； P86，1，2。 疑难解析 1、关系的概念关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。 2、关系的性质及其判定关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中 P49 上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法” ，即若?a1,a2?R,则?a1,ai?R。如若?a,b?R,、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。12 / 30关键是熟记三个定理的结论：定理 2， r?R?R?IA；定理3， s?R?R?R、半序关系及半序集中特殊元素的确定理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大元，极大元也就容易了。这里要注意，最大元与极大元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。、映射的概念与映射种类的判定映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。 例题分析例 1 设集合 A?a,b,c,d?，判定下列关系，哪些是自反的，对称的，反对称的和传递的：13 / 30?1?a2,a3?R,?,?ai?1,ai?R，?b,a?R，则有?a,a?R，且?b,b?R。；定理 4，推论 t?R?n?Ri?1i。14 / 30R1?R5?a,a?,?b,a?a,c?,?b,d?R2?a,a?,?b,c?,?d,a?R3?c,d?R4?a,a,?,?b,b?,?c,c?解：均不是自反的；R4 是对称的；R1 ,R2 ,R3 , R4 ,R5是反对称的；R1 ,R2 ,R3 , R4 ,R5 是传递的。 例 2 设集合 A?1,2,3,4,5?，A 上的二元关系 R 为R?1,1?,?2,2?,?3,3?,?3,4?,?4,4?,?5,3?,?5,4?,?5,5? 写出 R 的关系矩阵，画出 R 的关系图； 证明 R 是 A 上的半15 / 30序关系，画出其哈斯图；若 B?A，且 B?2,3,4,5?，求 B 的最大元，最小元，极大元，极小元，最小上界和最大下界。解 R 的关系矩阵为?1?0?0?0?00100000101001110?0?0? R 的关系图略 ?0?1?M16 / 30R因为 R 是自反的，反对称的和传递的，所以 R 是 A 上的半序关系。(A,R)为半序集， (A,R)的哈斯图如下4 。13 。2。5(3) 当 B?2,3,4,5?，B 的极大元为 2，4；极小元为2，5；B 无最大元与最小元；B 也无上界与下界，更无最小上界与最大下界。第三章 命题逻辑复习知识点、命题与联结词，复合命题17 / 30、命题公式与解释，真值表，公式分类，公式的等价离散数学课程设计方案中央电大教务处 教学管理科 XX 年 02 月 29 日为了落实教育部批准的关于广播电视大学开展人才培养模式改革和开放教育试点的报告精神，积极投入中央电大计算机科学与技术专业本科开放教育工程的建设和实施，搞好离散数学课程教学与管理工作，保证本课程的教学质量，实现本专业的培养目标，给出以下设计方案。一、课程的性质与任务计算机科学与技术专业是中央广播电视大学于 1999 年开设的开放教育试点专业，开设之初的合作高校为清华大学。在当时的专业教学计划中，把计算机数学基础离散数学确定为统设必修课程，课程的主要内容包括：数理逻辑、集合论、图论、代数系统等。由于 XX 年初，中央广播电视大学工学院将该专业的合作建设高校改为北京交通大学，18 / 30并在新教学计划中把离散数学课程确定为该专业的学位课程，该课程的主要内容包括：集合论、图论、数理逻辑等。离散数学是计算机科学与技术专业的基础核心课程。通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础。 本课程是一门理论性较强的课程，要求在完成基础知识教学任务的同时，通过适当的实际应用的介绍，提高学生的实际应用能力的培养。 二、课程的目的与要求本课程是计算机科学与技术专业及有关学科的一门重要的基础核心课程，内容主要是介绍离散量的结构及其相互关系，其包含的理论与方法在各学科领域都有着广泛的应用。同时，离散数学也是计算机科学与技术专业的许多专业课程，包括程序设计、数据结构、操作系统、编译技术、数据库、人工智能等的先修课程。教学内容以基本概念、结论、算法、推理与证明方法，以及一般应用方法的介绍为19 / 30主，课程内容突出简明扼要、体系结构清楚为原则。通过本课程的学习，学生可以初步掌握处理离散结构所必须的描述工具和方法，同时培养和提高自身的抽象思维和逻辑推理，以及分析和解决实际问题的能力，并为以后学习计算机基础理论与专业课程打下良好的基础。 本课程具体要求为：了解离散数学的主要组成部分，各个部分所涉及的基本内容，及其在计算机科学与技术领域中的应用；理解离散数学的的基本概念、结论、算法、应用方法及适用范围； 掌握离散数学的的基本推理与证明过程、基本算法及应用方法。 三、学时和学分本课程课内学时 72，共 4 学分，开设一学期。下表给出该课程的主要教学内容，视频课程和辅导课程的学时分配。课内学时序号20 / 30教学内容电视课1 2 3 4 5绪论 集合论 图论 数理逻辑 复习 合 计1 5 6 6 2 20流媒体课件2 3 3 2 1013 17 16 2 48 辅导四、教学内容与学习方法 基本学习内容 第一部分 集合论 1集合及其运算集合的概念与表示，集合间的关系和特殊集合，集合运算，容斥原理。 2关系与函数21 / 30笛卡儿积，关系的概念、表示方法及性质，复合关系与逆关系的概念与计算，关系的闭包的概念及计算，等价关系的概念与判定，等价类的概念与求解，序关系的概念与判定，复盖集与哈斯图的概念与求解。函数的概念及性质，逆函数与复合函数的概念与计算。 第二部分 图论3图的基本概念与性质图的概念与表示，有向图、无向图、度，图同构，子图、补图，路与回路的概念，图的连通性与连通度概念、判定，点割集与割点，边割集与割边，图的矩阵表示及计算。 4几种特殊图欧拉图与汉密尔顿图的概念、性质、判定，平面图的概念、性质、判定，对偶图及着色的概念。5树及其应用树的定义及性质，生成树与最小生成树的概念与求解算法，22 / 30根树的概念及性质，最优树的概念与求解算法，最优树的应用。 第三部分 数理逻辑 6命题逻辑命题的概念、命题联结词的概念，命题公式的解释，范式的概念与求法，命题公式的等值式与蕴涵式，命题逻辑的推理理论。 7谓词逻辑谓词的概念，量词的概念，谓词公式的解释，范式的概念与求法，谓词公式的等值式与蕴涵式，谓词逻辑的推理理论。学习方法在学习本课程时要按照教学大纲规定的教学内容和教学进度，先自学文字主教材，了解基本内容和方法，找出疑难点。然后上网根据需要学习相关的部分的内容，包括网上流媒体 IP 课件、VOD 电视课资源、午间教学辅导直播、教学文件和教学辅导，也可以在课程论坛中提问设疑，寻求老师和同学的帮助。可以向主讲教师、主持教师发电子邮件等，争取尽快解决疑难问题。再下网做形成性作业。教学内容基本掌握后，最后做网上的综合练习，如果未达到教学要求，则返回本章节的起点重新组织学习；如果达到23 / 30教学要求，可进行下一章节的学习。在学习本课程的过程中要注意把握以下几点： 1基本概念要清楚离散数学课程中，几乎每一章都有一些概念需要弄清楚、理解确切并且记住。一般地，首先弄清这个概念是怎样提出来的，它的背景是什么？然后记住这个概念的确切内容，它与其他内容的内在的联系，最后掌握一些例子来帮助理解抽象的概念，这样就比较直观，形象。 2基本公式要牢记所有基本公式都应该把它们记住，就是指在对有关概念的理解的基础上，通过逐步推导和反复运用将公式记住，公式的记忆还要讲究方法，注意总结规律。 3反复学习勤思考通过反复学习来真正掌握有关的基本内容，需要经过由厚变薄和由薄变厚的两个学习过程。勤于思考，对于掌握知识，将会有一个很大的提高。 4独立作业善总结学习数学仅仅满足于能够把书看懂，公式和定理记住，而24 / 30自己不去动手做题，那是学不好数学的。独立完成作业是学习的重要手段。学时所限，本课程的理论推证和例题都比较少，必须通过做数学作业来加深对基本概念的理解，熟悉公式的运用，掌握基本解题方法，从而达到掌握知识、提高能力的目的。通过做作业，才能学到一些具体的方法，做完作业后，注意小结，养成做读书笔记的好习惯，看看这样一类问题应当如何入手，想想通过做这几个题目有那些收获，学到什么方法，使自己分析问题和解决实际问题的能力逐步提高。 5全面复习保重点期末考核的内容不仅仅是考核重点内容，建议学员依据期末考核说明，全面复习，突出重点，解决难点，注意总结各章节内容之间的内在联系，这样才能取得较好的复习效果，并在考试中取得较好的成绩。总之，本课程的学习要以文字教材为主，网上教学资源为强化，小组学习、协作学习为补充，集中面授答疑辅导为突破口，利用多种手段促进学习。按照这种方式学习效果一定会比较明显的。五、教学措施、教学安排及考核 (一) 教学媒体25 / 30综合本课程多年教学实践，分析各种教学媒体功能和作用，结合电大远程开放教育的现状，本课程的第一阶段的教学媒体主要选择以下四种： 1文字教材文字教材是落实教学大纲、传授课程基本内容的主要媒体，是其它教学媒体的基础和核心，是学生学习各门课程的基本依据。本课程文字教材全面提供课程教学与学生自学所需要的各种基本信息，包括系统阐述课程基本教学内容、明确提出学习目标、推荐基本的学习方法指导、提供与之衔接的其它媒体的信息，并根据本课程的特点，配备相当数量习题和教学辅导。本课程的文字教材采用“主辅教材合一式”的形式设置，教学基本内容与自学指导内容及媒体使用信息有机结合，利于学生使用。 2视频教材本课程的视频教材只是录像教材。录像教材是强化文字教材教学内容、提高学生学习效率的重要媒体。其内容应与文字教材密切关联，主要是对本课26 / 30程的重点内容进行阐述与归纳，对比较抽象和学生较难理解的内容或适于用画面形象演示的内容进行直观形象化的演绎和讲解。在教学内容讲授中，要借鉴了普通高校和网络学院本课程的教学实践经验，尽量做到既介绍经典的离散数学基本内容，又兼顾到离散数学在计算机科学中的应用，使学生通过本课程的学习能够了解到离散数学最基本的概貌，有助于提高学生自身的数学基础，增强分析问题和解决问题的能力，同时也是为本专业后继课的学习做好必要的准备。本课程的录像教材的制作原则是：讲重点、思路和方法。具体内容见音像教材编制方案。离散数学视频教材内容安排讲次 1 2 3 4 5 6 7第 2 章 关系与函数：复合关系与逆关系的概念与计算，关系的 闭包的概念及计算第 2 章 关系与函数：等价关系的概念与