Preview

Modeling and Analysis of Information Systems

Advanced search
Vol 25, No 4 (2018)
View or download the full issue PDF (Russian)

Articles

347-357 936
Abstract

The paper considers methods of program transformation equivalent to optimizing the cycle invariant, applied to the functional data-flow model implemented in the Pifagor programming language. Optimization of the cycle invariant in imperative programming languages is reduced to a displacement from the cycle of computations that do not depend on variables that are changes in the loop. A feature of the functional data flow parallel programming language Pifagor is the absence of explicitly specified cyclic computations (the loop operator). However, recurring calculations in this language can be specified recursively or by applying specific language constructs (parallel lists). Both mechanisms provide the possibility of parallel execution. In the case of optimizing a recursive function, repeated calculations are carried out into an auxiliary function, the main function performing only the calculation of the invariant. When optimizing the invariant in computations over parallel lists, the calculation of the invariant moves from the function that executes over the list items to the function containing the call. The paper provides a definition of ”invariant” applied to the Pifagor language, algorithms for its optimization, and examples of program source codes, their graph representations (the program dependence graph) before and after optimization. The algorithm shown for computations over parallel lists is applicable only to the Pifagor language, because it rests upon specific data structures and the computational model of this language. However, the algorithm for transforming recursive functions may be applied to other programming languages.

358-381 848
Abstract

In the article, we consider verification of programs with mutual recursion in the data driven functional parallel language Pifagor. In this language the program could be represented as a data flow graph, that has no control connections, and has only data relations. Under these conditions it is possible to simplify the process of formal verification, since there is no need to analyse resource conflicts, which are present in the systems with ordinary architectures. The proof of programs correctness is based on the elimination of mutual recursions by program transformation. The universal method of mutual recursion of an arbitrary number of functions elimination consists in constructing the universal recursive function that simulates all the functions in the mutual recursion. A natural number is assigned to each function in mutual recursion. The universal recursive function takes as its argument the number of a function to be simulated and the arguments of this function. In some cases of the indirect recursion it is possible to use a simpler method of program transformation, namely, the merging of the functions code into a single function. To remove mutual recursion of an arbitrary number of functions, it is suggested to construct a graph of all connected functions and transform this graph by removing functions that are not connected with the target function, then by merging functions with indirect recursion and finally by constructing the universal recursive function. It is proved that in the Pifagor language such transformations of functions as code merging and universal recursive function construction do not change the correctness of the initial program. An example of partial correctness proof is given for the program that parses a simple arithmetic expression. We construct the graph of all connected functions and demonstrate two methods of proofs: by means of code merging and by means of the universal recursive function.

382-387 797
Abstract

To ensure traffic safety of railway transport, non-destructive testing of rails is regularly carried out by using various approaches and methods, including magnetic and eddy current flaw detection methods. An automatic analysis of large data sets (defectgrams) that come from the corresponding equipment is still an actual problem. The analysis means a process of determining the presence of defective sections along with identifying structural elements of railway tracks on defectograms. At the same time, under the conditions of significant volumes of incoming information, fast and efficient algorithms of data analysis are of most interest. This article is an addition to the previous article devoted to the problem of automatic determination of a threshold level of amplitudes of useful signals (from defects and structural elements of a railway track) during the analysis of defectograms (records) of magnetic and eddy current flaw detectors, which contains an algorithm for finding the threshold level of a rail noise and its theoretical justification with examples of its operation on several fragments of real magnetic and eddy current defectograms. The article presents a simple and effective implementation of the algorithm, which is successfully used in practice for the automatic analysis of magnetic and eddy current defectograms.

 

388-401 745
Abstract

In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or k + 1 vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges, and it can be the common ending vertex to k linked edges of a multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of any other multi-edge. Special attention is paid to the class of divisible multiple graphs. The main peculiarity of them is a possibility to divide the graph into k parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. The definition of a multiple tree is stated and the basic properties of such trees are studied. Unlike ordinary trees, the number of edges in a multiple tree is not fixed. In the article, the evaluation of the minimum and maximum number of edges in the divisible tree is stated and proved. Next, the definitions of the spanning tree and the complete spanning tree of a multiple graph are given. The criterion of completeness of the spanning tree is proved for divisible graphs. It is also proved that a complete spanning tree exists in any divisible graph. If the multiple graph is weighted, the minimum spanning tree problem and the minimum complete spanning tree problem can be set. In the article, we suggest a heuristic algorithm for the minimum complete spanning tree problem for a divisible graph.

402-410 1390
Abstract

