Программирование. Рубрика в журнале - Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование
Статья научная
This article describes a method for machine-readable zones location in document images based on a combination of the Hough transform and the search for feature points. The search for feature points, filtering, and clustering using the Hough transform are described step-by-step. In addition to the machine-readable zone location, we develop a solution for determining the orientation of the zone. This method is designed to meet the requirements for real-time operation on mobile devices. The paper presents the results of measuring the quality of the method on an open synthetic dataset and the operating time on mobile devices. An experimental study on an artificial dataset show that the proposed algorithm allows to achieve a quality of 0,82 in terms of the mean value of the Jaccard indices. The operating time of the proposed algorithm for machine-readable zone location on a mobile device is 6 ms on the iPhone SE 2.
Бесплатно
Статья научная
We consider the problem on recognition of a string object presented in several video stream frames. In order to maximize the output accuracy, we combine several results of the recognition. To this end, we consider a model of result of a string object recognition. The model takes into account the estimations of alternative results of per-character classification. Also, we propose an algorithm to combine results of a string recognition according to this model. The algorithm was evaluated on a MIDV-500 dataset of document images. The experimental results show that the proposed algorithm allows to achieve the high accuracy of recognition result due to an analysis of several images, and the use of the estimations of alternative results of per-character classification gives the higher results then a combination of strings that contain only the final alternatives of each character.
Бесплатно
A numerical method for solving quadratic integer programming problem
Статья научная
We propose a new numerical method for solving quadratic integer programming problem. The algorithm is based on a special representation of a minimizer of the corresponding objective functional. The problem can be reduced to a special box-constrained integer least squares problem. The advantage of the proposed algorithm is a good computational performance (approximately O(nln(n))operations) shown in numerical experiments, where the number of unknowns can be up to 108. The computational complexity of the algorithm is confirmed experimentally by a large number of numerical experiments. The algorithm consists of 3 steps. At the average, a solution is found at the second step in 83,6% cases, while the third step gives solution in the remaining cases. The algorithm is realized with the use of the Python programming language. The results of numerical experiments can be found at the service GitHubGist. The elaborated software system was used to solve the problem on formation of the optimal order for education institutions in regions of the Russian Federation.
Бесплатно
Статья научная
The research is devoted to a numerical solution of the Volterra equations of the first kind that were obtained using the Laplace integral transforms for solving the equation of heat conduction. The paper consists of an introduction and two sections. The first section deals with the calculation of kernels from the respective integral equations at a fixed length of the significand in the floating point representation of a real number. The PASCAL language was used to develop the software for the calculation of kernels, which implements the function of tracking the valid digits of the significand. The test examples illustrate the typical cases of systematic error accumulation. The second section presents the results obtained from the computational algorithms which are based on the product integration method and the midpoint rule. The results of test calculations are presented to demonstrate the performance of the difference methods.
Бесплатно
A software package for simulation of unsteady flows of the reacting gas in the channel
Статья научная
This paper describes a software package for numerical modelling of the structure of unsteady flows of multicomponent reacting gas with graphic and informational components for resource-intensive phases of computational experiments support. Simulation of the "fine structure" of unsteady flows is achieved because the calculation is carried out at substantially irregular mobile computational mesh, including the fact that the trajectories of strong and weak discontinuities, the parameters of which are calculated by special grid-characteristic algorithms, serve as computational knots; herewith all the gridline intersections are calculated precisely. The designed software package can be used to solve the problems of reacting gas dynamic, which may have practical significance, as well as to illustrate academic courses in physical gas dynamics.
Бесплатно
A synthesis of pseudo-Boolean empirical models by precedential information
Статья научная
The problem of decision-making based on partial, precedential information is the most important when the creation of artificial intelligence systems. According to the results of observations over the behaviour of external objects or systems it is necessary to synthesize or, more precisely, extract from the data a mathematical model of optimization of the object on the basis of accumulated empirical information in the form of a finite set of triples: "a state vector, the value of the quality of functioning of the object, a binary indicator of the admissibility of this state". The aim of the work is to create and substantiate mathematical methods and algorithms that allow to synthesize models of scalar pseudo-Boolean optimization with a constraint in the form of disjunctive normal form (DNF) using this precedential information. The peculiarity of pseudo-Boolean optimization models with separable objective functions and DNF constraint, which has a bounded constant length, is their polynomial solvability. However, the complexity of bringing the problem to the form with a DNF constraint in general case is exponential. When extracting the model from the data the DNF constraint is synthesized approximately but with polynomial complexity and the number of conjunctions in the extracted DNF does not exceed the number of examples in the initial precedential information. In the paper is shown how to use binary decision trees to construct a disjunctive constraint, proposed the methods to identify the properties of monotonicity and linearity of the partially defined objective functions, and developed algorithms for solving problems pseudo-Boolean scalar optimization in the presence of incomplete, precedential initial information. The scope of application of the obtained results includes intelligent control systems, intelligent agents. Although the control models derived from the data are approximate, their application can be more successful than the use of less realistic, inconsistent with the objects models which are chosen on the base of subjective considerations.
Бесплатно
Acceleration of summation over segments using the fast Hough transformation pyramid
Статья научная
In this paper, we propose an algorithm for fast approximate calculation of the sums over arbitrary segments given by a pair of pixels in the image. Using the results of intermediate calculations of the fast Hough transform, the proposed algorithm allows to calculate the sum over arbitrary line segment with a logarithmic complexity depending on the linear size of the original image (also called fast discrete Radon transform or Brady transform). In this approach, the key element of the algorithm is the search for the dyadic straight line passing through two given pixels. We propose an algorithm for solving this problem that does not degrade the general asymptotics. We prove the correctness of the algorithm and describe a generalization of this approach to the three-dimensional case for segments of straight lines and of planes.
Бесплатно
Algorithm and software development to allocate locomotives for transportation of freight trains
Статья научная
We suggest a mathematical model to allocate locomotives for transportation of freight trains. The aim of the optimization in this model is to minimize the number of locomotives used for the transportation of the trains by choosing routes of the trains and locomotives. It is supposed that the trains can be transported only at defined time intervals (so-called train paths); every locomotive has possible routes called railway hauls. We take into account the necessity of periodic maintenance. We use graph theory and integer optimization to formulate the problem. We suggest mathematical definitions of a railway haul, a train path, a train route, and a locomotive route. An heuristic search algorithm to find an approximate solution of the problem is suggested. The main idea of the algorithm is maximal usage of locomotives that started earlier than other ones. The algorithm contains three stages. A solution of the previous stage is improved at each following stage. We use transfers of the locomotives to improve the current solution. We describe software development to optimize the model. We solve the problem using the historical data of Moscow railway.
Бесплатно
Статья научная
The article is devoted to the construction of algorithm for solving inverse spectral problems generated by Sturm-Liouville differential operators of an arbitrary even order. The goal of solving inverse spectral problems is to recover operators from their spectral characteristics and spectral characteristics of auxiliary problems. In the scientific literature, we can not find examples of the numerical solution of inverse spectral problems for the Sturm-Liouville operator of higher than the second order. However, their solution is caused by the need to construct mathematical models of many processes arising in science and technology. Therefore, the development of computationally efficient algorithm for the numerical solution of inverse spectral problems generated by the Sturm-Liouville operators of an arbitrary even order is of great scientific interest. In this article, we use linear formulas obtained earlier in order to find the eigenvalues of discrete semi-bounded operators and develop algorithm for solving inverse spectral problems for Sturm-Liouville operators of an arbitrary even order. The results of the performed computational experiments show that the use of the algorithm developed in the article makes it possible to recover the values of the potentials in the Sturm-Liouville operators of any necessary even order.
Бесплатно
Статья научная
The weighted finite element method allows to find an approximate solution to a boundary value problem with a singularity faster in 106 times than the classical finite element method for a given error equal to 10-3. In this case, it is required to apply the necessary control parameters in the weighted finite element method. The body of optimal parameters is determined on the basis of carrying out and analysing a series of numerical experiments. In this paper we propose an algorithm for processing the results of calculations and determining the body of optimal parameters for the Dirichlet problem and the Lamé system in a domain with one reentrant corner on the boundary taking values from π to 2π.
Бесплатно
Algorithm of effective transportation work for cargo traffic
Статья научная
We suggest a mathematical model that describes railway network. This model is applied to the problem of allocation locomotive for transportation of freight trains. The aim of the optimization is to minimize the size of active locomotive fleet by choosing trains and locomotives routes. An alternative formulation of the optimization problem is proposed with the usage of a heuristic objective function, which makes it possible to construct an effective decision algorithm. A new deterministic algorithm for suboptimal control is described. This algorithm is a modification of the previously proposed, based on the construction of routes tree for each locomotive and, subsequently, the choice of such a route, in which the maximum value of the given objective function is reached. Numerical experiments were carried out on the example of the historical data of the Moscow Railway. The analysis and comparison of the results are given.
Бесплатно
Algorithm of polynomial factorization and its implementation in Maple
Статья научная
In the work we propose an algorithm for a Wiener-Hopf factorization of scalar polynomials. The algorithm based on notions of indices and essential polynomials allows to find the factorization factors of the polynomial with the guaranteed accuracy. The method uses computations with finite Toeplitz matrices and permits to obtain coefficients of both factorization factors simultaneously. Computation aspects of the algorithm are considered. An a priory estimate for the condition number of the used Toeplitz matrices is found. Formulas for computation of the Laurent coefficients with the given accuracy for functions that analytical and non-vanishing in an annular neighborhood of the unit circle are obtained. Stability of the factorization factors is studied. Upper bounds for the accuracy of the factorization factors are established. All estimates are effective. The proposed algorithm is implemented in Maple computer system as module "PolynomialFactorization". Numerical experiments with the module show a good agreement with the theoretical studies.
Бесплатно
Application of the finite volume method for calculating radiation heat transfer in applied problems
Статья научная
A number of numerical models of radiation heat transfer, based on P approximation and finite volume method, were implemented in the in-house CFD code "SigmaFlow" developed by the Krasnoyarsk group of the Institute of Thermophysics of Russian Academy of Science. The implemented finite volume method allows parallel calculations based on domain decomposition of an unstructured mesh and uses sub-mapped spatially inhomogeneous angular grids. Both conventional in CFD methods for solving linear systems such as BiCGStab, DILU, CG and a marching scheme were considered. A number of applied problems with radiation heat transfer were solved by means of CFD code "SigmaFlow". They include such problems as the numerical simulation of a gas furnace chamber, a burner and a vacuum electrical furnace.
Бесплатно
Baltic Sea water dynamics model acceleration
Статья научная
Industrial Baltic sea water dynamics modelling program optimization and parallelization is described. Program is based on solving the system of partial differential equations of shallow water with numerical methods. Mechanical approach to program modernization is demonstrated involving building module dependency graph and rewriting every module in specific order. To achieve desired speed-up the program is translated into another language and several key optimization methods are used, including parallelization of most time-consuming loop nests. The theory of optimizing and parallelizing program transformations is used to achieve best performance boost with given amount of work. The list of applied program transformations is presented along with achieved speed-up for most time-consuming subroutines. Entire program speed-up results on shared memory computer system are presented.
Бесплатно
Circular shift of loop body - programme transformation, promoting parallelism
Статья научная
The article deals with the programme transformation executing the circular shift of loop body statements. It can be used for vectorizing or parallelizing. This becomes possible due to the fact that when the order of loop body statements is changed, some of the bottom-up arcs become top-down arcs. Besides, sometimes loop carried dependence arcs are substituted by loop independent ones. It should be pointed out that in executing the circular shift the number of loop iterations is reduced by one. The transformation can be used both independently and in conjunction with other transformations promoting parallelism. These could be "forward substitution", "scalar expansion", "privatization", "array expansion", etc. The transformation under consideration in this article can be used both in hand parallelization and added to a paralleling (optimizing) compiler. Moreover, the application of the transformation results in the equivalent code only for the loops where loop unrolling is the equivalent transformation. Thus, they can contain nested loops, if statements and other programming language statements.
Бесплатно
Статья научная
Inverse problems of identification of the fractional diffusivity and the order of fractional differentiation are considered for linear fractional anomalous diffusion equations with the Riemann - Liouville and Caputo fractional derivatives. As an additional information about the anomalous diffusion process, the concentration functions are assumed to be known at several arbitrary inner points of calculation domain. Numerically-analytical algorithms are constructed for identification of two required parameters of the fractional diffusion equations by approximately known initial data. These algorithms are based on the method of time integral characteristics and use the Laplace transform in time. The Laplace variable can be considered as a regularization parameter in these algorithms. It is shown that the inverse problems under consideration are reduced to the identification problem for a new single parameter which is formed by the fractional diffusivity, the order of fractional differentiation and the Laplace variable. Estimations of the upper error bound for this parameter are derived. A technique of optimal Laplace variable determination based on minimization of these estimations is described. The proposed algorithms are implemented in the AD-TIC package for the Maple software. A brief discussion of this package is also presented.
Бесплатно
Consistency and Lyapunov stability of linear singular time delay systems: a geometric approach
Статья научная
When we consider the control design of practical systems (chemical engineering systems, lossless transmission lines, large-scale electric network control, aircraft attitude control, flexible arm control of robots, etc.), time-delay often appears in many situations. Singular time delayed systems are the dynamic systems described by a mixture of algebraic and differential equations with retarded argument. This paper investigates the geometric description of initial conditions that generate smooth solutions to such problems and the construction of the Lyapunov stability theory to bound the rates of decay of such solutions. The new delay dependent conditions for asymptotic stability for the class of systems under consideration were derived. Moreover, the result is expressed in terms of only systems matrices that naturally occur in the model, therefore avoiding the need to introduce algebraic transformations into the statement of the main theorem.
Бесплатно
Constructing of OE-postman path for a planar graph
Статья научная
With automated preparation of the cutting process, the cutting plan can be represented as a flat graph. The purpose of this simulation is to determine the shortest path of the cutting tool, provided that the part cut from the sheet would not require additional cuts. The article deals with the task of building the path of the Chinese postman in a flat graph, which is a model of the cutting plan. An orderly coverage condition is imposed on this path (i.e., the cycle of traversed edges does not encompass those not yet traversed). Such a path will also be called an OE path. This limitation means the absence of additional cuts for parts. The article discusses the recursive algorithm for constructing such chains. It is proved that the algorithm has polynomial complexity. The developed software allows solving the problem for an arbitrary flat graph. The program has been tested for various types of flat graphs.
Бесплатно
Статья научная
The paper considers two simple systems of differential-algebraic equations that appear in the study of chemical kinetics problems with partial equilibria: some of the variables are determined from the condition argmin for some system function state, which depends on all variables of the problem. For such a statement, we can write a differential-algebraic system of equations where the algebraic subproblem expresses the conditions for the minimality of the state function at each moment. It is convenient to use splitting methods in numerical solving, i.e. to solve dynamic and optimization subproblems separately. In this work, we investigate the applicability of differential-algebraic splitting using two simplified systems. The convergence and order of accuracy of the numerical method are determined. Different decomposition options are considered. Calculations show that the numerical solution of the split system of equations has the same order of accuracy as the numerical solution of the joint problem. The constraints are fulfilled with sufficient accuracy if the procedure of the numerical method ends with the solution of the optimization subproblem. The results obtained can be used in the numerical solving of more complex chemical kinetics problems.
Бесплатно
Статья научная
The research work develops a Context aware Data Fusion with Ensemblebased Machine Learning Model (CDF-EMLM) for improving the health data treatment. This research work focuses on developing the improved context aware data fusion and efficient feature selection algorithm for improving the classification process for predicting the health care data. Initially, the data from Internet of Things (IoT) devices are gathered and pre-processed to make it clear for the fusion processing. In this work, dual filtering method is introduced for data pre-processing which attempts to label the unlabeled attributes in the data that are gathered, so that data fusion can be done accurately. And then the Dynamic Bayesain Network (DBN) is a good trade-off for tractability becoming a tool for CADF operations. Here the inference problem is handled using the Hidden Markov Model (HMM) in the DBN model. After that the Principal Component Analysis (PCA) is used for feature extraction as well as dimension reduction. The feature selection process is performed by using Enhanced Recursive Feature Elimination (ERFE) method for eliminating the irrelevant data in dataset. Finally, this data are learnt using the Ensemble based Machine Learning Model (EMLM) for data fusion performance checking.
Бесплатно
