"复旦大学计算机科学与工程系-吴永辉-离散数学-组合数学.ppt"
本资源摘要信息是基于吴永辉教授在复旦大学计算机科学与工程系讲授的离散数学课程，特别是组合数学部分。组合数学是一门研究离散结构的存在、计数、分析和优化等问题的学科。它对于算法研究变得日益重要。
组合数学的四个方面：
1. 判定所提出问题的解是否存在的存在性问题
2. 确定有解问题其不同解的个数的计数问题
3. 对可解问题去把解构造出来的构造性算法
4. 从问题的多种构造性算法中择优改进的优化问题
组合数学的历史和发展原因：
1. 组合数学的历史渊源扎根于数学娱乐和游戏之中。
2. 计算机的发展，程序的基础往往是求解问题的组合学算法。
3. 组合数学对于过去很少与数学正式接触的学科的适用性
组合数学的定义：
组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。它主要涉及将一个集合的物体排列成满足一些指定规则的格式。
两个一般性问题：
1. 排列的存在性：排列在什么样的（充分和必要）条件下能够实现？
2. 排列的计数和分类：如果一个排列是可能的，那么就会存在多种方法实现它。
组合学另外两种问题：
1. 研究一个已知的排列
2. 构造一个最优的排列
鸽笼原理：
1. 鸽笼原理的简单形式
2. 鸽笼原理的加强形式
鸽笼原理的简单形式：
1. 问题的引入
2. 鸽笼
定理10.1：n+1只鸽子飞回n个笼子，至少有一个鸽笼含有不少于2只鸽子。
例子：
1. 某次会议有n位代表参加，每位代表认识其他代表中某些人，则至少有两个人认识的人数是一样的。
2. 367人中至少有2人生日相同。
3. 1010双手套中任取11只，其中至少有两只是完整配对的。
鸽笼原理的加强形式：
定理10.2：s（s-1）个元素分成t个组，那么必存在一个组至少含有s/t个元素。
例子：
1. 设f是D到R的函数，这里|D|>|R|，令i= |D|/ |R|，则D中存在i个元素d1, d2, ……, di，使得f(d1)=f(d2)=……f(di)。
组合数学是一门重要的学科，它对算法研究和计算机科学的发展产生了重要影响。本资源摘要信息对组合数学的基本概念、历史和发展原因、定义和两个一般性问题进行了详细的介绍，并提供了鸽笼原理的简单形式和加强形式的证明和例子。
评论0
最新资源