《组合数学》教学大纲

《组合数学》教学大纲

一、课程基本信息

1、课程中文名称:组合数学 2、课程类别:专业选修课

3、适用专业:数学与应用数学、计算机专业 4、课程地位:专业选修课 5、总学时:30学时 6、总学分:2

7、先修课程:数学分析、微分方程、高等代数

二、课程目标

1、组合数学是计算机应用领域中十分重要的基础理论课程,是计算机应用技术研究生的学位专业基础课。学习该课程的主要目的是使学生掌握组合数学的理论、技术和方法。应用组合数学方法解决实际工作中的计算机应用问题。组合数学是一门提高思维分析能力和自我构造算法本领的必修课程。

2、通过组合数学这门课程的学习,可以有效地锻炼学生的论证能力,培养学生用组合学的思想和方法分析问题和解决问题的能力。使学生能得到严格的逻辑推理与抽象思维能力的训练,建立数学模型与计算机科学实践之间的内在联系,不仅可以提高专业开发能力,而且为计算机教育打好数学基础。通过本课程的学习,应达到知识和能力两方面的目标:(1)知识方面:系统地学习组合数学中的排列与组合、容斥原理及其应用、递归关系、生成函数、整数的分拆、鸽巢原理和 定理、二分图问题和组合设计。为解决实际问题,提高计算机专业开发能力打好知识基础。 (2)能力方面:使学生能得到组合数学的思想、方法和理论严格的逻辑推理与抽象思维能力的训练,了解数学中的抽象思维与计算机科学实践之间的内在联系,提高分析问题和解决问题的能力

3、本课程开设时间比较灵活,总学时数为30学时。

三、课程内容

第一章 排列与组合(8学时)

[教学目的与要求]

本部分集中介绍排列和组合。使学生认识到排列和组合是组合数学研究的最简单、最基本的课题。通过三个基本计数原理及排列、组合公式的研究,进一步讨论了几个计数问题,能体会要想完满地解决一个排列和组合问题,往往需要较强的组合思维、巧妙的组合方法、熟练的组合技巧。本章内容初步展示了组合数学的迷人魅力,有利于激发学生学习后续内容的兴趣。

§1.1 加法规则和乘法规则

§1.2 排列 §1.3 组合 §1.4二项式定理 §1.5组合恒等式

第二章 鸽笼原理(4学时)

[教学目的与要求]

本部分集中介绍鸽笼原理和定理,所谓的鸽巢原理也叫抽屉原理,是Ramsey定理的特例。它的简单形式是:把n?1个物体放入n个盒子里,则至少有一个盒子里含有两个或两个以上的物体。Ramsey定理的简单形式:设p,q是正整数,p,q?2,则存在最小的正整数R(p,q),使得当n?R(p,q)时,用红蓝两色涂色Kn的边,则或者存在一个蓝色的完全p边形,或者存在一个红色的完全q边形 。通过本章内容的学习可以使学生掌握鸽笼原理和 定理以及它们在解决有关存在性的组

合问题中的一些应用。

§2.1 鸽笼原理的简单形式

§2.2 一般形式 §2.3 ramsey原理

第三章 容斥原理(8学时)

[教学目的与要求]

所谓容斥原理是指在计数时,为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。本部分介绍了容斥原理和容斥原理的若干应用。容斥原理是解决组合计数问题的一个重要工具,它研究的是有限个集合的并集形成的集合的计数的方法。本章内容包括容斥原理一般公式、有重组合计数问题、错位排列问题、带禁止位、相对禁止位排列等复杂问题的计数。了解容斥原理的符号形式和一般形式,能熟练地把一些问题的计数转化为应用容斥原理来计数。

§3.1 容斥原理 §3.2 集合的R组合 §3.3错排问题

§3.4相对位置上有限制的错排问题

第四章 母函数(10学时)

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4