集合运算

2024-06-22

集合运算（共4篇）

集合运算篇1

摘要：利用C语言编制程序检验有限集合及其上二元运算是否适合结合律, 是否存在单位元, 每一个元是否存在逆元, 从而快速检查一个有限集合对所给二元运算是否成一个群。

关键词：有限群,结合律,左单位元,左逆元,程序

在半群论、群论的研究中, 经常需要构造反例以支持研究, 这就面临着检验对集合特别是有限集合规定的代数运算是否满足构成半群或群的条件, 其中结合律的检验尤为繁琐, 对含有N个元的集合, 就结合律需检验个式子, 每个式子又需进行四次二元运算;虽然对于阶数不高于20的群的个数和种类已完全得到[1]:

但在实际构建阶数不大于20的群时, 仍需与已知的群建立同构映射;因而可借助编制程序利用计算机进行快速检验;本文通过用数字字符代替字母字符, 将文[2]最多可检验含有65536个元的有限集合扩展为任意有限集合。

1 预备知识

定义2.1[3]群的第二定义

一个不空集合G对于一个叫做乘法的代数运算来说作成一个群, 假如

I, G对于乘法来说是封闭的;

II, 结合律成立:a (bc) = (ab) c

对于G的任意三个元a, b, c都对;

III, G里至少存在一个左单位元e, 能让

对于G中的任何元a都成立;

IV, 对于G的每一个元a, 在G里至少存在一个左逆元, 能让

定义2.2[3]有限群的另一定义

一个有乘法的有限不空集合G作成一个群, 假如

Ⅰ、G对于这个乘法来说是闭的;

Ⅱ、结合律成立:

对于G的任意三个元、、都成立;

Ⅲ、消去律成立:

2 程序

对于一个有限集合来说:如果利用有限群的另一定义来判断所给的有限集合及其代数运算是否构成群:封闭性的检验很简单, 只需观察所给的运算表中没有新元素出现即可, 如果有新元素出现则不满足封闭性, 反之则满足封闭性;对于消去律的验证, 只需观察集合A中的所有元素都出现在所给的运算表中每行每列, 因而只需检验结合律是否成立;但对于一个给定的阶数很大的群, 在判断消去律的时候就会显得麻烦。这时依据群的第二定义检验有限集合及其上二元运算是否构成群, 可利用计算机的方法检验结合律是否成立及左单位元, 左逆元的存在性。下面, 笔者给出利用C语言编制的检验程序。

2.1 结合律及左单位元的检验程序

2.2 左逆元的检验程序

在检验过程中, 需将运算表输入, 输入的过程即可检验封闭性, 因而本程序没有对封闭性检验的过程。

3 实例检验

设集合A中包含e, a, b, c, d, f六个元.A的乘法由下表规定:

试验证集合A对于该乘法来说是否作成群.

说明:由于本文中的程序仅对所给有限集A中的元为数字时能正常运行.若对于所给有限集A中的元为其外的字母或符号时, 须先对其做一个替换。

在利用程序检验前, 先做如下替换:分别用1, 2, 3, 4, 5, 6代替字母e, a, b, c, d, f.则A的乘法表为

利用结合律和左单位元的检验程序进行检验, 其运行过程如下:

说明:替换e, a, b, c, d, f的字母只要是数字即可, 但替换后的数字不能重复 (集合中元素具有互异性) .YES!说明所给运算结合律成立, “111111 6”表示有六个1即单位元为1。

利用左逆元的检验程序进行检验, 其运行过程如下:

说明:结果表明此六元集合及所给运算满足:以”1”为单位元, 每一个元都有左逆元;因而此六元集合及其上定义的运算构成群。

设集合A中包含四个元.A的乘法由下表规定:

利用程序进行检验, 其运行过程如下:

说明:结果表示该运算结合律成立, 但是左单位元不存在, 因为输出的是1234四个不同的数字, 显示有4个左单位元, 这与群有唯一左单位元矛盾, 因而左逆元的检验程序就没有必要执行, 所以A对于该运算不构成群。

