【doc】测试二元运算乘法表是否构成群表的算法设计

【doc】测试二元运算乘法 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 是否构成群表的算法设计 测试二元运算乘法表是否构成群表的算法 设计 第24卷第3期 2003年3月 东北大学(自然科学版) JournalofNortheasternUniversity(NaturalScience) Vo1.24,No.3 Mar.2003 文章编号:1005—3026(2003)03—0233—04 测试二元运算乘法表是否构成群表的算法设计 张大坤,王光兴 (东北大学信息科学与 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院,辽宁沈阳110004) 摘要:对计算机测试二元运算乘法表是否构成群表的算法进行研究,一个乘法表构成群表的 充要条件是乘法表具有两个性质.在测试乘法表构成群表的第一性质中提出了直接逐行,逐列测试 G中所有元素,按行,按列搜索相同元素及相异元素计数三种算法;在第二性质测试中,对搜索与单 位元1构成矩形的同行,同列元素中提出自然升序法,外推法及小段优先三种算法;在遍历整个二维 乘法表判别矩形第4顶点元素特性中,提出了单个矩形移动,按行(Yd)(一1)个矩形同时移动,(一 1)个矩形同时移动及改进的单个矩形移动四种算法;讨论了主要算法的复杂性;用VisualC++6.0 实现了算法的程序设计;用所设计的软件对多个乘法表进行测试均得到了正确的结果. 关键词:二元运算;乘法表;群表;算法;计算机测试 中图分类号:TP391文献标识码:A 群论是近世代数的重要内容,在许多领域得 到了广泛的应用.任何一个有限群都可以用一个 乘法表即群表来表示,群表可以直观地反映出群 的许多特性?~5J.在许多情况下是用群表来定义 群的,群表是研究群论及应用群论解决实际问题 的有力工具L6,7J. 二元运算应用广泛,在解决实际问题中经常 用乘法表来定义有限集合中的二元运算,判别所 定义的二元运算是否构成群很有意义,若构成群 就可以应用群论方法来求解实际问题.当二元运 算是通过乘法表给出时,没有给出抽象的运算规 则,难以用证明的方法来判别是否构成群,用群的 四个基本性质一一测试也很困难.然而,若根据乘 法表构成群表的充要条件来测试所定义的二元运 算是否构成群,就使测试问题容易实现.采用人工 方式测试一个二元运算乘法表是否构成群表,不 仅费时费力,而且出错的机会多,特别是对于高阶 群用计算机来完成测试工作就显得尤为重要l8, 实现计算机测试的关键是设计出有效的算法. 1二元运算乘法表及构成群表的充 要条件 1.1二元运算乘法表 二元运算是最常见的代数运算,它的定义如 F. 设G为非空集合,函数厂:G*G—G称为G 上的一个二元运算,简称为二元运算.二元运算最 基本的特性是封闭性,这是用乘法表来定义一个 集合上的二元运算的基础.例如,表1就是用乘法 表在集合{a,,7,0}上定义的一个二元运算,此 二元运算是否构成群可以通过测试来确定. 表1乘法表 Table1Multiplicationtable *口口y0 口口口y0 卢870& yy口0y 00口口y 1.2乘法表构成群表的充要条件 设G是有限集,用乘法表定义了一个二元运 算,且G有单位元1,则G是群的充要条件为乘 法表具有如下两个性质: ?乘法表的每一行,每一列都含有集合G 的所有元素; ?对G的每一对元素z?1,?1(此处的1 为单位元),在乘法表中任意选取一个1,设R是 以1,z,为顶点的矩形(如图1所示).1与z位 于同一列,1与v位于同一行,则R的第4顶点 收稿日期:2002.07.29 基金项目:国家自然科学基金资助项目(69973011). 作者简介:张大坤(1960一),女,辽宁新民人,东北大学博士研究生,沈阳工业大学副 教授;王光兴(1937一),男,辽宁沈阳人,东北 大学教授,博士生导师. 234东北大学(自然科学版)第24卷 上的元素厂仅依赖于z和,而与l的选择无 关I9]9. ……y… ………,… 图1矩形开示意图 Fig.1RectangleRsketchmap 对于任何一个二元运算的乘法表都可以根据 乘法表具有的两个性质来判别是否构成群表,从 而解决了一个集合上的二元运算是否能构成群的 判断问题. 2测试乘法表是否构成群表的算法 2.1测试乘法表的第一性质的三种算法 乘法表为群表的第一性质是每一行,每一列 都含有G的所有元素.经分析,对测试本性质提 出如下3种算法. ?直接在每行,每列中测试是否存在G中 所有元素算法.从G中取出第一个元素,在二维 乘法表的第一行开始测试是否存在该元素,如不 存在则不符合第一性质,停止测试;否则继续取 G中的第二个元素,重复上面的操作,直至测试 到G中的第个元素;然后,按同样方法逐行,逐 列进行测试. ?按行,按列搜索相同元素算法.由于G中 有个元素,在任何一行和任何一列中都有个 元素,要使每一行,每一列均出现G中所有的元 素,那么在每一行,每一列中不能有相同的元素. 经分析,可以逐行,逐列地进行搜索,在某行或某 列中一旦发现相同元素就说明乘法表不符合第一 性质,停止测试,否则继续搜索. ?元素计数算法.逐行,逐列搜索某行(列)不 相等的元素个数,每发现一个新元素,计数器加l, 到达某行(列)的末尾,检查计数器的值,若小于 说明不符合第一性质,停止测试;否则继续测试. 2.2测试乘法表的第二性质的算法 2.2.1单位元l的搜索算法 对于任意的乘法表单位元l的分布是没有规 律的,只有特殊的乘法表单位元l的分布才是有 规律的,例如,对于Abel群的乘法表单位元1分 布在主对角线上.然而,为了适应一般的乘法表只 能采用逐行(列)搜索单位元l的算法. 2.2.2搜索z,的三种算法 当某个单位元l确定后,就要搜索构成矩形 R(i=l,2,…,一1)的zi(i=l,2,…,一1)和 ,(=l,2,…,一1)两点(如图2所示).由于乘 法表是二维表,二维表中的元素多以抽象的符号 表示且无规律性,使得元素的搜索相对困难.经分 析,可采用以下3种算法. … 1……yj… … Xi……,.… 图2外推法 Fig.2Extrapolationmethod ?自然升序法.当搜索z时,从上至下一一 搜索,跳过单位元l所在的行;搜索时,从左至 右一一搜索,跳过单位元l所在的列. ?外推法.以搜索z为例(如图2所示).以 单位元l为基点(不包括单位元1),按向上,向下 两个方向搜索z,直到找到为止.同理按向左,向 右两个方向搜索. ?小段优先法.此方法是模拟人的智能的一 种方法,在二维乘法表中搜索z(或)时,优先 处理小段,即先判别处于单位元l上(左)方的元 素个数和下(右)方的元素个数,优先在元素个数 少的一段进行搜索. 2.2.3矩形R第4顶点元素特性判别的4种算 法 ?单个矩形移动算法.这是最基本的方法, l,z,对应着矩形R,找到矩形R的第4顶点 元素,然后找到与R等价的第2个矩形及其 第4顶点元素,判别与是否相同,不同, 说明不符合第二性质,停止搜索与判断;否则继续 上面的操作.每次重复操作都找到一个等价的矩 形,故称此算法为单个矩形移动算法. ?按行(列)(一1)个矩形同时移动算法.对 于一个单位元l,使z不动,则与之对应的,( =l,…,一1)有(一1)个,那么就有(一1)个 矩形的第4顶点元素.(志=l,…,一1)与之对 应,记录这(一1)个值.再找到下一个单位元l, 重复上面的操作,又得到了(一1)个(志=l, … ,一1),判别对应的与(志=l,2,…,一 1)是否相等,若存在不相等的元素则不符合第二 性质,停止搜索与判断;否则,继续上面的操作.每 次重复操作都找到(一1)个矩形,故称之为(— 1)个矩形同时移动算法. ?(一1)个矩形同时移动算法.对于一个 单位元l,墨取值有(一1)个,的取值也为( 第3期张大坤等:测试二元运算乘法表是否构成群表的算法设计235 — 1)个,所有可能的矩形为(,z一1)个,对搜索到 的一个单位元1,搜索到所有可能的第4顶点 (=1,2,…,(,z一1)),然后搜索第2个单位元1 及所有可能的第4顶点(k=l,2,…,(一 1)),分别判别与是否相等,若有不相等的 就说明不符合第二性质,停止操作;否则乘法表构 成群表.这种算法对每个单位元只搜索一次,每次 得到(,z一1)个矩形,故称之为(,z一1)个矩形 同时移动算法. ?改进的单个矩形移动算法.在单个矩形移 动算法中,要反复查找单位元1,其中有很多重复 操作,故对此算法进行改进.将第一轮搜索中找到 的,z个单位元1的位置记录下来,在以后的矩形 搜索中不必再去寻找单位元1的位置.算法改进 后使时间复杂度降低. 3算法复杂性分析 算法复杂性分为时间复杂性和空间复杂性, 空间复杂性分析与时间复杂性分析方法相似,且 空间复杂性分析相对简单…j,在此着重分析 2.2.3中关于矩形移动的四种算法的时间复杂 性,仅对空间复杂性作简略分析.算法的时间复杂 性是用时间复杂度来衡量的.在算法分析中基本 的操作有两个,即乘法表中元素的搜索与判别两 元素是否相等. 3.1单个矩形移动算法时间复杂性 此算法中首先要搜索单位元1,最多要进行 ,然后搜索矩形的另外两个顶点z和 ,z次操作 ,,最多都要进行(n—1)次操作,当l,z,,找到 后就得到了矩形尺的第4顶点元素,,用同样方 法找到下一个单位元1及z,时就又得到一个 矩形的第4顶点元素,比较与是否相等, 在二维乘法表中对特定的一个矩形1,,27卜,可以 得到(,z,1)个,比较与厂的操作最多进行 (1l,1)次,上面的过程最多重复(,z一1)次.经 分析总的时间复杂度 丁l(,z)=3n,7n.+4,z+一1.(1) 3.2(几一1)个矩形同时移动算法时间复杂度 由于篇幅所限算法分析从略,此算法时间复 杂度 丁2(,z)=,z一2,z+3,z一1.(2) 3.3(n一1)个矩形同时移动算法时间复杂度 此算法时间复杂度 丁3(,z)=3n0—8,z+9,z一3.(3) 3.4改进的单个矩形移动算法的时间复杂度 此算法是对算法1的改进,减少了对单位元 1的搜索次数.经分析,算法时间复杂度 T4(n)=4n.一11n+10n一3.(4) 经上述对时间复杂度的分析可知,(,z一1) 个矩形同时移动算法的时间复杂度为O(,z),此 算法时间复杂度最低,但占用的内存空间最大,主 要是记录(,z一1)个矩形第4顶点元素;而改进 的单个矩形移动算法,时间复杂度也为0(n0), 虽然略高于(,z一1)个矩形同时移动算法,但只 记录,z个单位元1的位置坐标.用户可根据实际 问题选择不同的算法. 4软件设计 用VisualC++6.0语言实现了上述算法的 软件设计,在软件设计中采用面向对象的程序设 计方法,设计了乘法表输入 模板 个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载 ,首先输入集合 G中的元素个数,z,系统动态形成一个,z×,z的 二维表,用户可以方便地分栏填入二维乘法表的 各个元素,系统设计了各种容错功能,保证输入元 素的正确性.用此软件对多个二元运算乘法表进 行了测试,均得到了正确的结果. 5结论 通过软件运行验证了用计算机测试一个二元 运算的乘法表是否构成群表各种算法的正确性. 实践表明,用计算机测试一个二元运算的乘法表 是否构成群表方便,快捷,准确,具有实用价值. 参考文献: [1]HermannL.S2anmetry[M].Princet,NewJersey:Prince— tonUniversityPress,1980.70—81 [2]MorgeraSD.Fheroleofabstractalgebrainstructurede.sti— mationtheory[J].InformationTheory,IFEETransac. tions,1992,38(3):1053—1065. [3]WilliamJ.Mcx:lernalgebrawithapplication[M].New York:JohnWiley&Sons,1976.51—81. [4]EmestML.Groupthamyandapplications[M].New York:AcademicPrcs.s,1971.199—210. [5]HupperyB,BlackburnN.Finitegroups[M].NewYork: Springer-VerlagBerlinHeidelberg,1982.1—28. [6]Masdkov6z.Characterizationofcut—and—projectsetsusinga binaryoperation[J].LettersMathematicalPhysics, 2000,54(1):1—10. [7]TanH,BalasubramanianK.Aflexiblecorrelationgroup table(CGT)methodfortherelativisticconfigurationinterac tionwavefunctions[J].JournalofMathematical(Zero. istry,2000,28(1):213—239. 8]王绍恒.有限群的结合律的计算机检查法[J].西南师范 大学(自然科学版),2000,25(1):14—17. (WangSH.Chokingbycomputermethodfortheassoeia tirelawoffinitegroups[J].JournalofSouthwestChina NormalUniversity(NaturalScience),2000,25(1):14— 236东北大学(自然科学版)第24卷 17) [9]胡冠章.应用近世代数[M].北京:清华大学出版社, 19994081. (HuGz.Modernalgebrawithapplication[M].Beijing TsinghuaUniversityPre.~s.1999.4081) [10]傅清祥,王晓东.算法与数据结构[M].北京:电子:I:业出 版社.20o0.1—16. (FuQX,WangXD.Algorithma*Mdatastru~t[M].Bei. jing:PublishingHouseOfElectronicsIndustry,2000.1— 16.) AlgorithmicDesignofTestingwithComputerwhethertheMultiplica— tionTableofBinaryOperationFormsGroupTable ZHANG一kun.WANGGuang-xing (Sch(DlofInformationScience&Engineering,NortheasternUniversity,Shenyang11 0004,China.Corresfx)ndent:ZHANG Da.kun.associateprofessor,E.mail:zhangdakun2002@163.COI'I1) Abstract:AncomputeralgorithmwasdevelopedtOexaminewhetherthenmltiplicationtable ofbinaryoperationformsthe grouptable.ThreealgorithmsOf~archingforal1elementsingroupGrowbyrow,.searchingf orsalTleelementsandcounting di~similarelementSlinebylineandrowbyrow,wereraisedintestingthefirstsufficientnecess aryconditionofthegrouptable fbHnedbvmultiplicationtableThreealgorithms,extralmlationmethod,smallsegmentprec edencemethodandnaturalascend' ingorder,weregiventOsearchforelementsinthesalTlelineandrowofrectanglewithunit1int estingthesecondsufficientnee— esk,~rycondition;Fouralgorithms,singlerectanglemoving,simultaneousmovingof(一 1)rectanglelinebyline(column),si? multaneoUsmovingof(一 1)rectanglesandthemovingofimprovedsinglerectangle,wereraisedtOdistinguishthe4thv ertex elenaentcharacteristicoftherectanglebyransackingtheentiretwo-dimensionalmultiplicati ontable;Thecomplexityofmainal— gorithmswasdiscussed.ThealgorithmwasprogrammedwithVisualC十十 6.0..Severalmultiplicationtablesweretestedbythe designedsoftware. Keywords:binaryoperation:multiplicationtable;grouptable;algorithm;computertesting 一(Receiz*.~lJul3,29,2002) :并行流程式生产线调度问题的概率分析求解算法 庞哈利.万珊珊 并行生产线调度问题兼有并行机器和流程车间调度问题的特点,是一类新型的调 度问题.针对工件在各工序具有任 意加工时间的一般并行生产线调度问题,构造了整数规划模型,设计了基于概率分 析的求解算法.对随机生成的测试问 题进行求解的实验结果表明了算法的有效性. WDM网状网中具有业务量疏导能力的共享通路保护算法 何荣希,王光兴 研究了WDM网状网中具有抗毁能力的动态业务量疏导问题,提出一种新的具有 业务量疏导能力的共享通路保护 算法.该算法既可以保证用户业务的可靠性要求,同时又能够有效提高全网的资源 利用率,从而大大降低全网的业务阻 塞率.对所提算法进行了仿真研究,并给出了仿真结果.