軟件進(jìn)程分解方法模式

莊 蕓,李 暉

(1.武漢工程大學(xué)環(huán)境與城市建設(shè)學(xué)院,湖北 武漢 430074;2.武漢大學(xué)計算機(jī)學(xué)院,湖北 武漢 430072)

0 引 言

對軟件體系結(jié)構(gòu)形式化一直都是軟件工程的一個重要的研究和應(yīng)用領(lǐng)域[1-5].本文的目的在于:依據(jù)分解運(yùn)算集合ρθ等效劃分原理,綜合分析原型樹Pri-cTr五個基本結(jié)構(gòu)參量特征和它們之間的關(guān)系,最終綜合它們于一個框架;這個框架形成軟件進(jìn)程模塊[6]M一般的分解模式.

文獻(xiàn)[6]的推論6說明:任何一個軟件進(jìn)程模塊M(θ)(θ∈ASeteq(M)),關(guān)于算子θ的分解運(yùn)算集合ρθ可由一個值區(qū)間VL(O(f))等效劃分.

(1)

組合函數(shù)fi,fj分別對應(yīng)兩個分解運(yùn)算ρi,ρj∈ρθ.VL(O(f))是集合ρθ上所有分解運(yùn)算ρi對應(yīng)組合函數(shù)fi復(fù)雜性值集合.這是一個實數(shù)區(qū)間.如果在區(qū)間有些值z不存在有ρθ的組合函數(shù)的復(fù)雜性值與之相等則記為[Φ]=z.此外,雖然在該區(qū)間有些值很大甚至無窮,但這些值只要有對應(yīng)的組合函數(shù)復(fù)雜性值,則對應(yīng)的等效子集[ρj]就一定存在,[ρj]≠Φ.這個事實,概括為如下的推論.

推論1 任何一個軟件進(jìn)程模塊M(θ)(θ∈ASeteq(M)),

(2)

這個推論的正確性可由軟件工程提供的一組曲線圖說明.這組曲線圖如下:

如圖1所示的組合函數(shù)fj(θ1,θ2,…,θk)對應(yīng)分解運(yùn)算ρj(θ)=(θ1,θ2,…,θk),由組合-分解一致性原則,它的的復(fù)雜性O(shè)(fj)就是算子θ的復(fù)雜性,有下面復(fù)雜性關(guān)系式.

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

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

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

(3)

圖1 軟件進(jìn)程分解模塊數(shù)與復(fù)雜性

由圖1可以看出:

1.隨著模塊數(shù)N的增加,分解運(yùn)算ρj(θ)的最大子算子的復(fù)雜性O(shè)(θi)M逐步下降,而它的組合函數(shù)fj的連接復(fù)雜性O(shè)(fil)卻逐步上升.

2.O(θi)M與O(fil)兩者的反向運(yùn)動,在某些時候它們變化的絕對值可能是相等的,從而保持它們的積O(fj)不變或近似.

上面證明了式(1)的在正確性.對于一個軟件進(jìn)程模塊M(θ)(θ∈ASeteq(M)),它的算子θ的分解運(yùn)算集合[7]ρθ中,不同的分解運(yùn)算ρi,ρj它們對應(yīng)的組合函數(shù)的結(jié)構(gòu)雖然不同,但它們的復(fù)雜性可能相等或近似.值得指出的是:(3)式中的O(θ)是算子θ經(jīng)過fj-ρj(θ)處理后形成的復(fù)雜性.

1 原型樹的復(fù)雜性

組合函數(shù)fj的復(fù)雜性公式(3)的因子O(θi)M是子算子θi的復(fù)雜度,它在ρj(θ)形成的所有子算子中具有最大值,ρj(θ)是fj對應(yīng)的分解運(yùn)算.O(θi)M引導(dǎo)模塊M(θ)的垂直分解傾向.事實上,子算子θi的復(fù)雜性同樣可以表達(dá)成式(3);隨著算子θ的遞歸展開,各個子算子也將逐層同時遞歸展開,但算子θ的最終遞歸深度將取決于子算子θi的抽象程度,也就是該子算子的遞歸深度.抽象化方法是化解軟件模塊復(fù)雜性的最基本的方法,算子的遞歸深度描述了該算子的抽象度.事實上,算子θi的抽象度越高,它要求更多次的遞歸實現(xiàn)抽象分解,則意味著復(fù)雜性越大.這同樣意味著,一個軟件進(jìn)程模塊M(θ)(θ∈ASeteq(M)),對于算子θ的任何一個實際的計算原型Pri-cTr,其遞歸展開表達(dá)式為

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