4 结果分析

利用上述C语言程序运行时, 输入乘法表, 运行结果与实际情况完全相同;对于任意一个有限集合及其上二元运算, 利用上面的程序大大节省了检验时间。本程序理论上可检验任意有限集合, 但对于元素个数较高的有限集合, 人工输入乘法表会比较繁琐, 因而在实际过程中, 本程序的实现还依赖于乘法表的输入。

参考文献

[1]施武杰.关于有限群的阶[J].常熟理工学院学报, 2005 (19) :1-5.

[2]王绍恒.有限群的结合律的计算机检查法[J].西南师范大学学报:自然科学版, 2000 (25) :14-17.

[3]张禾瑞.近世代数基础[M].北京:高等教育出版社, 1978.

集合运算篇2

《集合间的基本运算》

授课学校

六盘水市特殊教育学校

授课教师杨霞授课班级听障高三年级课型数学

教材分析

《集合间的基本运算》是人教版普通高中课程标准实验教科书数学必修一第一章1.1.3，教材9-12页。集合的交、并运算是许多知识的切入点或重要辅助工具，比如后面要学习的函数中对于函数的定义域、值域的求解就要借助函数的并、交运算。

学情分析

学生已经学习了集合的一些基本概念以及集合的基本关系，集合的基本运算是在以上知识的基础上建立起来的，这些集合的基本运算的结果都是集合，因而需要注意运算后的集合需要具备集合的元素的三个性质。学生通过对高中数学中集合的基本知识的学习，从而能够解决一些与集合相关的问题。通过教师启发式引导，学生自主探究完成本节课的学习。教学目标

知识与技能：理解集合的基本运算的定义，掌握集合的基本运算性质，培养学生熟练运用集合运算的能力。

过程与方法：通过观察和类比，借助韦恩图（Wenn图）理解集合的基本运算，体会直观图示对理解抽象概念的作用，培养数形结合的思想。

情感态度与价值观：在集合的基本运算的学习过程中，体验数学的类比思想和应用价值，培养学生善于观察、勇于探索的良好习惯和严谨的科学态度。

教学重难点

重点：让学生把握如何求出并集、交集。

难点：能用图示法表示出集合的关系，能从图示中看出集合的关系。

教学方法

教法：启发式教学探究式教学学法：自主探究分组合作交流

教学用具

多媒体（PowerPoint）、展示图、纸质小棒

教学课时第一课时

教学准备

教学环境：多媒体教室

活动准备：制作幻灯片、准备导学案、道具

教学过程如下表

师生活动设计意图

一、课堂小游戏导入

通过复习集合的含义及表示、集合间的基本关系中有关的符号例如：、、等，引入新课中将要学习的两个符号并集、交集。学生根据幻灯片上出现的集合符号快速作答，反应时间不能超过三秒，否则就算错误。

活跃课堂气氛。让学生既巩固了已学过知识，又能培养学生对新知识的学习兴趣。

二、探索新知并集学案：

观察A，B，C这些集合之间是什么关系？

（1）集合A={1，3,5} 集合B={2,4,6}（3）集合C={1,2,3,4,5,6}（2）集合A=﹛有理数﹜?B=﹛无理数﹜??C=﹛实数﹜（3）A=﹛x|2

共同的特点：集合C是由所有属于集合A或属于集合B 的元素组成。

像这样由所有属于集合A或集合B的元素组成的集合，我们称为A与B的并集，记作：A∪B，读作：A并B

A∪B={x | x∈A,或x∈B} 学案：

根据并集的定义在导学案上进行自我练习，也可以和老师进行相互交流。例

设A={1,3, 4,5}, B={2,4,5,6},求A∪B.导案：

（提醒学生画出维恩图进行解答，然后展示PPT，让学生自己作对比，及时改正）注意：求两个集合的并集时，它们的公共元素在并集中只能出现一次.如：

