Vol 52, No 7 (2018)

The development of a procedure supporting automated migration of Java programs to a new set of libraries is explored. Code migration is a common task in modern software projects. For example, it may arise when a project must be ported to a more secure or feature-rich library, a new platform, or a new version of an existing library. This paper presents a procedure for semantics-driven automated migration. A metamodel that applies the formalism earlier proposed by the authors and intended to describe libraries in object-oriented languages was developed for the migration procedure. The formalism specifies a library behaviour by using a system of extended finite state machines (EFSMs). The migration is split into five steps and each step is described in the paper. The procedure applies an algorithm of an equivalent path based on a breadth-first search extended for the needs of the migration task. The proposed procedure is implemented in a prototype of the migration tool. The tool includes modules for extraction of the software execution path, visualization of library models, user interaction, and migration. A library description language was developed for the tool. The prototype was tested by both artificial code and a real-world open source project. The article describes the experiments performed, the difficulties that have arisen in the process of migration of test samples, and how they are solved in the proposed procedure. The HTTP protocol and log library are used as libraries in the experiment. The results of the experiments indicate that code migration can be successfully automated through the developed procedures.

The classification and application of switching methods and their advantages and disadvantages are considered. A computing grid model was constructed in the form of a colored Petri net with a node, which implements cut-through packet switching. The model consists of packet switching nodes, traffic generators, and guns that form malicious traffic disguised as usual user traffic. The characteristics of the grid model are investigated under a workload with different intensities. The influence of malicious traffic such as “traffic duel” to the quality of service parameters of the grid is estimated. A comparative analysis of computing grid stability with nodes, which implement store-and-forward (SAF) and cut-through switching technologies, was conducted. It is shown that grid performance is approximately the same under workload, and under peak load the grid with a node implementing SAF packet transmission is more stable. The grid with nodes implementing SAF technology comes to a complete deadlock through an additional load, which is less than 10%. It is shown after detailed study that the traffic duel configuration does not affect the grid with cut-through nodes when increasing the workload up to peak load, at which the grid comes to a complete deadlock. The periodicity of execution of the guns, which generate malicious traffic, is determined by a random function with the Poisson distribution. The CPN Tools modeling system is used for constructing models and measuring characteristics. The grid performance and average packet delivery time are estimated under different variants of the grid load.

Prevention of data loss from digital media includes processes such as backup. It can be done manually by copying data to external media or automatically on schedule using special software. There are also remote backup systems, when data are saved over the network to some remote repository. Such systems are multi-user and process large amounts of data. A shared storage can have files containing the same fragments. The elimination of repeated data is based on the mechanism of deduplication. It is a method of information compression, when the search for copies is carried out in the entire dataset rather than within a single file. The main advantage of using this technology is significant saving of disk space. However, the mechanism of eliminating repetitive data can significantly reduce the rate of saving and restoring information. This paper is devoted to the problem of implementing such a mechanism in the backup system with information storage in a relational database. In this work we consider an example of implementation of such a system working in two modes: with and without data deduplication. This paper illustrates a class diagram for the development of the client part of the application as well as the description of tables and their relationships in a database that belongs to the backend. The author proposes an algorithm for saving data with deduplication, and also provides results of comparative tests on the speed of the algorithms for saving and recovering information when working with relational database management systems from various manufacturers.

In the article, the definition of an undirected multiple graph of any natural multiplicity \(k > 1\) is stated. There are edges of three types: ordinary edges, multiple edges, and multi-edges. Each edge of the last two types is the 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 some multi-edge. If a vertex is the common end of a multi-edge, it cannot be the common end of any other multi-edge. Also, a class of the divisible multiple graphs is considered. 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 ordinary edges. Each part is an ordinary graph. The following terms are generalized: the degree of a vertex, connectedness of a graph, the path, the cycle, the weight of an edge, and the path length. The definition of a reachability set for the ordinary and multiple edges is stated. The adjacency property is defined for a pair of reachability sets. It is shown, that we can check the connectedness of a multiple graph with the polynomial algorithm based on the search for reachability sets and testing their adjacency. A criterion of the existence of a multiple path between two given vertices is considered. The shortest multiple path problem is stated. Then, we suggest an algorithm for finding the shortest path in a multiple graph. It uses Dijkstra’s algorithm for finding the shortest paths in subgraphs, which correspond to different reachability sets.

