离散数学2 集合与序列

7
2. 描述法：说明集合A中的元素x应满足的条件。 描述法：说明集合A中的元素x应满足的条件。 记为： 记为： A＝{x | x满足的条件} 满足的条件} 如: 大于0小于1的实数集合： 大于0小于1的实数集合：{ x | (0<x<1)且 x∈R }; 所有正奇数的集合：{ x | x＝2y+1且 y∈N }。 y+1 所有正奇数的集合：
b是这位理发师 如果这位理发师不自己刮脸 这位理发师不自己刮脸, 如果这位理发师不自己刮脸, 即b∈C，则 b∉C； 如果这位理发师自己刮脸, 即b∉C，则 b∈C。 这位理发师自己刮脸, ∴ b∈C或b∉C都不能成立
11
三、集合的运算 设A、B是两个集合，E是全集，则 是两个集合， 是全集， 并集(union) 定义2.1.1 定义2.1.1 A和B的并集(union) A∪B、 A和B的交集(intersection) A∩B、 交集(intersection) A的补集(complement) 补集(complement) 分别定义如下： 分别定义如下： A∪B ＝｛x | x∈A 或 x∈B｝ ＝｛x A∩B ＝｛x | x∈A 且 x∈B｝ ＝｛x x∈ ＝｛x ＝｛x | x ∉A 且 x∈E｝叫 空集 (empty set), 定义】没有任何元素的集合叫空集 空集(empty set), 记为∅ 记为∅ 。 【 定义 】 当我们所讨论的集合都是某一集合的子 定义】 集时, 这某一集合就称为全集 集时, 这某一集合就称为全集(universal set), 并用E表 全集(universal set), 并用E 示。
A－B ? B－A。 = B－
15
由定义或文氏图都容易得到下面的公式: 由定义或文氏图都容易得到下面的公式: A－B＝ A ∩ B
16
2.1.2 集合运算的实现
Questions
如何在计算机 表示集合? 如何在计算机中表示集合? 计算机中 如何在计算机中计算集合的运算 如何在计算机中计算集合的运算? 计算集合的运算?
6
表示一个集合的方法通常有以下三种: 表示一个集合的方法通常有以下三种: 1. 列举法。 如： 列举法。 A =｛ 0 , 1 , 2 , 3 ｝ 。 自然数集N用列举法表示是｛ 自然数集N用列举法表示是｛0, 1, 2, 3, …｝。
根据所列元素, 根据所列元素, 容 易判断N 易判断N中的其余 元素
18
一、紧凑存储方式下的集合运算的实现 算法2.2.1：求两个集合交集的算法。 ：求两个集合交集的算法。 算法 2 4 6 51 2 4 3
依次扫描A、B中的元素，若相同，则把其添加到C中 依次扫描 、 中的元素，若相同，则把其添加到 中 中的元素 A 1 2 4 5 6 B 2 3 4
C
19
算法2.2.1：求两个集合交集的算法。 算法2.2.1：求两个集合交集的算法。 FindIntersection(set A, set B) //求出集合A和B的交集 //求出集合 求出集合A { iALength = length(A) //集合A的长度 //集合 集合A iBLength = length(B) //集合B的长度 //集合 集合B for(i=0;i<iALength;i++) { for(j=0;j<iBLength;j++) if(A[i]==B[j]) { C[k]=A[i]; //添加交集元素到交集C中 //添加交集元素到交集 添加交集元素到交集C k++; break； break； } } Return C; //集合C就是A与B的交集 //集合 就是A 集合C }
24
算法时间复杂度分析： 算法时间复杂度分析：
for(i=0;i<iALength;i++) { for(j=0;j<iBLength;j++) …… }
时间复杂度： 时间复杂度：O(n2) 思考：若集合中元素按次序存储在数组中， 思考：若集合中元素按次序存储在数组中， 则算法可以怎样改进？ 则算法可以怎样改进？
22
算法2.2.2：求两个集合减法的算法。 ：求两个集合减法的算法。 算法
2 4 6 51
2 4 3
删除在B中出现的 的元素 删除在 中出现的A的元素。 中出现的 的元素。 A 1 2 4 5 6 B 2 3 4
23
算法2.2.3：集合减法运算算法。 算法2.2.3：集合减法运算算法。 FindDeference (set A, set B) //求出集合A-B的差集 //求出集合 求出集合A { iALength = length(A) //集合A的长度 //集合 集合A iBLength = length(B) //集合B的长度 //集合 集合B for(i=0;i<iBLength;i++) { for(j=0;j<iALength;j++) if(A[j]==B[i]) { A=A-A[i]；//从集合 中去掉元素A[i] A=A-A[i]；//从集合A中去掉元素A[i] 从集合A Break； Break； } } Return A; //集合A就是A与B的差集 //集合 就是A 集合A }
10
罗素悖论：
Questions
在一个僻静的孤岛上，住着一些人家， 在一个僻静的孤岛上，住着一些人家， 岛上只有一位理发师，该理发师专给 专给那些 岛上只有一位理发师，该理发师专给那些 并且只给那些自己不刮脸的人刮脸 那么， 那些自己不刮脸的人刮脸。 并且只给那些自己不刮脸的人刮脸。那么， 谁给这位理发师刮脸？ 谁给这位理发师刮脸？ 解：设 C＝{x|x是不给自己刮脸的人} 是不给自己刮脸的人}
25
二、非紧凑存储方式下的集合运算的实现 假定全集E是有限的。首先为 假定全集E是有限的。首先为E的元素任意规定 一个顺序，例如d 一个顺序，例如d1，d2，…，dn，于是可以用长度为 n的位串(布尔型数组)表示E的子集A： 位串(布尔型数组)表示E的子集A 如果d 属于A 则位串中第i位是1 如果di属于A，则位串中第i位是1； 如果d 不属于A 则位串中第i位是0 如果di不属于A，则位串中第i位是0。
8
3. 递归法(递推法) 递归法(递推法) 数列常常用递归定义。 数列常常用递归定义。 【例】斐波那契数列: 斐波那契数列: f 1= 1 , f 2= 1 , fn=fn-1+fn-2，n=3,4,… n=3
9
【 定义 】 集合 A 中元素的个数称为 A 的 基 （ 基数 , 定义】 集合A 中元素的个数称为A 基数, cardinality） 也称为长度 记作| cardinality），也称为长度，记作|A|。 当|A|是有限数 长度， 时, 集合A称作有限集, 否则称为无限集。 集合A称作有限集 否则称为无限集 有限集, 无限集。 显然, 显然, |∅|＝0。
17
1、程序中怎样来表示集合？ 程序中怎样来表示集合？ 选用面向过程还是面向对象 面向过程：数组 面向过程： 面向对象： 面向对象：vector 有序还是无序存储 有序利于集合的运算 无序输入数据简单 元素与元素之间是否需要紧凑存储 紧凑存储节省空间，运算时间长（大量检索） 紧凑存储节省空间，运算时间长（大量检索） 不紧凑存储则是以空间换取时间 2、如何利用程序实现集合的运算？ 如何利用程序实现集合的运算？
20
算法2.2.2：求两个集合并集的算法。 ：求两个集合并集的算法。 算法 2 4 3
2 4 6 51
把A中的元素加到 中，再扫描 ，把其不再 中 中的元素加到C中 再扫描B，把其不再A中 中的元素加到 的元素加入C。 的元素加入 。 A 1 2 4 5 6 B 2 3 4
C
21
算法2.2.2：求两个集合并集的算法： 算法2.2.2：求两个集合并集的算法： FindUnion (set A, set B) //求出集合A 和 B 的并集 //求出集合 求出集合A { iALength = length(A) //集合A的长度 //集合 集合A iBLength = length(B) //集合B的长度 //集合 集合B C=B；//用集合 存储集合的并集， C=B；//用集合C存储集合的并集，把B中的元素赋值到C中 用集合C 中的元素赋值到C iCLength = iBLength for(i=0;i<iALength;i++) { bFind=false; for(j=0;j<iBLength;j++) //循环1 //循环 循环1 if(A[i]==B[j]) { bFind=true; //A[i]为公共元素； //A[i]为公共元素 为公共元素； break； //跳出循环 break； //跳出循环1 跳出循环1 } if not find //A[i]不是公共元素； //A[i]不是公共元素 不是公共元素； 加入到集合C C[i length+1]=A[i]; //把A[i]加入到集合 C[iClength+1]=A[i]; //把A[i]加入到集合C中； iClength=iClength+1; } Return C; //集合C就是A与B 的并集 //集合 就是A 集合C }
12
直观地表示集合间关系的文氏图 直观地表示集合间关系的文氏图： 文氏图：
注：文氏(John Venn), 1834-1923, 英国逻辑学家。 文氏(John 1834-1923, 英国逻辑学家。 注意： 注意 ： 文氏图只能帮助我们形象地理解复杂的集 合关系, 一般不作为一种证明方法 合关系, 一般不作为一种证明方法。 不作为一种证明方法。
2
2.1.1 集合的定义 一、集合（sets）的概念 集合（sets）
抽象成数学概念
集体
集合
组成集合的事物（也称个体）叫做该集合的元素 组成集合的事物（也称个体）叫做该集合的元素 （elements）。 例如： elements）。 例如： 计算机学院2011级全体同学 计算机学院2011级全体同学； 级全体同学； 全体自然数； 全体自然数； 方程 x2-1＝0的解； 的解；