离散数学 第三章集合.pptVIP

例3.3.3 设A1、A2和A3是全集U的子集，则形如∩Ai?（Ai?为Ai或 ）的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 3.6 基本计数原理 算法是计算机科学中最基本的概念，我们常常要对算法的效率进行分析。这就要使用一定的数学方法对计算中所需的各种资源的耗费作定量的分析，从而得出算法的时间复杂性和空间复杂性。 组合数学的最主要内容是离散对象的计数（Counting），即计算出具有某些性质的离散对象的数目（Enumerating of objects with certain properties)，常常用于算法的复杂性分析（时间复杂性和空间复杂性）。 这一节的主要内容： 加法原理、乘法原理、容斥原理、抽屉原理。 重点和难点： 如何将问题转化为能用它们解决的形式。 加法原理 The Sum Rule 若 S1, S2, …, Sm 是两两不相交的集合，则 |S1∪S2∪…∪Sm|=|S1|+|S2|+…+|Sm|。 例3.6.1 一个学生能从三张不同的计算机项目表中挑选项目。这三张表分别有 23，15 和 19 个项目。问他能从多少个项目中挑选（假设所有的项目都是不同的）? 解： 设 S={所有他能挑选的项目}， S1={第一张表中的所有项目}， S2={第二张表中的所有项目}， S3={第三张表中的所有项目}，则 S=S1∪S2∪S3, 且这三个集合两两不相交，所以 |S|=|S1|+|S2|+|S3|=23+15+19 =57。 例3.6.2 有一段程序的伪代码如下： k:=0 for i1=1 to n1 k:=k+1 for i2=1 to n2 k:=k+1 …… for im=1 to nm k:=k+1 问这段代码执行完后 k 的值是多少？ 解： k=n1+n2+…+nm。 □ 乘法原理 The Product Rule 如事件 E1 的发生有 n1 种方式，事件 E2 的发生有 n2 种方式，…，事件 Em 的发生有 nm 种方式，则 E1, E2, …, Em 发生的方式有 n1×n2×…×nm 种。 例3.6.3 1999 年，一种叫梅莉莎（Melissa）的计算机病毒用侵吞系统资源的方法破坏计算机系统。它通过以含恶意宏的字处理文档为附件的电子邮件传播。当附件被打开时，宏从用户的地址簿中找到前 50 个地址，并将以该字处理文档为附件的电子邮件转发给他们。用户接收到这些被转发的复件并将附件打开后，宏又会自动将以该字处理文档为附件的电子邮件继续转发。 根据乘法原理，第一个梅莉莎病毒只要经过 4 次转发，就可以发送 50+2500+125000+6250000=6377550 个复件。 例3.6.4 有一段程序的伪代码如下： k:=0 for i1=1 to n1 for i2=1 to n2 …… for im=1 to nm k:=k+1 问这段代码执行完后 k 的值是多少？ 解： k=n1×n2×…×nm。 □ 例3.6.5 IPv6 是 Internet Protocol Version 6 的缩写。它是 IETF（互联网工程任务组，Internet Engineering Task Force）设计的用于替代 IPv4 的新一代 IP协议。IPv6 一劳永逸地解决了 IPv4 的地址短缺问题，还提高了网络的整体吞吐量，服务质量得到很大改善，安全性有了更好的保证。 解： 在 IPv4 中 IP 地址长度为 32 位，由netid（网络 ID）和 hostid（主机标识符）组成。共有 5 类 IP 地址：A，B，C，D 和E 类。其中互联网上的计算机可以根据所在的网络不同而拥有 A，B