Null values have become an urgent problem since the creation of the relational data model. The impact of uncertainty affects all types of dependences used in designing and operating a database. This fully applies to inclusion dependences, which are the theoretical basis for referential integrity on the data. Attempts to solve this problem contain inaccuracies in the statement of the problem and its solution. The errors in formulation of the problem can be associated with use in the definition of untyped inclusion dependences, which leads to permutations of the attributes, although, the attributes in database technology are identified by name and not by their place. In addition, linking with the use of inclusion dependences of heterogeneous attributes, even of the same type, is a sign of lost functional dependences and leads to interaction of inclusion dependences and non-trivial functional dependences. Inaccuracies in the solution of the problem are contained in the statements of axioms and proof of their properties, including completeness. In this paper we propose an original solution of this problem only for typed inclusion dependences in the presence of Null values: a new axiom system is proposed, its completeness and soundness are proven. On the basis of inference rules, we developed an algorithm for the construction of a nonredundant set of typed inclusion dependences. The correctness of the algorithm is proven.

Nondestructive testing of rails using various approaches and methods, including methods of magnetic and eddy-current flaw detection, is regularly carried out to ensure traffic safety on railway transport. This article is devoted to the problem of automatic determination of the threshold level of the amplitudes of useful signals (from the flaws and structural elements of the track) when interpreting defectograms of magnetic and eddy-current flaw detectors. A signal is considered useful (and is subject to further analysis), if the deviation of its value from the average value of all signals is, at least, twice more than the threshold noise level of rails. The probability of appearance of a signal with some amplitude in flawless rails in a section without structural elements, i.e. being a rail noise, is characterized by the normal distribution law. Thus, the three-sigma rule can be used to calculate the threshold noise level, and doubling the noise threshold gives a level that, if it exceeds the amplitude deviation from the sample mean, means that the signal is useful. This article proposes an algorithm to find the threshold noise level of rails and gives its theoretical justification, as well as examines examples of its operation in several fragments of real magnetic and eddy-current defectograms.

Let \(n \in \mathbb{N}\) and let \({{Q}_{n}}\) be the unit cube \({{[0,1]}^{n}}\). For a nondegenerate simplex \(S \subset {{\mathbb{R}}^{n}}\), by \(\sigma S\) denote the homothetic copy of \(S\) with center of homothety in the center of gravity of \(S\) and ratio of homothety \(\sigma .\) Put \(\xi (S) = min{\text{\{ }}\sigma \geqslant 1:{{Q}_{n}} \subset \sigma S{\text{\} }}{\text{.}}\) We call \(\xi (S)\) an absorption index of simplex \(S\). In the present paper we give new estimates for minimal absorption index of the simplex contained in \({{Q}_{n}}\), i.e., for the number \({{\xi }_{n}} = min{\text{\{ }}\xi (S):S \subset {{Q}_{n}}{\text{\} }}.\) In particular, this value and its analogues have applications in estimates for the norms of interpolation projectors. Previously the first author proved some general estimates of \({{\xi }_{n}}\). Always \(n \leqslant {{\xi }_{n}} < n + 1\). If there exist an Hadamard matrix of order \(n + 1\), then \({{\xi }_{n}} = n\). The best known general upper estimate have the form \({{\xi }_{n}} \leqslant \tfrac{{{{n}^{2}} - 3}}{{n - 1}}\)\((n > 2)\). There exist constant \(c > 0\) not depending on \(n\) such that, for any simplex \(S \subset {{Q}_{n}}\) of maximum volume, inequalities \(c\xi (S) \leqslant {{\xi }_{n}} \leqslant \xi (S)\) take place. It motivates the making use of maximum volume simplices in upper estimates of \({{\xi }_{n}}\). The set of vertices of such a simplex can be consructed with application of maximum \(0/1\)-determinant of order \(n\) or maximum \( - 1/1\)-determinant of order \(n + 1\). In the paper we compute absorption indices of maximum volume simplices in \({{Q}_{n}}\) constructed from known maximum \( - 1/1\)-determinants via special procedure. For some \(n\), this approach makes it possible to lower theoretical upper bounds of \({{\xi }_{n}}\). Also we give best known upper estimates of \({{\xi }_{n}}\) for \(n \leqslant 118\).

