软件进程分解方法模式

庄 芸,李 晖

(1.武汉工程大学环境与城市建设学院,湖北 武汉 430074;2.武汉大学计算机学院,湖北 武汉 430072)

0 引 言

对软件体系结构形式化一直都是软件工程的一个重要的研究和应用领域[1-5].本文的目的在于:依据分解运算集合ρθ等效划分原理,综合分析原型树Pri-cTr五个基本结构参量特征和它们之间的关系,最终综合它们于一个框架;这个框架形成软件进程模块[6]M一般的分解模式.

文献[6]的推论6说明:任何一个软件进程模块M(θ)(θ∈ASeteq(M)),关于算子θ的分解运算集合ρθ可由一个值区间VL(O(f))等效划分.

(1)

组合函数fi,fj分别对应两个分解运算ρi,ρj∈ρθ.VL(O(f))是集合ρθ上所有分解运算ρi对应组合函数fi复杂性值集合.这是一个实数区间.如果在区间有些值z不存在有ρθ的组合函数的复杂性值与之相等则记为[Φ]=z.此外,虽然在该区间有些值很大甚至无穷,但这些值只要有对应的组合函数复杂性值,则对应的等效子集[ρj]就一定存在,[ρj]≠Φ.这个事实,概括为如下的推论.

推论1 任何一个软件进程模块M(θ)(θ∈ASeteq(M)),

(2)

这个推论的正确性可由软件工程提供的一组曲线图说明.这组曲线图如下:

如图1所示的组合函数fj(θ1,θ2,…,θk)对应分解运算ρj(θ)=(θ1,θ2,…,θk),由组合-分解一致性原则,它的的复杂性O(fj)就是算子θ的复杂性,有下面复杂性关系式.

O(fj(θ1,θ2,…,θk))=O(θ)

O(fj)=O(θi)M×O(fjl)

O(θi)M=MaxO(θi){1≤i≤k}

(3)

图1 软件进程分解模块数与复杂性

由图1可以看出:

1.随着模块数N的增加,分解运算ρj(θ)的最大子算子的复杂性O(θi)M逐步下降,而它的组合函数fj的连接复杂性O(fil)却逐步上升.

2.O(θi)M与O(fil)两者的反向运动,在某些时候它们变化的绝对值可能是相等的,从而保持它们的积O(fj)不变或近似.

上面证明了式(1)的在正确性.对于一个软件进程模块M(θ)(θ∈ASeteq(M)),它的算子θ的分解运算集合[7]ρθ中,不同的分解运算ρi,ρj它们对应的组合函数的结构虽然不同,但它们的复杂性可能相等或近似.值得指出的是:(3)式中的O(θ)是算子θ经过fj-ρj(θ)处理后形成的复杂性.

1 原型树的复杂性

组合函数fj的复杂性公式(3)的因子O(θi)M是子算子θi的复杂度,它在ρj(θ)形成的所有子算子中具有最大值,ρj(θ)是fj对应的分解运算.O(θi)M引导模块M(θ)的垂直分解倾向.事实上,子算子θi的复杂性同样可以表达成式(3);随着算子θ的递归展开,各个子算子也将逐层同时递归展开,但算子θ的最终递归深度将取决于子算子θi的抽象程度,也就是该子算子的递归深度.抽象化方法是化解软件模块复杂性的最基本的方法,算子的递归深度描述了该算子的抽象度.事实上,算子θi的抽象度越高,它要求更多次的递归实现抽象分解,则意味着复杂性越大.这同样意味着,一个软件进程模块M(θ)(θ∈ASeteq(M)),对于算子θ的任何一个实际的计算原型Pri-cTr,其递归展开表达式为

ρt(θ)=Pri-cTr(θ,t)

(4)

∀ρj(θ)∈ρθ∃ρj(θ)=(θ1,θ2,…,θk)⟹

∃O(θi)M[θi∈ρj(θ)]=

MaxO(θi){1≤i≤k}

(5)

类似地,算子θi的递归展开表达式为

