离散数学教程集合论与图论

《离散数学教程集合论与图论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、离散数学教程（集合论与图论）离散数学：计算机科学与技术的数学基础课内容：集合论，图论，组合数学，代数结构，数理逻辑集合论:（第1-4章）组合数学初步:（第5-7章）图论:（第8-11章）教师介绍教师：吴永辉博士副教授简历：1984-1988上海科技大学计算机系本科1988-1991复旦大学计算机系硕士1991-2003华东师范大学计算机系工作1998-2001复旦大学计算机系博士2003-复旦大学计算机系工作答疑E-mail:yhwu@fudan.edu.cn《集合论与图论》课件制作软件MicrosoftPowerPointMathTypeEquation

2、《集合论与图论》课程大纲课程性质与目的教学内容与要求使用教材、参考书籍命题说明和题型课程性质、目的与基本要求课程性质本课程讲授计算机科学与技术的数学基础课《离散数学》的部分主要内容：集合论、图论与组合数学初步，是计算机专业的主干课程之一。本课程前行课程为线性代数，数学分析(上)。课程目的使学生掌握集合论、图论与组合数学初步的基本内容，并对证明的思想和方法深入理解和体会，初步培养学生的思维过程的数学化。基本要求：掌握集合论、组合学和图论的基本概念，清楚了解引入基本概念的实际背景、各概念间相互关系；掌握基本定理以及有关理论题的证明技巧；掌握解决计数问题的基本方法和

3、技巧；掌握图论中各算法设计的思想、正确性证明以及算法的应用。为进一步学习计算机其他课程打下坚实的基础。教学方式本课程以课堂讲授为主。考核方式平时作业；集合论、组合数学和图论3次课堂练习；期中，期末的两次笔试考试。教学内容与要求----集合论第一章集合的基本概念掌握：集合的基本概念，集合的运算。了解：集合论的悖论。掌握证明两个集合相等的基本法和公式法。第二章关系掌握：关系的性质、运算和关系的闭包，以及等价关系和偏序关系。了解：关系在关系数据库中的应用。掌握证明的类型。第三章函数掌握：函数的基本概念，复合函数和逆函数。了解：集合的特征函数。第四章无限集掌握：基数及

4、基数的比较，判断可列集与不可列集的方法。了解：集合的递归定义。教学内容与要求----组合数学初步第五章鸽笼原理掌握：利用鸽笼原理解决组合数学中一些存在性问题的技巧。第六章排列与组合掌握：集合的排列与组合，多重集的排列与组合等计数方法，有序划分和无序划分。第七章生成函数与递推关系掌握：用生成函数和递推关系解决组合计数问题的方法，以及求解递推关系的生成函数方法。了解：求解递推关系的特征根方法。教学内容与要求----图论第八章图的基本概念掌握：图的基本术语，路、回路和连通的基本概念，求最短路的算法及算法正确性证明，欧拉图和哈密顿图的基本概念、判别方法以及有关定理。第九章平

5、面图与图的着色掌握：平面图的基本概念、平面图的特征和欧拉公式，掌握图的点着色和平面图的面着色概念。了解：图的边着色概念。第十章树掌握：树的基本性质和生成树、割集、有根树的概念，求最小生成树和最优树的算法及算法的正确性证明。了解：树的计数问题。教学内容与要求----图论第十一章连通度、网络与匹配教学时间：10学时；掌握：点连通度和边连通度的基本概念，掌握最大网络流算法及算法正确性证明，掌握匹配的基本概念和判别方法，掌握独立集和覆盖的基本概念和有关定理及证明方法。了解：佩特里网及其图的表示。使用教材《离散数学》，赵一鸣，阚海斌，吴永辉编著。人民邮电出版社，2011。参考书籍

6、一、基础[1]BernardKolman,etc..DiscreteMathematicalStructure,ThirdEdition.1997.清华大学出版社,PrenticeHall.(中、英文版)[2]左孝凌,李为槛,刘永才.离散数学理论分析题解。1988，上海科技文献出版社。[3]左孝凌,李为槛,刘永才.离散数学。1988，上海科技文献出版社。二、提高[4]KennethH.Rosen.DiscreteMathematicsanditsApplications.(4th,5thEdition).机械工业出版社,McGraw-Hill.(中、英文版)[5]吴永辉，

7、王建德。数据结构编程实验：大学程序设计课程与竞赛训练教材（附光盘）。机械工业出版社。2012。参考课件[1]《DiscreteMathematicsandItsApplications》课件在线学习网站[1]北京大学计算机系《离散数学教程》网上教室http://necweb.neu.edu.cn/ncourse/lssx/index.htm[2]北京邮电大学《离散数学》在线课件http://www.pris.edu.cn/lesson/dis-math/Content.htm[3]国立交通大学《