We consider the problem of mathematical modeling of oxidation-reduction oscillatory chemical reactions based on the Belousov reaction mechanism. The process of main component interaction in such a reaction can be interpreted by a phenomenologically similar to it predator–prey model. Thereby, we consider a parabolic boundary value problem consisting of three Volterra-type equations, which is the mathematical model of this reaction. We carry out a local study of the neighborhood of the system’s non-trivial equilibrium state and define a critical parameter at which the stability is lost in this neighborhood in an oscillatory manner. Using standard replacements, we construct the normal form of the considered system and the form of its coefficients, that define the qualitative behavior of the model, and show the graphical representation of these coefficients depending on the main system parameters. The obtained normal form makes it possible to prove a theorem on the existence of an orbitally asymptotically stable limit cycle, which bifurcates from the equilibrium state, and find its asymptotics. To identify the applicability limits of the found asymptotics, we compare the oscillation amplitudes of one periodic solution component obtained on the basis of asymptotic formulas and by numerical integration of the model system. Along with the main case of Andronov–Hopf bifurcation, we consider various combinations of normal form coefficients obtained by changing the parameters of the studied system and the resulting behavior of solutions near the equilibrium state. In the second part of the paper, we consider the problem of diffusion loss of stability of the spatially homogeneous cycle obtained in the first part. We find a critical value of the diffusion parameter at which this cycle of the distributed system loses its stability.

A periodic boundary value problem is considered for one of the first versions of the Kuramoto–Sivashinsky equation, which is widely known in mathematical physics. Local bifurcations in a neighborhood of spatially homogeneous equilibrium points are studied in the case when they change stability. It is shown that the loss of stability of homogeneous equilibrium points leads to the occurrence of a two-dimensional local attractor on which all solutions are periodic functions of time, except for one spatially inhomogeneous state. The spectrum of frequencies of this family of periodic solutions fills the entire number line, and all of them are unstable in the sense of Lyapunov’s definition in the metric of the phase space (the space of initial conditions) of the corresponding initial boundary value problem. As the phase space, a Sobolev functional space natural for this boundary value problem is chosen. Asymptotic formulas are given for periodic solutions filling the two-dimensional attractor. To analyze the bifurcation problem, analysis methods for an infinite-dimensional dynamical system are used: the integral (invariant) manifold method combined with the methods of the Poincaré normal form theory and asymptotic methods. Analyzing the bifurcations for the periodic boundary value problem is reduced to analyzing the structure of the neighborhood of the zero solution to the homogeneous Dirichlet boundary value problem for the equation under consideration.

For a second-order equation with a small factor at the highest derivative, the asymptotic behavior of all eigenvalues of periodic and antiperiodic boundary value problems is studied. The main assumption is that the coefficient at the first derivative in the equation is the sign of the variable, i.e., turning points exist. An algorithm to compute all coefficients of asymptotic series for every considered eigenvalue is developed. It turns out that the values of these coefficients are determined only by the values of the coefficients of the original equation in a neighborhood of turning points. The asymptotic behavior of the length of Lyapunov stability and instability zones is obtained. In particular, the stability problem is solved for solutions of second-order equations with periodic coefficients and small parameters at the highest derivative.

The system of phase differences for a chain of diffuse weakly coupled oscillators on a stable integral manifold is constructed and analyzed. It is shown (by means of numerical methods) that Lyapunov dimension growth is close to linear as the number of oscillators in the chain increases. Extensive computations performed for the difference model of the Ginsburg–Landau equation illustrate this result and determine the applicability limits for asymptotic methods.

In this paper, we offer an efficient parallel algorithm for solving the NP-complete Knapsack Problem in its basic, so-called 0-1 variant. To find its exact solution, algorithms belonging to the category “branch-and-bound methods” have long been used. To speed up the solving with varying degrees of efficiency, various options for parallelizing computations are also used. We propose here an algorithm for solving the problem, based on the paradigm of recursive-parallel computations. We consider it suited well for problems of this kind, when it is difficult to immediately break up the computations into a sufficient number of subtasks that are comparable in complexity, since they appear dynamically at run time. We used the RPM_ParLib library, developed by the author, as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network in the .NET Framework. Such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support for the .NET Framework can be used as a programming language in conjunction with this library. For our experiments, we developed some C# applications using this library. The main purpose of these experiments was to study the acceleration achieved by recursive-parallel computing. A detailed description of the algorithm and its testing, as well as the results obtained, are also given in the paper.

