《组合数学》教学大纲

《组合数学》教学大纲课程基本信息课程中文名称：组合数学课程类别：专业选修课适用专业：数学与应用数学、计算机专业课程地位：专业选修课总学时：30学时总学分：27、先修课程：数学分析、微分方程、高等代数课程目标1、组合数学是计算机应用领域中十分重要的基础理论课程，是计算机应用技术研究生的学位专业基础课。学习该课程的主要目的是使学生掌握组合数学的理论、技术和方法。应用组合数学方法解决实际工作中的计算机应用问题。组合数学是一门提高思维分析能力和自我构造算法本领的必修课程。2、通过组合数学这门课程的学习，可以有效地锻炼学生的论证能力，培养学生用组合学的思想和方法分析问题和解决问题的能力。使学生能得到严格的逻辑推理与抽象思维能力的训练，建立数学模型与计算机科学实践之间的内在联系，不仅可以提高专业开发能力，而且为计算机教育打好数学基础。通过本课程的学习，应达到知识和能力两方面的目标：(1)知识方面：系统地学习组合数学中的排列与组合、容斥原理及其应用、递归关系、生成函数、整数的分拆、鸽巢原理和定理、二分图问题和组合设计。为解决实际问题，提高计算机专业开发能力打好知识基础。(2)能力方面：使学生能得到组合数学的思想、方法和理论严格的逻辑推理与抽象思维能力的训练，了解数学中的抽象思维与计算机科学实践之间的内在联系，提高分析问题和解决问题的能力3、本课程开设时间比较灵活，总学时数为30学时。合问题中的一些应用。§2.1鸽笼原理的简单形式§2.2一般形式§2.3ramsey原理容斥原理（8学时）[教学目的与要求]所谓容斥原理是指在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。本部分介绍了容斥原理和容斥原理的若干应用。容斥原理是解决组合计数问题的一个重要工具，它研究的是有限个集合的并集形成的集合的计数的方法。本章内容包括容斥原理一般公式、有重组合计数问题、错位排列问题、带禁止位、相对禁止位排列等复杂问题的计数。了解容斥原理的符号形式和一般形式，能熟练地把一些问题的计数转化为应用容斥原理来计数。§3.1容斥原理§3.2集合的R组合§3.3错排问题§3.4相对位置上有限制的错排问题母函数（10学时）[教学目的与要求]本章学习母函数的概念、性质、表示法及母函数在排列组合中的应用。本部分介绍普通生成函数及其应用、指数生成函数及其应用。使学生掌握利用常生成函数计算组合计数、利用指数生成函数计算排列计数的重要方法。本部分总的要求是：为何要引入生成函数，两种生成函数及其应用。概念清晰、准确。§4.1母函数的基本概念§4.2母函数的基本运算§4.3母函数在组合中的应用§4.4整数的拆分四、教学方法理论教学五、课程考核考试六、教材与参考书教材：孙世新编《组合数学》（第三版）．电子科技大学出版社，2003。参考书目：1.《组合数学》，屈婉玲编，北京大学出版社,2.《组合数学引论》，孙淑玲编著,中国科学技术大学出版社.3.《组合数学及其算法》,杨振生编著,中国科学技术大学出版社。4.《组合数学》（第四版）卢开澄编著清华大学出版社2006年12月5.《组合数学》[美]R.A.Brualdi著冯舜玺等译机械工业出版社2005年2月七、本课程的教学方式说明本课程的特点是理论性强，思想性强，与相关基础课及专业课联系较多，教学中应注重启发引导学生掌握重要概念的背景思想，理解重要概念的思想本质，避免学生死记硬背。要善于将有关学科或生活中常遇到的名词概念与组合数学的概念结合起来，使学生体会到学习组合数学的必要性。注重各教学环节（理论教学、习题课、作业、辅导参考）的有机联系,特别是强化作业与辅导环节，使学生加深对课堂教学内容的理解，提高分析解决问题的能力和运算能力。教学中有计划有目的