(4)

?ρj(θ)∈ρθ?ρj(θ)=(θ1,θ2,…,θk)?

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

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

(5)

類似地,算子θi的遞歸展開表達(dá)式為

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

(6)

在這里

t=ti+1

(7)

遞歸深度t∈Ccons={mn,w,t,Cin,Cout}(Ccons稱為Pri-cTr的結(jié)構(gòu)參量),又稱為計算原型Pri-cTr(θ,t)的抽象度,正是按垂直方向逐層化解該模塊的復(fù)雜性的層次數(shù).在此時,子算子θi因為具有最大復(fù)雜度O(θi)M,所以它的遞歸深度值

ti=t-1

(8)

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

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

(9)

這說明:其它子算子θr∈ρθ到達(dá)t層之前或至多到達(dá)t層時遞歸過程結(jié)束.

下面分析原型樹Pri-cTr(θ,t)各個層次[8]的復(fù)雜性.

原型樹Pri-cTr(θ,t)的寬度w∈Ccons說明:在Pri-cTr(θ,t)中各層能夠達(dá)到的最大節(jié)點數(shù).由于原型樹Pri-cTr(θ,t)的特殊結(jié)構(gòu),每層的節(jié)點θj,或為原子節(jié)點,或為也引導(dǎo)一棵子原型樹Pri-cTrj(θj,tj)的復(fù)合節(jié)點,如式(6)所示. 該層的所有子節(jié)點有它們自身的復(fù)雜性,它們在該層的連接復(fù)雜性;還有在它們自身復(fù)雜性中存在有最大復(fù)雜性.一般來說,各層節(jié)點通過上輩的多個子計算原型樹分成若干子集橫向分布于這一層.因此,此層的連接復(fù)雜性將會大大降低.如在Pri-cTr(θ,t)的i層,它的寬度記為wi≤w,則上輩的各個子Pri-cTrj(θj,tj)通過i層時的寬度記為wij,于是wi被分解成若干(如k)個子集,并且有,

wi=∑j=1kwij

(10)

此時,Pri-cTr(θ,t)在i層的連接復(fù)雜性有下面的關(guān)系表達(dá)式,

(11)

其中O(fil)是對應(yīng)wij的連接復(fù)雜性.顯然,下面的表達(dá)式是正確的,

O(fil)=O(fijl)M

(12)

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

(13)

關(guān)于原型樹Pri-cTr,它的任意層的復(fù)雜性公式以一個推論表述如下.

推論2 一個軟件進(jìn)程模塊M(θ)(θ∈ASeteq(M)),對于算子θ的任何一個實際計算原型Pri-cTr(θ,t),它的任意層的復(fù)雜性公式為

(14)

式(14)中，wi是第i層的寬度,k表示通過該層的子原型樹數(shù),t∈Ccons為Pri-cTr(θ,t)的深度,w∈Ccons為它的寬度.

首先,推論2說明:Pri-cTr(θ,t)在任意層的連接復(fù)雜性為O(fijl)M只取決于該層某個最大的子集,也就是該子集上輩節(jié)點的扇出值.其次,Pri-cTr(θ,t)的參量w∈Ccons及其相關(guān)推論2表達(dá)了模塊M(θ)(θ∈ASeteq(M))橫向(水平)抽象分解,參量t∈Ccons則表達(dá)了它的縱向(垂直)抽象分解.該模塊最終分解的模塊數(shù)(Pri-cTr(θ,t)的節(jié)點數(shù))mn∈Ccons則取決于t和w兩個參量綜合作用的結(jié)果.

2 軟件進(jìn)程的分解模式