Let \(n \in N\), and let \({{Q}_{n}}\) be the unit cube \({{[0,1]}^{n}}\). By \(C({{Q}_{n}})\) we denote the space of continuous functions \(f:{{Q}_{n}} \to R\) with the norm \({{\left\| f \right\|}_{{C({{Q}_{n}})}}}: = \mathop {max}\limits_{x \in {{Q}_{n}}} \left| {f(x)} \right|,\) by \({{\Pi }_{1}}\left( {{{R}^{n}}} \right)\) – the set of polynomials of \(n\) variables of degree \( \leqslant 1\) (or linear functions). Let \({{x}^{{(j)}}},\)\(1 \leqslant j \leqslant n + 1,\) be the vertices of an \(n\)-dimnsional nondegenerate simplex \(S \subset {{Q}_{n}}\). The interpolation projector \(P:C({{Q}_{n}}) \to {{\Pi }_{1}}({{R}^{n}})\) corresponding to the simplex \(S\) is defined by the equalities \(Pf\left( {{{x}^{{(j)}}}} \right) = f\left( {{{x}^{{(j)}}}} \right).\) The norm of \(P\) as an operator from \(C({{Q}_{n}})\) to \(C({{Q}_{n}})\) can be calculated by the formula \(\left\| P \right\| = \mathop {max}\limits_{x \in {\text{ver}}({{Q}_{n}})} \sum\nolimits_{j = 1}^{n + 1} {\left| {{{\lambda }_{j}}(x)} \right|} .\) Here \({{\lambda }_{j}}\) are the basic Lagrange polynomials with respect to \(S,\)\({\text{ver}}({{Q}_{n}})\) is the set of vertices of \({{Q}_{n}}\). Let us denote by \({{\theta }_{n}}\) the minimal possible value of \(\left\| P \right\|.\) Earlier the first author proved various relations and estimates for values \(\left\| P \right\|\) and \({{\theta }_{n}}\), in particular, having geometric character. The equivalence \({{\theta }_{n}} \asymp \sqrt n \) takes place. For example, the appropriate according to dimension \(n\) inequalities can be written in the form \(\tfrac{1}{4}\sqrt n \)\( < {{\theta }_{n}}\)\( < 3\sqrt n .\) If the nodes of a projector \(P{\text{*}}\) coincide with vertices of an arbitrary simplex with maximum possible volume, then we have \(\left\| {P{\text{*}}} \right\| \asymp {{\theta }_{n}}.\) When an Hadamard matrix of order \(n + 1\) exists, holds \({{\theta }_{n}} \leqslant \sqrt {n + 1} .\) In the present paper, we give more precise upper bounds of \({{\theta }_{n}}\) for \(21 \leqslant n \leqslant 26\). These estimates were obtained with application of maximum volume simplices in the cube. For constructing such simplices, we utilize maximum determinants containing the elements \( \pm 1.\) Also we systematize and comment the best nowaday upper and low estimates of \({{\theta }_{n}}\) for concrete \(n.\)

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 only has 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 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. The 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.

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 estimation 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.

A model of neural association of three pulsed neurons with a delayed broadcast connection is considered. It is assumed that the parameters of the problem are chosen near the critical point of stability loss by the homogeneous equilibrium state of the system. Because of the broadcast connection the equation corresponding to one of the oscillators can be detached in the system. Two remaining pulsed neurons interact with each other and, in addition, there is a periodic external action, determined by the broadcast neuron. Under these conditions, the normal form of this system is constructed for the values of parameters close to the critical ones on a stable invariant integral manifold. This normal form is reduced to a four-dimensional system with two variables responsible for the oscillation amplitudes, and the other two are defined as the difference between the phase variables of these oscillators with the phase variable of the broadcast oscillator. The obtained normal form has an invariant manifold on which the amplitude and phase variables of the oscillators coincide. Dynamics of the problem is described on this manifold. An important result was obtained on the basis of numerical analysis of the normal form. It turned out that periodic and chaotic oscillatory solutions can occur when the coupling link between the oscillators is weakened. Moreover, a cascade of bifurcations associated with the same type of phase transformations was discovered, where a self-symmetric stable cycle alternately loses symmetry with the appearance of two symmetrical to each other cycles. A cascade of bifurcations of period doubling occurs with each of these cycles with the appearance of symmetric chaotic regimes. With further decreasing of the coupling parameter, these symmetric chaotic regimes are combined into a self-symmetric one, which is then rebuilt into a self-symmetric cycle of a more complex form compared to the cycle obtained at the previous step. Then the whole process is repeated. Lyapunov exponents were computed to study chaotic attractors of the system.