4、5。（因为在集合的表示中我们已经学过了集合中元素要满足互异性）总结：求两个集合的并集就是把两个集合中所有的元素全部放到一起，如果有相同的元素写一个就行。那么请同学们再来看下一张幻灯片，集合A、B、C的关系又是怎样的呢？（出示PPT）学案：

说出集合A,B与集合C之间的关系吗?(1)A={2,4,6,8,10},B={2,3,5,8,9,12},C={2,8};导案：

集合C中的元素只有2、8，通过观察我们可以发现，集合C中的元素2、8，集合A、B中也有。像这样的关系，在数学中我们称为交集，这就是我们将要学习的集合第二个运算交集。

2、交集导案：

一般地,由属于集合A且属于集合B的所有元素组成的集合,称为A与B的交集,记作A∩B,(读作“A交B”)，A∩B={x|x∈A,且x∈B} 学案：

学生以分组（分为三组）的形式，分别完成以下内容：（1）三种不同状态下集合A、B 交集部分的描绘

（2）用纸棒代替两条直线在相交、平行、重合的状态

下交集是怎样的情况。（3）设A={x|x>-1},B={x|x<1}，求A∩B.学案：学生来讲授，提醒求不等式的交集、并集关系时，首先要画出数轴，然后在数轴上标记出集合A、B的区间，最后求出交集，同样用不等式的形式表示出来。

三、课堂小结

导案：

快速区分并、交运算符号的方法：求集合A、B的并集就是把所有集合A、B中的元素全部放在一起，如果有相同的元素写一个就行。

求集合A、B的交集就是找到集合A、B中共有的元素组成一个集合就是集合A、B的交集。板书设计

集合的基本运算并集

A∪B={x|x∈A,或x∈B}

二、交集

A∩B={x|x∈A,且x∈B}

通过学生自己的观察、思考然后再进行教学，学生能够更加快速的掌握新知识。

通过练习的方式强化新知识的吸收。

集合运算篇3

关联规则挖掘作为数据挖掘的重要内容, 主要用于挖掘大量数据中项集之间的关联或相关关系利用Web访问信息挖掘[1,2]改进访问效率是关联规则挖掘的典型范例。最近几年已被业界所广泛研究, 其研究成果可以应用于Web服务器推送, 自适应网站, 改进服务器效率等方面。因此, 对关联规则的研究具有非常重大的意义。

1 Apriori算法思想及其瓶颈

挖掘关联规则, 首先应该计算出整个项目集的最大频繁集, 然后根据最大频繁集生成所有大于最小置信度的规则。在众多的关联规则挖掘算法中, Apriori算法[3]是最基本也是最著名的一种。其核心思想是通过项目集元素数目不断增长来逐步完成频繁项目集发现的。

(1) 搜集所有支持度不低于给定minsup的项目构成频繁项目序列集1-频繁项目集, 记为L1;

(2) 连接Ll中所有元素对形成候选工作集C, 再次扫描目标数据库, 计算C中每个项目集的支持, 记录所有不低于minsup的项目构成2-频繁项目集, 记为L2;

(3) 连接L2中所有元素对形成候选工作集C, 再次扫描目标数据库, 计算C中每个项目集的支持, 记录所有不低于minsup的项目构成3-频繁项目集;

(4) 重复上述步骤, 直到不再有新的候选产生为止。

算法利用了两条基本性质

性质1如果A是频繁项集, 那么A的任何子集都是频繁项集。

性质2如果A是非频繁项集, 那么A的任何超集都是非频繁项集。

2基于位运算的频繁集计算方法

Apriori算法在反复扫描中存在以下几个问题[4]值得改进。

(1) 根据性质1, 对不可能成为频繁集的连接, 如果能够事先判断出来, 就可以节省连接时间, 并减少用于存储候选项的存储空间。