ρti(θi)=Pri-cTr(θi,ti)

(6)

在这里

t=ti+1

(7)

递归深度t∈Ccons={mn,w,t,Cin,Cout}(Ccons称为Pri-cTr的结构参量),又称为计算原型Pri-cTr(θ,t)的抽象度,正是按垂直方向逐层化解该模块的复杂性的层次数.在此时,子算子θi因为具有最大复杂度O(θi)M,所以它的递归深度值

ti=t-1

(8)

ρj(θ)形成的其它子算子的递归深度值,一般有

∀θr∈ρθ(r≠i)⟹tr≤t-1

(9)

这说明:其它子算子θr∈ρθ到达t层之前或至多到达t层时递归过程结束.

下面分析原型树Pri-cTr(θ,t)各个层次[8]的复杂性.

原型树Pri-cTr(θ,t)的宽度w∈Ccons说明:在Pri-cTr(θ,t)中各层能够达到的最大节点数.由于原型树Pri-cTr(θ,t)的特殊结构,每层的节点θj,或为原子节点,或为也引导一棵子原型树Pri-cTrj(θj,tj)的复合节点,如式(6)所示. 该层的所有子节点有它们自身的复杂性,它们在该层的连接复杂性;还有在它们自身复杂性中存在有最大复杂性.一般来说,各层节点通过上辈的多个子计算原型树分成若干子集横向分布于这一层.因此,此层的连接复杂性将会大大降低.如在Pri-cTr(θ,t)的i层,它的宽度记为wi≤w,则上辈的各个子Pri-cTrj(θj,tj)通过i层时的宽度记为wij,于是wi被分解成若干(如k)个子集,并且有,

wi=∑j=1kwij

(10)

此时,Pri-cTr(θ,t)在i层的连接复杂性有下面的关系表达式,

(11)

其中O(fil)是对应wij的连接复杂性.显然,下面的表达式是正确的,

O(fil)=O(fijl)M

(12)

O(fijl)M=MaxO(fijl){1≤j≥k}

(13)

关于原型树Pri-cTr,它的任意层的复杂性公式以一个推论表述如下.

推论2 一个软件进程模块M(θ)(θ∈ASeteq(M)),对于算子θ的任何一个实际计算原型Pri-cTr(θ,t),它的任意层的复杂性公式为

(14)

式(14)中，wi是第i层的宽度,k表示通过该层的子原型树数,t∈Ccons为Pri-cTr(θ,t)的深度,w∈Ccons为它的宽度.

首先,推论2说明:Pri-cTr(θ,t)在任意层的连接复杂性为O(fijl)M只取决于该层某个最大的子集,也就是该子集上辈节点的扇出值.其次,Pri-cTr(θ,t)的参量w∈Ccons及其相关推论2表达了模块M(θ)(θ∈ASeteq(M))横向(水平)抽象分解,参量t∈Ccons则表达了它的纵向(垂直)抽象分解.该模块最终分解的模块数(Pri-cTr(θ,t)的节点数)mn∈Ccons则取决于t和w两个参量综合作用的结果.

2 软件进程的分解模式

对于软件进程模块M(θ)(θ∈ASeteq(M)),它的任意一个计算原型树Pri-cTr(θ,t)的生成过程说明:在分解运算的连续递归作用下,这个计算原型按水平和垂直两个方向逐层展开.同时根据上面对Pri-cTr(θ,t)的结构参量Ccons的基本分析,它的两个因子w,t∈Ccons在这个递归展开过程中有着重要的作用和意义.这两个因子参量正好刻画了计算原型按水平和垂直两个方向的深度和宽度.它们的适当地选取有可能构成一个等效的面积,指导着该过程有效地展开.这个面积适当的变化(长与宽相对变化,保持面积大小不变,),尽管该面积里包含的模块数mn可能有变化,但保持它们对应的计算原型树Pri-cTr(θ,t)的复杂性不变.这就使得这两个因子形成的矩形,形同一个框架,这个框架把Ccons的四个因子mn,w,t,和Cout有机地联系在一起.同时,由于Pri-cTr(θ,t)是树结构,它的扇入值是一个常量,Cin=1.所以这个框架实际上综合引导Pri-cTr(θ,t)递归展开过程:在确定复杂性要求时,在一个确定的矩形面积里,指导M(θ)软件实体分解递归过程[9].这个模式也就称为矩阵分解模式,下面给这个模式正式定义.

