Return to search

Pasiekiamų būsenų grafo sudarymo sudėtingumo tyrimas / Complexity analysis of reachable state graph creation

Darbe nagrinėjamas realiojo laiko sistemų, specifikuotų agregatiniu metodu, verifikavimo uždavinys. Sprendžiant šį uždavinį, naudojama pasiekiamų būsenų grafo sudarymo metodika, leidžianti įvertinti laiko intervalus, kuriais įvyksta sistemoje apibrėžti įvykiai. Darbe nagrinėjami pasiekiamų būsenų grafo sudarymo algoritmai ir pateikta prototipinėse programose naudojama duomenų struktūra. Suformuluoti ir įrodyti teiginiai apie pasiekiamų būsenų grafo sudarymo algoritmo sudėtingumą (maksimalaus vienos būsenos galimų perėjimų skaičiaus; grafo viršūnių skaičiaus augimo priklausomybės nuo įvykių skaičiaus; maksimalaus įvykių skaičiaus elgsenoje laiko intervale; maksimalaus viršūnių skaičiaus laiko intervale.) Pateikta trijų testinių sistemų grafų automatizuoto sudarymo analizė. Parodyta, kad Simplekso optimizavimo procedūra laiko momentų palyginimui gali būti naudojama tik atskirais atvejais. / The work deals with a verification task of real time system specified by aggregate method. While solving the task, a technique for creation a reachable state graph is used. The technique permits to evaluate intervals of time when the defined system events occur. Reachable state graph creation algorithms are analysed in the work. A data structure used in prototype software is presented in the work too. Assertions about a complexity of algorithm for reachable state graph creation are formulated and proved. These assertions concern maximum number of transitions from single state, dependency of number of graph verteles growth on a number of events, maximum number of events in a behaviour during time interval, and maximum number of vertexes during time interval. Analysis of automated creation of graphs for three test systems is presented. It is shown that Simplex optimisation procedure for comparison of time intervals can be used only in certain cases.

Identiferoai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2008~D_20080811_154652-52373
Date11 August 2008
CreatorsAmbrazas, Nerijus
ContributorsTelksnys, Laimutis, Maciulevičius, Stasys, Barauskas, Rimantas, Jasinevičius, Raimundas, Mockus, Jonas, Plėštys, Rimantas, Pranevičius, Henrikas, Makackas, Dalius, Valakevičius, Eimutis, Kaunas University of Technology
PublisherLithuanian Academic Libraries Network (LABT), Kaunas University of Technology
Source SetsLithuanian ETD submission system
LanguageLithuanian
Detected LanguageUnknown
TypeMaster thesis
Formatapplication/pdf
Sourcehttp://vddb.library.lt/obj/LT-eLABa-0001:E.02~2008~D_20080811_154652-52373
RightsUnrestricted

Page generated in 0.002 seconds