(2) 如果能减少由于计算支持度而引发的遍历原数据库次数, 就可以节省大量的时间。

基于上面两点, 笔者结合集合运算和位运算, 对Apriori算法进行了改进。

算法思想: (1) 扫描数据库中的表, 将所有支持度大于最小支持度的项目组成1-频繁项目集, 记为L1, 利用位视图来表示访问了该数据项的事务, 即如果事务Ti访问了该数据项, 则这组整数的第i位就为“1”, 否则为“0”。 (2) 将L1中的集合按照Apriori算法中定义的连接规则两两进行并运算, 对应的位视图作交运算, 计算结果中位“1”的个数, 作为支持数, 将所有支持度大于最小支持度的项目组成2-频繁项目集。 (3) 重复进行上述计算k-频繁项目集。

算法描述如下:

3算法比较分析

相对于经典的Apriori算法, 该算法只需扫描1次原始事务数据库, 产生最初的候选集。后续操作, 例如产生候选集, 计算支持数等操作都不需要访问原数据库。另外, 该算法就避免了非频繁集的生成, 不需要剪枝。

在相同条件下, 采用Apriori算法和本例中的算法进行测试比较。测试数据为20万条, 测试结果如图1所示。

4算法示例

数据挖掘在改进Web站点的访问效率方面具有重要的作用。如果在Web服务器上能够识别出典型的对文档的访问模式, 那么就可以应用相应的预推送技术提前推送给访问用户, 以加速用户的访问。表1中整理出了在某个时间段内, 用户所访问的站点页面情况。

将每个用户看成一个事务, 用数字1～6代替页面a.htm～f.htm, 可以转换成表2所示形式。假设最小支持数为3, 以下给出利用位运算求解频繁集。

(1) 扫描一遍事务数据库, 建立每一个事务的位视图, 如表3所示。

(2) 根据表2, 计算位视图中各行1的个数 (即事务支持数) , 并删除那些支持数小于minSup的的项集, 获得1-频繁项目集。表4给出了上例的1-频繁项目集, 由于项目集{5}的最小支持数只有2, 故从表中被删除。

(3) 根据得到的1-频繁项目集, 将项集两两作并运算, 并将对应的两个位视图的行进行交运算, 然后计算每项事务支持集元素的个数, 并删除小于最小支持数的项集, 得到表5所示的2-频繁项目集。

(4) 按照步骤 (3) , 继续计算表3中两两项集之间的并运算, 同时将对应的位视图中的行作交运算。但需要注意的是, 从计算3-频繁项目集开始, 必须保证Lk-频繁项目集 (K≥3) 的子集也是频繁的。因此, 本例的3-频繁项目集如表6所示。

(5) 由于无法产生4-频繁项目集, 频繁集挖掘算法结束。

根据关联规则算法, 我们可以看出在用户访问了页面b.htm和c.htm后又访问页面d.htm的信度为75%。因此, 为了提高用户访问网站的速度, 在用户访问了页面b.htm和c.htm之后, 网站可以将页面d.htm提前推送给用户。

5总结

本文从两个方面对Apriori算法进行了改进, 在生成频繁集过程中避免了生成非频繁项目集的超集, 另外, 在计算支持数时利用位运算避免了扫描原始数据库。实验表明相对于原算法, 在时间开销和空间开销上都要优越得多。

参考文献

[1] Mobasher B, Cooley R.Srivastava J.Automatic person a1ization based on Web usage mining. Communications of the ACM, 2000;43 (8) :142—151

[2]Huszerl G, Majzik I.Modeling and analysis of redundancy manage-ment in distributed object oriented systems by using UML statecharts.In:Proceedings of27, Euromicro Conference.2001:200

[3]Srikantr A.Fast algorithms for mining association rulers//Proceeding of the20th Int7Conference on Very Large Databases, Santiago, Chil-e, Santiago de Chile:Morgan Kanfmarm, 1994:487—499