Nagrinėjami atsitiktiniai sankirtų grafai G(n,m,p)jų viršūnių laipsnių skirstinius. Įrodyta, kad grafo viršūnės laipsnis turi Binominį pasiskirstymą. Rasta išraiška tikimybės p, kad dvi grafo viršūnės renkasi bendrą objektą. / Random intersection graphs audits vertex degree distributions are viewed. Its proved, vertex degree has Binomial distribution. Probability p that two vertex of graph chooses common object is find.

Sparčiai plintant informacinėms technologijoms vis daugiau daiktų ir paslaugų yra perkeliama į virtualią erdvę. Šis darbas nagrinėja galimybę padaryti universaliu rezervacijos procesą. Pagrindinis tikslas sukurti paprastą sistemą, kurią skirtingoms situacijoms galėtų susikonfigūruoti pats vartotojas. Viena iš sudėtingiausių funkcijų kurią nagrinėja darbas yra galimybė sistemai generuoti automatinius tvarkaraščius. Sistemos praktiškumo būtinybė reikalavo gana plataus analizės spektro: sistemos įgyvendinimo principo tyrimo, programinės įrangos parinkimo, rezervavimo algoritmo sukūrimo, tvarkaraščių sudarymo algoritmo išvedimo. Galutinis rezultatas yra ištirti ir aprašyti konfigūravimo, administravimo bei rezervavimo procesai, jų tyrimų metodai ir gauti rezultatai. / With rapid spread of information technologies, more and more things and services are transferred to the virtual space. Online stores or online reservation systems has long ceased to surprise customers. The main purpose of this master thesis is to analyze and find the way to universalize online reservation process using information gathered from scientific literature analysis and from author’s research. The main objective is to create a model of a simple system for the different situations that could be configured by administrator. Since most of internet users have great computer skills and new IT technologies are becoming more sophisticated and easier to use, most of processes could be performed by ordinary user with no IT education with use of simplified tools. One of the most complex parts of this thesis is to examine the possibility of the system to generate automated schedules. Usability of the system called for the need of a relatively broad spectrum of analysis: the research of various ways of implementation of system, software selection, the creation of a reservation algorithm, scheduling algorithm modification and analysis. In my work I analyze theoretical fundamentals needed for creation of sophisticated reservation system. I review installation and configuration, reservation, object creation and other processes. Also I examine real situations and possible their implementation. The final result of my thesis is detailed information about preferred implementation way... [to full text]

Die Graphenwissennschaft vervendet man bei praktischem Bedarf in mehreren Gebieten der Wissenschaft (zum Beispiel: in der Chemie, in der Biologie, in der in der Psychologie, in der Informatik). Die Graphen vereinfachen viele kompliezierte Schemen, Probleme. Die Graphentheorie wird in der Schulmathematik bei der Kombinationslehre (die Baumgraphe, doppel Graph) benutzt. In der Diplomarbeit werden wichtige Arte und Eigenschaften der Gfaph verallgemeinert. Es wurde bewiesen: 1. Jeder vollständige Graph besitzt Verbindungen und der Graph ist gleichmäβig mit dem Grad r=p-1. 2. Jedem (p,q)-Graph und beliebigem v gehört der Menge V regelgerechte Ungleichheit 0≤deg v ≤p-1. 3. Wenn p≠8, dann G – kanten Graph Kp dann: 1) G hat Scheitel; 2) G – regelgerecht Graph mit Grad 2(p-2). 4. Jeden Naturzahlen m,n und vollständigem doppel Graph Km,n ist solche Gleichheit Km,n = regelgerecht. 5. Wenn m≠4 und n≠4, dann ist vollständiger doppel Graph Km,n kanten Graph L(Km,n): 1) hat Scheitel; 2) ist regelgerecht Graph mit Grad r=m+n-2.

