資源描述：
《覆蓋陣列can(t，k，v)上界推導》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。
1、覆蓋陣列CAN(t,k,v)上界的推導 摘要 軟件測試方面的局限性已經(jīng)嚴重阻礙了元件化軟件產(chǎn)品的發(fā)展。我們希望能夠?qū)⑺械臏y試情況很好地構建出來，通過數(shù)學方法做到盡可能多地測試元件之間的相互關系并節(jié)省時間和財力。覆蓋陣列CA(N;t,k,v)是一個N×k的矩陣，使得每一個N×t的子矩陣至少包含v個元素中的t個，其中t是矩陣的強度。N×t的子矩陣代表元件之間相互關系集合的子集合。為了進行軟件測試，我們主要通過以下兩種方法來構建覆蓋陣列：一、通過改進的代數(shù)和組合構造，產(chǎn)生更小的覆蓋陣列；二、通過設計一種效率更高的搜索算法，構造更小的覆蓋陣列。Stei
2、n和Lovász首次在[1]和[2]中使用Stein-Lovász定理，即貪心算法，來研究一些組合覆蓋問題。GérardCohen、SimonLitsyn和GillesZémor在[2]中用這一定理解決了一些編碼的問題。Stein-Lovász定理可以用來進行組合設計中的一些存在性證明，它比概率方法具有更好的可構造性。本文主要通過列舉一些例子來詳細說明構造覆蓋陣列的過程，并提供覆蓋陣列的一個新上界。關鍵詞：覆蓋陣列、貪心算法、軟件測試 IDerivationofUpperBoundofCoveringArrayNumberCAN(t,k,v)ABS
3、TRACTAcoveringarrayCA(N;t,k,v)isanN×karraysuchthateveryN×tsub-arraycontainsallt-tuplesfromvsymbolsatleastonce,wheretisthestrengthofthearray.Oneapplicationoftheseobjectsistogeneratesoftwaretestsuitestocoverallt-setsofcomponentinteractions.Methodsforconstructionofcoveringarraysf
4、orsoftwaretestinghavefocusedontwomainareas.Thefirstisfindingalgorithmstofindsmallercoveringarraysmorequickly.Thesecondisrefiningcomputationalsearchalgorithmstofindsmallercoveringarraysmorequickly.Inthispaper,weexaminesomenewcut-pastetechniquesforstrengththebasemethod,thisisaug
5、mentedannealing.Thismethodleveragesthecomputationalefficiencyandoptimalityofsizeobtainedthroughcombinatorialconstructionswhilebenefitingfromthegeneralityofaheuristicsearch.Wepresentafewexamplesofspecificconstructionsandprovidenewboundsforsomestrengththreecoveringarrays.Compone
6、nt-basedsoftwaredevelopmentposesmanychallengesforthesoftwaretester.Interactionsamongcomponentsareoftencomplexandabundant.Componentsmaynotbedesignedwiththefinalproductinmindwhichleavesthempronetounexpectedinteractionfaults.Ideallywewanttotestallpossibleinteractions,butthisisusu
7、allyinfeasibleeithertime-wiseorcost-wise.Weare,therefore,interestedingeneratingtestsuitethatprovidecoverageofasmanyinteractionsaspossible.Keywords:Coveringarrays,softwaretest,Stein-LovászTheoremII上海交通大學學位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的學位論文，是本人在導師的指導下，獨立進行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他
8、個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。本人完全意識到本聲明
