《离散数学》教学大纲

“离散数学”课程教学大纲课程编号:08012060课程名称：《离散数学》/DiscreteMathematics学时：64学时学分：4适用专业：计算机相关专业开课学期：第4学期开课部门：数学与计算机科学学院先修课程：线性代数、高等数学考核要求：课程成绩按百分制计算，其中考试成绩占80%，平时作业课堂考核占20%。使用教材及主要参考书：王元元等著，《计算机科学中的离散结构》，左孝凌等著，《离散数学》，上海科学技术文献出版社,2001年方世昌著编，《离散数学》,西安电子科技大学出版社，2001年一、课程的性质和任务《离散数学》是计算机科学与技术专业教学中最为重要的核心基础课程，它是学习专业理论不可少的数学工具，是计算科学专业的专业必修课程。通过学习本课程,培养学生的抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力。《离散数学》是现代数学的一个重要分支,为学生今后从事计算机科学各方面的工作提供重要的工具。二、教学目的与要求本课程主要有数理逻辑、集合论、图论、代数系统等内容，是一门理论性较强，应用性较广的课程。课程的教学组织应为计算科学专业的学生提供必要的数学基础和展示离散数学的实用性为目的，使专业学生理解严谨的数学概念的重要性以及这些概念对应用的作用，进一步提高抽象思维和逻辑推理的能力；。离散数学课程教学的目标，使学生学会特定的一些数学事实并知道怎样应用，教会学生做数学思维和解决应用问题。为此，应将数学推理、组合分析、离散结构、算法思考以及应用和建模等手段，作为核心内容和课程主线，有机地交融在一起并体现到对学生是否真正掌握课程知识的考核中。三、学时分配章节教学内容学时分配小计讲课试验上机讨论/习题第一章集合代数62第二章两个常用数学原理31第三章逻辑代数-命题演算82第四章逻辑代数-谓词演算62第六章计数62第八章图82第九章二分图、平面图和树82第十章关系42四、教学中应注意的问题本课程以课堂讲授为主，精讲多练，注重理论联系实际。各章中平行的内容可安排学生自学，以提高学生独立思考和解决问题的能力。《离散数学》课程涉及的概念较多，解题方法灵活多样，更需要分析和解决问题的能力，因此必须通过做练习题来加深对概念的理解和掌握，熟悉基本公式、基本方法的运用，从而达到理解、掌握所学知识的目的。因此独立完成作业是学好本课程的重要手段。在教学中，通过习题的布置，使学生深入理解基本原理及概念，提高分析和解决问题的能力。作业分为必做和选做两类。必做作业是基本教学所要求的，每个学生都要认真完成；选做作业涉及提高部分的内容，供不同层次的学生选做。每次课后布置3-5题作业。教学过程中，有关定义、定理、性质、特征等概念的内容要求，由低到高分“知道、了解、理解”三个层次。五、课程教学内容第一章集合代数1.基本内容：集合的概念和表示，集合的运算，集合的归纳定义方法2.教学要求：掌握集合的概念和表示，熟练掌握集合的并、交、差、补、差运算并通过文氏图加深理解，会做笛卡尔积的运算；理解集合的包含与相等、幂集等基本概念。熟练掌握集合的基本运算，并能用以证明集合恒等式。掌握集合相等的互为子集和利用性质的证明方法，掌握包含关系的证明方法。3.教学重点、难点：集合相等的性质，集合包含的性质第二章两种常用数学原理1.基本内容：归纳原理、鸽笼原理2.教学要求：掌握归纳原理的数学思想和证明方法；掌握鸽笼原理及其应用3.教学重点、难点：归纳原理和鸽笼原理的理解第三章逻辑代数-命题演算1.基本内容：命题和逻辑联结词、逻辑等价式和逻辑蕴含式、范式2.教学要求：熟练掌握命题的概念和表示法；熟练掌握对命题的符号化；理解命题概念，会判断语句是否命题；掌握命题的基本等值公式和蕴含式，掌握用有关的定理证明；掌握命题等价的证明方法，和命题的范式和主范式的求解方法，掌握用主析取范式判断两个公式是否等价的方法；掌握如何将实际问题转化为逻辑问题。3.教学重点、难点：命题公式的等价和蕴含的证明。第四章逻辑代数-谓词演算1.基本内容：谓词演算的基本概念、谓词演算永真式2.教学要求：理解谓词、量词、变元、个体域等概念；掌握用谓词、量词、联接词构造谓词逻辑公式的方法；熟练掌握任意和存在量词的意义；会将谓词逻辑作为工具，将命题符号化，熟练掌握对命题的符号化；掌握谓词公式中常用的等价式和蕴含式；掌握命题等价的证明方法。3.教学重点、难点：常用的谓词公式的等价式和蕴含式。第六章计数1.基本内容：计数基本性质、排列组合、重集的排列和组合2.教学要求：掌握乘法、加法原理及其包含排斥原理；掌握排列和组合的计数；掌握重集的排列和组合及其禁位计数3.教学重点、难点：排列、组合和重集的排列与组合。第八章图1.基本内容：图的基础知识，路径、回路及连通性，欧拉图与哈密尔顿图，图的矩阵表示2.教学要求：掌握图的基本知识；掌握路径、回路和连通性的概念；熟练掌握欧拉图与汉密尔顿图的定义，理解相关定理及其应用；掌握欧拉回路和汉密尔顿回路的求解方法；掌握图的矩阵表示，可达矩阵和路径矩阵求法。.3.教学重点、难点：图的连通性，欧拉回路和汉密尔顿回路的求解，图的矩阵的应用。第九章二分图、平面图和树1.基本内容：二分图，平面图和树2.教学要求：掌握二分图，平面图和树的基本概念；掌握二分图的判定，掌握匹配的概念和最大匹配的求解方法及其匹配的应用；理解平面图、极大平面图的定义及相关定理，掌握平面图的欧拉公式和平面图的性质，知道非平面图的定义和判定定理；掌握求最小生成树的卡鲁斯科尔算法，掌握完全二叉树的性质和算术表达式的二元位置树的表示法和三种遍历方法，掌握树的应用。3.教学重点、难点：求最大匹配的匈牙利算法，求最小生成树的卡鲁斯科尔算法，算术表达式的二叉树表示法和波兰式和逆波兰式第十章关系1.基本内容：二元关系，等价关系与等价类，序关系2.教学要求：理解二元关系的概念及其性质；掌握二