The software currently used by SDH net operators does not guarantee the automatic generation of routes between the selected nodes. This is the reason why the operators spend a lot of time on designing the nets manually. Despite all the time spent on designing, errors are still made which are the causes of net overload and connection disorders. It is necessary to convert the measuring units of SDH resources from a tree type structure to real numbers, because the structure of the analyzed object’s resource units is hierarchical. After evaluation of these units the solution of this problem can be found in theory of graphs. It is natural that given these data structures a special method is needed which would allow determining these structures and finding specific weight unit of edges of the graphs with which the problem is solved. The complexity of graph route composition algorithms is not satisfactory because the scope of real systems will be big enough. The amount of net nodes can exceed 500 and the amount of lines connecting them can be more than 5000. It is not very difficult to implement the automatic generation of routes in principle. The knowledge of graph theory can be used to do that. But in solving real problems with the best known methods of graph theory the time of solution is not acceptable because of the big scope of the problem. It is possible to reduce the time of solution by increasing the efficiency of the system that solves the problem. The need for more... [to full text]

Šiame darbe apžvelgti dalelių spiečių algoritmai ir jų taikymai, išanalizuotas dirbtinės bičių kolonijos (ABC) algoritmas. Sukurta programinė ABC algoritmo realizacija, skirta optimizuoti žaidimo „Path of Exile“ veikėjo pasyvių įgūdžių grafui. Šio uždavinio sprendimui buvo panaudotas dirbtinės bičių kolonijos algoritmas su „godžiąja“ euristika. Atliktas programos testavimas, rezultatų palyginimas su žmonių sukurtais pasyvių įgūdžių grafais, padarytos išvados. / In this work an overview of particle swarm algorithms and their applications was given. Also artificial bee colony (ABC) algorithm was analyzed. The software realization of the ABC algorithm for optimizing “Path of Exile” game characters passive skill graph was developed. For solving this problem, ABC algorithm with greedy heuristic was used. Created software was tested, results were compared with passive skill graphs created by players and conclusions are given.

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.

The problem of analyzing concurrent systems has been investigated by many researchers, and several solutions have been proposed. Among the proposed techniques, reachability analysis—systematic enumeration of reachable states in a finite-state model—is attractive because it is conceptually simple and relatively straightforward to automate and can be used in conjunction with model-checking procedures to check for application-specific as well as general properties. The system validation problem considered here is the problem of verifying that the original specification is itself logically consistent. If, for instance, the specification has a design error, an implementation is expected to pass a conformance test if it contains the same error. A validation for the logical consistency of the system, however, must reveal the design error. An automated analysis of all reachable states in a distributed system can be used to trace obscure logical errors that would be very hard to find manually. This type of validation is traditionally performed by the symbolic execution of a finite state machine model of the system studied. The author presents an overview of the existing validation techniques and methods. Specified and analyzed systems are presented as reachable state graph. The implementation of the aggregate specifications validation system is also presented.

Formalios specifikacijos – tai matematinis programinės ar techninės įrangos aprašymas, kurį galima naudoti sistemos realizacijai. Formalių specifikacijų naudojimas dar negarantuoja specifikacijos teisingumo. Tam naudojami formalaus verifikavimo metodai. Šiame dokumente aptariami formalių specifikacijų validavimo metodai. Du populiaraiausi formalių specifikacijų validavimo metodai yra pasiekiamų būsenų grafo analizė bei invarianto tikrinimas. Pasiekiamų būsenų grafo analizę sudaro pasiekiamų būsenų grafo generavimas ir analizė. Grafo analizės metu ieškoma aklaviečių, uždarų ciklų, nepasiekiamų būsenų, atliekamas būsenų koordinačių apribojimų tikrinimas bei invarianto tikrinimas. Tradiciniai pasiekiamų būsenų grafo sudarymo algoritmai grafo sudarymui naudoja sistemos būsenų eilę. Kiekviena išanalizuota būsena įrašoma į pasiekiamų būsenų grafą. Dokumente aptariamas lygiagretaus programavimo naudojimas būsenų grafo generavimui, kuris analizuoja ir generuoja sistemos būsenas naudodamas lygiagrečias gijas. Eksperimentų su vienkanale aptarnavimo sistema metu nustatyta, kad lygiagretaus algoritmo naudojimas šio uždavinio metu leidžia pagerinti sistemos veikimą iki 35%, priklausomai nuo būsenų skaičiaus. / Arguably the most important task in creation of software is user requirement specification. Accurate requirement specification allows avoidance of errors in late stages of software development. This is extremely important in critical systems, where even vague error can cause great financial losses or even human victims. One of the methods used for precise user requirement specification is use of formal specifications. Formal specification is a mathematical method for describing of software or hardware, which might be suitable for system realization. Nevertheless, the construction of formal specifications does not guarantee the correctness of specification. For this reason formal specification validation is necessary. In this paper methods of formal specification validation are discussed. Two most popular methods of formal specification validation are reachable state graph analysis and invariant checking. Reachable state graph analysis consists of graph generation and graph analysis. Graphs can be analyzed for dead-ends, closed loops, state reach ability checking, coordinate restriction checking or invariant checking. Traditional reachable graph generation algorithm uses unanalyzed states queue to produce reachable state graph. Each step single state is analyzed and depending on results new vertex or edge is added to state graph. An improvement to the algorithm to consider is usage of parallel programming to process multiple states simultaneously. This allows increasing the... [to full text]