對于軟件進(jìn)程模塊M(θ)(θ∈ASeteq(M)),它的任意一個計算原型樹Pri-cTr(θ,t)的生成過程說明:在分解運(yùn)算的連續(xù)遞歸作用下,這個計算原型按水平和垂直兩個方向逐層展開.同時根據(jù)上面對Pri-cTr(θ,t)的結(jié)構(gòu)參量Ccons的基本分析,它的兩個因子w,t∈Ccons在這個遞歸展開過程中有著重要的作用和意義.這兩個因子參量正好刻畫了計算原型按水平和垂直兩個方向的深度和寬度.它們的適當(dāng)?shù)剡x取有可能構(gòu)成一個等效的面積,指導(dǎo)著該過程有效地展開.這個面積適當(dāng)?shù)淖兓?長與寬相對變化,保持面積大小不變,),盡管該面積里包含的模塊數(shù)mn可能有變化,但保持它們對應(yīng)的計算原型樹Pri-cTr(θ,t)的復(fù)雜性不變.這就使得這兩個因子形成的矩形,形同一個框架,這個框架把Ccons的四個因子mn,w,t,和Cout有機(jī)地聯(lián)系在一起.同時,由于Pri-cTr(θ,t)是樹結(jié)構(gòu),它的扇入值是一個常量,Cin=1.所以這個框架實際上綜合引導(dǎo)Pri-cTr(θ,t)遞歸展開過程:在確定復(fù)雜性要求時,在一個確定的矩形面積里,指導(dǎo)M(θ)軟件實體分解遞歸過程[9].這個模式也就稱為矩陣分解模式,下面給這個模式正式定義.

定義1對于一個可求解問題P,它的軟件進(jìn)程模塊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的根節(jié)點,D是它的節(jié)點集,E節(jié)點之間連接邊集；

2) 參量w稱為計算原型Pri-cTr(θ,t)的寬度,是該原型中最寬層的節(jié)點數(shù)；

3)Ccons稱為計算原型Pri-cTr(θ,t)的結(jié)構(gòu)參量,mn是節(jié)點(模塊)數(shù),即

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

(17)

4)Cin,Cout分別是計算原型Pri-cTr(θ,t)扇入和扇出值,并規(guī)定原型中任何一個節(jié)點的扇入和扇出值分別不超過Cin,Cout.

矩陣分解模式A的意義在于把軟件進(jìn)程模塊M(θ)(θ∈ASeteq(M))的分解函數(shù)與它的計算原型Pri-cTr(θ,t)的結(jié)構(gòu)參量融合為一體,確立了M(θ)進(jìn)行理論分析和分解運(yùn)算的制約條件;通過矩陣A參量的調(diào)整,引導(dǎo)遞歸分解過程優(yōu)化運(yùn)行并取得最佳的分解效果,即生成優(yōu)化的計算原型Pri-cTr(θ,t).

3 結(jié) 語

以上建立了對軟件進(jìn)程模塊M的一種規(guī)范化的分解方法,這種方法視為分解M的一種方法模式——矩陣模式,表示為A=[w，t].本文說明了A形成的基因及其某些特征.這個模式把M的遞歸過程的理論分析和實際展開結(jié)合于一體,為它的遞歸展開過程形成有效的條件,生成M的優(yōu)化的計算原型Pri-cTr.

在A的基礎(chǔ)上,將繼續(xù)深入分析了軟件進(jìn)程模塊M分解運(yùn)算及其生成的計算原型集合的若干重要性質(zhì).如:1計算原型的復(fù)雜性;2等面積計算原型子族;3計算原型集合Set-Pri-cTr(M)生成表達(dá)式和它的等效劃分理論;4等面積計算原型子族ArPrTset[w,t].

軟件分解歷來是軟件學(xué)界關(guān)心的問題,本文的工作主要是希望用數(shù)學(xué)語義來描述軟件的開發(fā)過程,揭示其內(nèi)在的規(guī)律,使軟件的開發(fā)不再是一種經(jīng)驗和試探,而是在一種規(guī)則和模式的指導(dǎo)下開發(fā)出精確而有效的系統(tǒng),當(dāng)然這需要很大量研究和探索工作,還有不少問題等待進(jìn)一步分析與研究.

參考文獻(xiàn)：

[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ìn)[J].武漢工程大學(xué)學(xué)報,2010,32(7):89-93.

[4]田?？?胡榮強(qiáng).可變時延網(wǎng)絡(luò)控制系統(tǒng)的建模和穩(wěn)定性分析[J].武漢工程大學(xué)學(xué)報,2010,32(7):94-98.

[5]趙會群，王國仁，高運(yùn).軟件體系結(jié)構(gòu)抽象模型[J].軟件學(xué)報，2002，25(7)：730-736.

[6]李暉,莊蕓.軟件體系結(jié)構(gòu)的數(shù)學(xué)論域[J].武漢大學(xué)學(xué)報:工學(xué)版,2003,36(4):107-110.

[7]莊蕓,李暉.軟件體系結(jié)構(gòu)的數(shù)學(xué)描述[J].計算機(jī)應(yīng)用研究,2005,22(2):492-493.

[8]李暉,莊蕓.軟件體系結(jié)構(gòu)層次模型[J].計算機(jī)應(yīng)用研究,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.