定义1对于一个可求解问题P,它的软件进程模块M(θ)(θ∈ASeteq(M))的矩阵分解模式记为A.

A=[w，t]w,t∈Ccons=

{mn,w,t,Cin,Cout}

(15)

其中：

1) 参量t称为计算原型Pri-cTr(θ,t)的(递归)深度, 满足条件,

ρt(θ)=Pri-cTr(θ,t)=Tree(θ,D,E)

(16)

θ是树Tree的根节点,D是它的节点集,E节点之间连接边集；

2) 参量w称为计算原型Pri-cTr(θ,t)的宽度,是该原型中最宽层的节点数；

3)Ccons称为计算原型Pri-cTr(θ,t)的结构参量,mn是节点(模块)数,即

mn=|D|,D⊂Pri-cTr(θ,t)

(17)

4)Cin,Cout分别是计算原型Pri-cTr(θ,t)扇入和扇出值,并规定原型中任何一个节点的扇入和扇出值分别不超过Cin,Cout.

矩阵分解模式A的意义在于把软件进程模块M(θ)(θ∈ASeteq(M))的分解函数与它的计算原型Pri-cTr(θ,t)的结构参量融合为一体,确立了M(θ)进行理论分析和分解运算的制约条件;通过矩阵A参量的调整,引导递归分解过程优化运行并取得最佳的分解效果,即生成优化的计算原型Pri-cTr(θ,t).

3 结 语

以上建立了对软件进程模块M的一种规范化的分解方法,这种方法视为分解M的一种方法模式——矩阵模式,表示为A=[w，t].本文说明了A形成的基因及其某些特征.这个模式把M的递归过程的理论分析和实际展开结合于一体,为它的递归展开过程形成有效的条件,生成M的优化的计算原型Pri-cTr.

在A的基础上,将继续深入分析了软件进程模块M分解运算及其生成的计算原型集合的若干重要性质.如:1计算原型的复杂性;2等面积计算原型子族;3计算原型集合Set-Pri-cTr(M)生成表达式和它的等效划分理论;4等面积计算原型子族ArPrTset[w,t].

软件分解历来是软件学界关心的问题,本文的工作主要是希望用数学语义来描述软件的开发过程,揭示其内在的规律,使软件的开发不再是一种经验和试探,而是在一种规则和模式的指导下开发出精确而有效的系统,当然这需要很大量研究和探索工作,还有不少问题等待进一步分析与研究.

参考文献：

[1]Lau Kung-Kiu,Wang Zheng.Software component models[J].IEEE Transactions on Software Engineering,2007,33(10):37-45.

[2]Broy M.Taward a mathematical foundation of software engineering methods[J].IEEE Transactions On Software Engineering,2001,12(3):21-57.

[3]王忠,王春丽,刘莉.基于SVM的多类分类算法改进[J].武汉工程大学学报,2010,32(7):89-93.

[4]田裕康,胡荣强.可变时延网络控制系统的建模和稳定性分析[J].武汉工程大学学报,2010,32(7):94-98.

[5]赵会群，王国仁，高运.软件体系结构抽象模型[J].软件学报，2002，25(7)：730-736.

[6]李晖,庄芸.软件体系结构的数学论域[J].武汉大学学报:工学版,2003,36(4):107-110.

[7]庄芸,李晖.软件体系结构的数学描述[J].计算机应用研究,2005,22(2):492-493.

[8]李晖,庄芸.软件体系结构层次模型[J].计算机应用研究,2003,2(4):181-182.

[9]Li hui, Chen shihong. Recursive Decomposition of Softwate Process[J].Wuhan University Journal of Natural Sciences,2009,2(14):143-147.