The dissertation consists of two parts. In the first part several asymptotic properties of random intersection graphs are studied. They include birth thresholds for small complete subgraphs in the binomial random intersection graph, the clique number in sparse random intersection graphs and the chromatic index of random uniform hypergraphs. Several new methods and theoretically and practically relevant algorithms are proposed. Some results are illustrated with data from real-world networks. The second part deals with asymptotic enumeration and properties of graphs from minor-closed classes in the case when the excluded minors are disjoint. The class of graphs without k+1 (vertex-)disjoint cycles and more general classes of graphs without k+1 disjoint excluded minors (satisfying a condition related to fans) are considered. Typical graphs in such classes are shown to have a simple “k apex vertex” structure. Other asymptotic properties (connectivity, number of components, chromatic number, vertex degrees) are also determined. Finally, it is shown that typical graphs without k+1 disjoint minors K4 have a more complicated “2k+1 apex vertex” structure, and properties of such graphs are investigated. Part of the results is proved in greater generality. A variety of methods from computer science, graph theory, combinatorics and the theory of generating functions are applied. / Disertacijoje yra dvi pagrindinės dalys. Pirmojoje dalyje gaunami keli nauji rezultatai uždaviniams, susijusiems su atsitiktiniais sankirtų grafais. Nagrinėjamas pilnojo pografio gimimo slenkstis binominiame atsitiktiniame sankirtų grafe, didžiausios klikos eilė atsitiktiniame retame sankirtų grafe ir chromatinio indekso eilė atsitiktiniame reguliariajame hipergrafe. Sprendimams pasiūloma keletas naujų metodų, taip pat pateikiami teoriškai ir praktiškai svarbūs algoritmai. Kai kurie rezultatai iliustruojami duomenimis iš realių tinklų. Antrojoje dalyje pristatomi rezultatai grafų su uždraustaisiais minorais tematikoje, nagrinėjamas atvejis kai uždraustieji minorai yra nejungūs. Čia tiriamas asimptotinis grafų, neturinčių k+1 nepriklausomų ciklų, skaičius, rezultatai apibendrinami grafų, neturinčių k+1 uždraustųjų minorų, tačiau tenkinančių tam tikrą „vėduoklės“ apribojimą, klasėms. Įrodoma, kad tipiniai tokių klasių grafai turi paprastą „k dydžio blokatoriaus“ struktūrą, nustatomos kitos tokių grafų asimptotinės savybės (jungumas, komponenčių skaičius, viršūnių laipsniai). Galiausiai parodoma, kad tipiniai grafai, neturintys k+1 nepriklausomų minorų K4 turi sudėtingesnę „2k+1 dydžio blokatoriaus“ struktūrą ir ištiriamos kitos jų savybės. Dalis šių rezultatų įrodoma daug bendresniu atveju. Darbe pasitelkiami įvairūs informatikos, kombinatorikos, grafų, tikimybių ir generuojančiųjų funkcijų teorijos metodai.