论文总字数：26564字

目 录

第一章 覆盖阵列的背景介绍 4

1.1背景简介 4

1.2数学概念 4

1.3国内外的研究现状及结果 5

1.3.1 研究现状 5

1.3.2 一些覆盖阵列的界 6

1.4 本文结构 8

第二章 cover starters法构造覆盖阵列 9

2.1 本章内容介绍 9

2.2 cover starters构造覆盖阵列的原理 9

2.3 基于图的因子分解的Starter Arrays 11

2.4 作用于Starter arrays的群(group) 13

第三章 用cover starter构造覆盖阵列的具体实现 15

3.1 cover starter方法构造覆盖阵列的基本流程 15

3.2构造一个 16

第四章 总结 18

4.1 问题与展望 18

参考文献 19

致谢 20

t=3的覆盖阵列的cover starters法构造

刘钦臣

, China

Abstract: A covering array is an Nk array with entries from a set of symbols such that in any sub-array, each -tuple occurs at least λ times. Then is called the size of the covering array, is called the strength of the coverage of interactions, is the number of components (degree), and is the number of symbols for each component (order). When “at least” is replaced by “exactly”, the covering array is defined as an orthogonal array denoted by . The minimum size for which a exists is called the covering array number and written as . When, then the covering array is optimal.

Covering arrays have been extensively studied for their applications to software testing, hardware testing, drug screening, statistics, networks and computer science. A great number of research results have achieved in covering arrays for the case “”, while the question becomes more complex for the case “” and there are not too much research findings, therefore they currently receive more and more attention.

In this paper, we mainly study covering arrays of strength three using the method of cover starters. We use a “starter array” and a group which act on the starter array to construct a covering array. The specific approach is that we can get factor graphs by the one-factorization of the complete graph G when . Then we use these factor graphs to construct a starter array M, next we let a group G act on M, and we get , therefore is a where is a prime power.

Keywords: covering array; orthogonal array; starter array; group

第一章 覆盖阵列的背景介绍

1.1背景简介

覆盖阵列在组合设计理论和试验设计理论中均有研究，它是在研究统计实验设计中那些强度比较小的实验因子之间的交互情况下被引入的. 而随着互联网的发展，软硬件的开发有了很大的进步，而其开发过程中，组件之间的交互测试是很重要的环节，甚至关乎软硬件开发的成败，近些年来，在组件基础上的软件开发成为软件复用理论实用化的热门，基于此种模型，开发者能够重复使用已有的构件，即能够“即插即用”，可以比较迅速的构造出应用软件，这样的话在时间，费用以及工作效率上都有了很大的提升，更关键是能够开发出愈加规范可靠的软件. 但在软件测试中，由于各个组件之间的一些无法预料的交互错误或故障，而这些交互故障又是十分复杂而且数量庞大的，要检测出这些故障，对测试者来说，最理想的就是测试组件间所有的交互作用，但这种情况下要耗费大量的时间和费用. 如软件含有个组件，每个组件有种不同的作用，若把所有的交互作用全都测试一遍，则需要次测试，当或非常大时，是非常大的，所以这种方法是不可取的. 故应当找到若干测试集，而在这些测试集中所有的交互作用都必须出现，如此一来就会节省大量的时间和费用，而覆盖阵列就能解决上述问题.

例如在软件测试中一个软件有4个组件， 每个组件有2种不同的作用如下表所示：

如果把所有可能的结果都检测一遍的话，则需要=16次测试，而用覆盖阵列检测的话，则是一个, 则我们最多用5次实验就能够包括这4个组件的所有2-因子交互作用. 如下表所示：

这样的话既能保证所有-因子交互作用都能被覆盖，又可以大幅度地减少测试次数，这正是我们想所达到的目标.

这样的交互模型不仅在软硬件测试方面、在统计、药物筛选、农业生产、网络、电路等方面也有应用，而覆盖阵列就是用来满足这样的交互覆盖类型问题的主要的组合对象，正是由于其广泛的应用价值，近年来覆盖阵列已得到国内外数学界和计算机学者的共同研究.

1.2数学概念

定义1 ：一个覆盖阵列是一个定义在元集上的阵列，使得它的任意一个子阵包含在上的任意一个-元组至少次，其中称为大小，为相互作用覆盖的强度，是因子数，是每个因素的水平数，为指标.

当时，通常简记为，若给定一组，使存在的最小的正整数称为覆盖数，简记为, 如果覆盖阵列的，则称该覆盖阵列为最优.

当修改上述定义1中的“至少”为“恰好”就得到正交阵列的定义，而且可以得到，当时，通常简记为.

由定义可得,,故我们一般设，，且有.

1.3国内外的研究现状及结果

1.3.1 研究现状

近些年来，在覆盖阵列的研究上主要集中在下面两个方面：一方面是对覆盖阵列的渐进存在性的研究，另一方面是对于一组确定的，找到一个尽可能小的. 本文主要研究在时，对于给定的，使尽可能的小.

在渐进存在性上的研究，当Godbole，Skipper和Sunley[1]等人在V元集上随机地选择阵列，他们发现：对于给定的一组, 当足够大时，得到的随机阵列是的概率不为零，于是他们得到：

而在文章[2,3]中给出了，在文献[3]中证明了的渐进值为.

在而覆盖阵列界的研究上，则是一个较艰难的组合问题，当越来越大时，构造最优的覆盖阵列就越困难，事实上，只有当时，R完全确定了了的界. 相比较之下，关于的覆盖阵列数的研究就比较少，随着对覆盖阵列的研究. 对于的覆盖阵列数可参见[4,5,6,7]，关于强度大于3的覆盖阵列数可参见[5,8,9]，下面给出强度为2和3 一些已知的覆盖阵列的最小行数：

对于其他给定的的的值可参见Colbourn的覆盖阵列表[10].

对于覆盖阵列的构造方法，到目前为止有多种实现方法，包括正交阵列法，Roux型构作[5,6]，完美hash函数法等等. 正交表在覆盖阵列中有很重要的应用，显而易见一个一个最优的覆盖阵列,可以将研究正交阵列的方法推广到覆盖阵列的研究上.

剩余内容已隐藏，请支付后下载全文，论文总字数：26564字