The blockchain technology is based on the ”Proof-of-work” principles. The essence of this principle is that some event (for example the bill-to-bill money transaction) becomes significant after the confirmation by a certain computer work. So, a demand arose for such computational problems to work on, and we will spend on it about the whole blockchain system computing capacity. Now the main kind of such a problem is a hash-puzzle – the problem to find a bit string with a hash that satisfies some conditions. The important hash-puzzle weakness is the lack of the useful application outside of the blockchain technology. In this work, we offer some approaches to ”Useful Proof-of-work for blockchains” problem, namely, consider some practical variants of the NP-complete problems that could be solved with the help of SAT or LLL-solvers as the Proof-of-Work computational problems. The use of the FPTproblems requires special study. The offered approach allows to provide the following characteristics of the proof-of-work computational problems: usefulness, problems complexity management (through the dimension change, choosing problems of certain kind, the indication of necessary solution precision), mass character. Herewith we admit that not every solved problem can be useful but we consider the opportunity to solve some practical problems with the help of the blockchain technology. Among other things it is also possible to compare the virtual crypto-currency value (through the energy costs spent) and the effective result of the practical problems solution. The most complicated points of the described approach are the realization of the events-problems (providing the computer work for these events) relations and the realization of the problems complexity analysis system. This issue should be viewed as the study program because of many technical details that must be worked out further.

411-420 1054
Abstract

There is an increasing interest to the instant messaging applications, messengers. These applications allow us to interact with other users and include a functionality that can help us to implement bots that automate various business processes or provide information services. In this paper, we consider a specialized question answering system that uses today’s messaging services infrastructure to support university applicants. We gathered a corpus of applicants questions throughout two years and developed an information retrieval model that helps us to find similar questions in the corpus. Applicants can type their questions using a natural language without any formal requirements to phrase construction or using special templates. If the system is unable to find a relevant answer, the user can directly address the question to representatives of the university. The system was implemented with the use of modern cloud services that are provided by Amazon. We used serverless computations and NoSQL data bases, so we had to develop an architecture of the system in that way. Since the system contains sensitive personal data and provide personalized service, we must focus our attention on security. We proposed the means that must improve the safety of the system, more specifically, authentification process that can be used without the explicit use of personal data, however, this is a future work. At present we test our system and evaluate its quality of information retrieval.

421-434 1051
Abstract

In this work, a model of distribution of the file in P2P file-sharing network constructed on the basis of ordinary differential equations is considered. The phase variables which describe a condition of distribution of the file (as a first approximation is the number of users – seeder and leecher on distribution) are defined, the factors which influence the file distribution and the change of the number of users participating in exchange are analysed. On the basis of the analysis the system of the differential equations describing distribution evolution – dynamic model of evolution of distribution is written down. The life cycle of distribution in file-sharing network consisting of four stages – distribution creation, a fast gain leechers, stabilization and (for distributions of the files losing over time relevance) fading is considered. To each stage there corresponds the ratio of model parameters, and parameters change over time. The process of measuring the condition of real distributions is described. An example of the trajectory corresponding to the evolution of real distribution at a large torrent tracker is shown. Further, the distribution stabilization stage which is characterized by constants as a first approximation parameters is considered. Equilibrium points of the dynamic model of distribution evolution are investigated, their possible quantity and type are described. All configurations of the general position, possible in the model of distribution evolution in a file-sharing P2P network are described. Phase portraits of each configuration are represented. The influence of various administrative measures on a stock of distribution stability is analysed. Ambiguity of the influence of a rating accounting system on the stability of distributions is shown. The positive influence of a system of timebonus, feedback and absorption of distributions is also shown.

435-458 1345
Abstract

The paper reviews the existing Russian-language thesauri in digital form and methods of their automatic construction and application. The authors analyzed the main characteristics of open access thesauri for scientific research, evaluated trends of their development, and their effectiveness in solving natural language processing tasks. The statistical and linguistic methods of thesaurus construction that allow to automate the development and reduce labor costs of expert linguists were studied. In particular, the authors considered algorithms for extracting keywords and semantic thesaurus relationships of all types, as well as the quality of thesauri generated with the use of these tools. To illustrate features of various methods for constructing thesaurus relationships, the authors developed a combined method that generates a specialized thesaurus fully automatically taking into account a text corpus in a particular domain and several existing linguistic resources. With the proposed method, experiments were conducted with two Russian-language text corpora from two subject areas: articles about migrants and tweets. The resulting thesauri were assessed by using an integrated assessment developed in the previous authors’ study that allows to analyze various aspects of the thesaurus and the quality of the generation methods. The analysis revealed the main advantages and disadvantages of various approaches to the construction of thesauri and the extraction of semantic relationships of different types, as well as made it possible to determine directions for future study.



Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)