Search

The authors consider optimization transformations of the algorithm for constructing minimal generating sets of solutions of systems of linear homogeneous equations (SLHE) over the set of natural numbers. The paper describes the features of such SLHEs, substantiates optimization transformations, and presents examples of the algorithm before and after optimization transformations. It illustrates the applying the algorithm with examples of the analysis of Petri net properties and the construction of a basic solution set in the fields of complex, real, and rational numbers and over finite fields. [ABSTRACT FROM AUTHOR]

This paper considers algorithm unions (portfolios and teams) of optimization algorithms, their properties, and their impact on the acceleration of the optimization process. The authors have investigated the application of unions of global equilibrium search algorithms to specific discrete optimization problems and various information exchange schemes within algorithm teams. They devoted significant attention to experimental research of developed portfolios and algorithm teams in real-time mode using the multi-processor computing complex SCIT-4 at the V. M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine and to their comparative analysis. The authors have obtained estimates of the efficiency of algorithm unions, indicating that the team approach has significant advantages over algorithm portfolios. [ABSTRACT FROM AUTHOR]

The paper deals with state-of-the-art trends in the field of automated hardware development, specifically development of digital systems using programmable logic integrated circuits, as exemplified by field-programmable logic arrays. The paper suggests a modeling method of development using an algebraic model of design specifications, requirements and binary codes in order to apply formal methods of verification, model-based testing, as well as methods of algebraic matching. The specifications of the algebraic hardware model are behavior algebra determined on a set of actions and behaviors. [ABSTRACT FROM AUTHOR]

The paper proposes parallel algorithms for solving digital filtering problems of different dimensions using modern universal computers. Theoretical estimates of the complexity and speedup are obtained, which confirm the high efficiency of these algorithms. Some of the proposed parallel algorithms are implemented using computers with a multi-core processor, and real estimates of the speedup are obtained, which agree well with theoretical ones. [ABSTRACT FROM AUTHOR]

Equilibrium problems in Hadamard metric spaces are considered in the paper. For approximate solution of problems, a new iterative adaptive two-stage proximal algorithm is proposed and analyzed. In contrast to the previously used rules for choosing the step size, the proposed algorithm does not calculate bifunction values at additional points and does not require knowledge of the value of bifunction's Lipschitz constants. For pseudo-monotone bifunctions of Lipschitz type, the theorem on weak convergence of the sequences generated by the algorithm is proved. It is shown that the proposed algorithm is applicable to pseudo-monotone variational inequalities in Hilbert spaces. [ABSTRACT FROM AUTHOR]

The paper considers a mathematical model of the land use problem on hypergraphs. It is shown that, within the framework of this model, the problem can be formulated as an optimization problem on a fragmented structure. Moreover, the problem of finding the optimal solution itself reduces to the problem of unconditional combinatorial optimization on a set of permutations. A variant of a hybrid algorithm for finding approximate solutions to the problem based on a combination of a fragmented algorithm and an ant colony algorithm is proposed. [ABSTRACT FROM AUTHOR]

The paper observes a similarity between the stochastic optimal control of discrete dynamical systems and the learning multilayer neural networks. It focuses on contemporary deep networks with nonconvex nonsmooth loss and activation functions. The machine learning problems are treated as nonconvex nonsmooth stochastic optimization problems. As a model of nonsmooth nonconvex dependences, the so-called generalized-differentiable functions are used. The backpropagation method for calculating stochastic generalized gradients of the learning quality functional for such systems is substantiated basing on Hamilton–Pontryagin formalism. Stochastic generalized gradient learning algorithms are extended for training nonconvex nonsmooth neural networks. The performance of a stochastic generalized gradient algorithm is illustrated by the linear multiclass classification problem. [ABSTRACT FROM AUTHOR]

The paper presents a genetic algorithm for multicriteria optimization of parameters of a technological process, which finds a solution not from a certain point but from a specified population. The objective functions are used without their derivatives and probabilistic choice rules are applied. The multicriteria optimization is based on finding a solution that simultaneously optimizes the machining parameters defined by functions of productivity, tool consumption, tool cost, etc. [ABSTRACT FROM AUTHOR]

One of the major problems of transport logistics is planning optimal delivery routes. Solving this problem leads to combinatorial optimizations that require complex computations. The present research considers an asymmetric problem of transport routing with a limitation of the carrying capacity of transport facilities, the duration of the route, and a heterogeneous transport facilities fleet. An algorithm for solving the routing problem based on the ant colony method is proposed. The web application that has been developed implements the proposed algorithm for solving this problem. The obtained optimal routes were compared with the results of route building by other cartographic services. The proposed algorithm showed the best result. [ABSTRACT FROM AUTHOR]

In the paper, we consider bilevel problems: variational inequality problems over the set of solutions of the equilibrium problem. Finding normal Nash equilibrium is an example of such a problem. To solve these problems, an iterative algorithm is proposed that combines the ideas of the two-stage proximal method, adaptability, and iterative regularization. In contrast to the previously used rules for choosing the step size, the proposed algorithm does not calculate bifunction values at additional points and does not require knowledge of information on bifunction's Lipschitz constants and operator's Lipschitz and strong monotonicity constants. For monotone bifunctions of Lipschitz type and strongly monotone Lipschitz operators, the theorem on strong convergence of sequences generated by the algorithm is proved. The proposed algorithm is shown to be applicable to monotone bilevel variational inequalities in Hilbert spaces. [ABSTRACT FROM AUTHOR]

The paper is devoted to the Evidence Algorithm, initiated by Academician Glushkov in 1970 and implemented as Russian-language and English-language SAD systems intended for automated deduction. Some of their characteristics and features are described. Examples of their application to solving mathematical and common problems that require deductive constructions are provided. Possible ways of the further development of the English-language SAD system are given. [ABSTRACT FROM AUTHOR]

The paper presents the final version of the algorithm for translating MSC-2000 documents to event-equivalent Petri nets. The input document may include any elements of the MSC-2000 language, assuming that condition element value is not used and sequential composition of MSC diagrams is regarded as strict. The algorithm is implemented as a full-functional prototype and can be used to verify software systems. [ABSTRACT FROM AUTHOR]

An efficient computational method of segmentation of license plate characters is considered. Division into blocks is carried out on the assumption that the characters are localized in certain specific areas. The license plate image is divided into n parts, where n is the number of characters. The paper also describes a segmentation algorithm that underlies a modified version of this algorithm. Contour analysis was used as a mathematical apparatus for the solution of this problem. The proposed character segmentation algorithm allows its use in vehicle license plate recognition systems. [ABSTRACT FROM AUTHOR]

The author proposes algorithms for constructing a prebasis and the basis of the set of solutions to systems of linear constraints in the form of equalities and inequalities in the domains of integers, which are based on combined coefficients of constraints. The article considers the algorithm for constructing the prebasis and basis of systems of linear equations and algorithms for constructing the fundamental system of solutions to systems of linear homogeneous and linear inhomogeneous inequalities. [ABSTRACT FROM AUTHOR]

An efficient computational method of segmentation of license plate characters is considered. Division into blocks is carried out on the assumption that the characters are localized in certain specific areas. The license plate image is divided into n parts, where n is the number of characters. The paper also describes a segmentation algorithm that underlies a modified version of this algorithm. Contour analysis was used as a mathematical apparatus for the solution of this problem. The proposed character segmentation algorithm allows its use in vehicle license plate recognition systems. [ABSTRACT FROM AUTHOR]

This paper substantiates the urgency of developing theoretical foundations, methods, and algorithms for cryptographic protection of color image pixels using problem-oriented multifunctional data structuring and representing codes of color image pixels in the Rademacher, Chrestenson, Rademacher–Chrestenson, Haar–Chrestenson, and Galois systems and investigates the possibility of increasing the operating speed of algorithms for transforming, processing, and recognizing digital images using the modular arithmetic of residue number systems based on the mathematics of arithmetic operations of a non-positional residue number system. [ABSTRACT FROM AUTHOR]

An algorithm for the best uniform approximation by a spline with optimal knots is presented in the paper. Differential evolution is used to find optimal knots. It is one of the best evolutionary algorithms, which sustainably finds function's global optimum in minimum time. Spline coefficients are computed as a solution of a spline-approximation problem with fixed knots. Results of the numerical experiment are given. [ABSTRACT FROM AUTHOR]

This paper considers two variants of problems that arise in developing optical computers. The first variant is related to the mathematical analysis of problems of optical bistability in the case of multibeam interaction of laser radiation in nonlinear media. The existence of optical bistability is confirmed by the results of solving the boundary value problem for a system of nonlinear ordinary differential equations. In the general case of an arbitrary nonstationary process, the problem is reduced to solving a system of two nonlinear integral equations with respect to complex amplitudes describing interference patterns. The second variant of problems is devoted to studying the absorption and scattering of light by nanomaterials. As a result, a multidimensional integral equation was obtained for the complex amplitude of the electric field. A fundamentally important feature of this equation is its singularity inside a nanoparticle. [ABSTRACT FROM AUTHOR]

This paper considers the problem of constructing reduced disjunctive normal forms of order-convex Boolean functions. An original algorithm is proposed for finding these forms. The algorithm uses concepts of the theory of ordered sets such as an ideal and a coideal and has a substantially lower time complexity than the classical Quine-McCluskey algorithm. [ABSTRACT FROM AUTHOR]

This paper investigates the impact of communication between optimization algorithms running in parallel. In particular, we focus on the weighted maximum cut (WMAXCUT) problem and compare different communication strategies between teams of GES algorithms running in parallel. The results obtained by teams encourage the development of team algorithms. They were significantly better than the algorithmic portfolio (no communication) approach and suggest that the communication between algorithms running in parallel is a promising research direction. [ABSTRACT FROM AUTHOR]

The results of testing formula simplification tools are presented in the first part of this paper. In the second part, an algorithm for constructing canonical forms of linear semi-algebraic formulas is described. The main result of the study is the definition of the canonical form of a linear semi-algebraic formula that has the property of uniqueness and other useful properties. An algorithm for constructing such a formula is described. [ABSTRACT FROM AUTHOR]

The paper provides an approach to the assessment of the validity of decisions made for complex systems using multicriteria methods. It is also proposed to evaluate the validity based on the relevant criterion, which involves not only assessment of the results obtained by the multicriteria methods but also preliminary stages related to preparation of the initial data. [ABSTRACT FROM AUTHOR]

In this paper, new algorithms are proposed to solve operator inclusion problems with maximal monotone operators acting in a Hilbert space. The algorithms are based on inertial extrapolation and three well-known methods: Tseng forward-backward splitting and two hybrid algorithms for approximation of fixed points of nonexpansive operators. Theorems about strong convergence of the sequences generated by the algorithms are proved. [ABSTRACT FROM AUTHOR]

This paper considers generalized neural elements and identifies the conditions for implementation of functions of algebra of logic from these elements. We introduce the concept of a modified core of Boolean functions with respect to the system of characters of a group on which functions of algebra of logic are given. The criteria of belonging these functions to the class of generalized neurofunctions are provided. The algebraic structure of cores of Boolean neurofunctions is studied. On the basis of properties of tolerance matrices, a number of necessary conditions for implementation of Boolean functions by one generalized neural element are obtained. The obtained results allow to develop efficient methods of synthesis of integer-valued generalized neural elements with a large number of inputs that can be successfully applied in solving information compression and transmission problems, as well as discrete signal recognition problems. [ABSTRACT FROM AUTHOR]

This paper describes algorithms for non-negative factorization of sparse matrices and tensors, which is a popular technology in artificial intelligence in general and in computer linguistics in particular. It is proposed to use the latent Dirichlet distribution to reduce matrices and tensors to block-diagonal form for parallelizing computations and accelerating non-negative factorization of linguistic matrices and tensors of extremely large dimension. The proposed model also allows to supplement models with new data without performing non-negative factorization of the entire very large tensor anew from the very beginning. [ABSTRACT FROM AUTHOR]

This survey paper considers index structures for fast similarity search for objects represented by real-valued vectors. Index structures based on locality-sensitive hashing and their modifications are discussed. The ideas of specific algorithms, including the recently proposed ones, are stated. Their interrelations and some theoretical aspects are discussed. [ABSTRACT FROM AUTHOR]

The paper considers the solution of mixed combinatorial optimization problems on arrangements by the method of construction of lexicographic equivalence. A generalization of the relation of equivalence, which is used for space splitting, is proposed and its properties are analyzed. The algorithms of the method known earlier are modified, an approximated algorithm is validated. [ABSTRACT FROM AUTHOR]

This paper presents algorithms for solving several matching problems on Mazurkiewicz traces. The creation of the algorithms is reduced to the construction of automata that recognize corresponding rational trace languages. Such languages and their properties were studied by many authors. This paper considers trace languages used in solving concrete problems that have analogs in stringology. [ABSTRACT FROM AUTHOR]

The paper considers the properties of feasible and optimal scheduling of jobs on one machine under constraints on the terms of the beginning and completion of jobs and on partial sequences of job performance. The established properties and the lower-bound estimates of the length of the optimal schedule are used to develop methods for the exact and approximate solutions of the formulated problem by sequential optimization algorithms. The proposed algorithms are illustrated by numerical examples and can be successfully applied to solve these problems in the absence of constraints. [ABSTRACT FROM AUTHOR]

The year 2017 marks the 15th anniversary of the SCIT supercomputer project, which allows us to summarize the results and draw conclusions. In this paper, we discuss the evolution of SCIT architecture and statistics of the supercomputing center for years 2002-2017. These data will be useful for computer cluster developers and researchers who design resource management algorithms for computing clusters. [ABSTRACT FROM AUTHOR]

Nemirovski and Yudin proposed the mirror descent algorithm at the late 1970s to solve convex optimization problems. This method is suitable to solve huge-scale optimization problems. In the paper, we describe a new version of the mirror descent method to solve variational inequalities with pseudomonotone operators. The method can be interpreted as a modification of Popov's two-step algorithm with the use of Bregman projections on the feasible set. We prove the convergence of the sequences generated by the proposed method. [ABSTRACT FROM AUTHOR]

This paper proposes an approach to improving the efficiency of packet data transmission in computer radio networks on the basis of implementation of a complex of algorithms for operative compact data encoding and protection. The algorithms are implemented by subscribers of a network and provide the encryption and noise protection of binary sequences in noisy channels and formation and adaptive transmission of highly informative and noise-immune data packets consisting of interval code-signal sequences with a variable base. [ABSTRACT FROM AUTHOR]

Using exact penalty functions in schemes of decomposition in variables for nonlinear optimization make it possible to overcome problems related to implicit description of the feasible region of master problem. The paper deals with determining the values of penalty coefficients in such an approach. In the case where the functions of the original problem are not defined on the whole space of variables, the author proposes to use convex extension of functions. [ABSTRACT FROM AUTHOR]

The authors consider primal interior point algorithms to find normal solutions to systems of linear equations with bilateral constraints on variables. Analyzing this problem and the methods of its solution is important to develop the theory of mathematical modeling (in particular, to solve power engineering problems) and to create efficient computational algorithms. The paper contains the results of experimental analysis of the algorithms using test problems and identifies the ways to accelerate the computational process. [ABSTRACT FROM AUTHOR]

This paper proposes fast algorithms for the cellular operation $$ D=C+{\displaystyle \sum_{l=1}^{\upxi}{A}_l{B}_l} $$ that are based on hybrid multiplication algorithms for matrices of orders n = 3μ (μ > 1) and n = 6μ (μ > 0) and are characterized by the lowest computational complexity in comparison with well-known algorithms. The multiplicative, additive, and overall complexities of the mentioned algorithms are estimated. [ABSTRACT FROM AUTHOR]

The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer. [ABSTRACT FROM AUTHOR]

This paper considers the problem of exploration of finite undirected graphs by a collective of agents. Two agents-researchers simultaneously traverse a graph, read and change labels of graph elements, and send necessary information to the agent-experimenter constructing a representation of the graph being explored. An exploration algorithm is proposed with a linear (with respect to the number of vertices) time complexity and a quadratic space complexity. An optimization procedure is developed that partitions a graph with a view to exploring its parts by different agents. Each of the agents traversing a graph needs two different colors (three colors are used in the aggregate) for exploring a graph. The algorithm is based on the depth-first traversal method. [ABSTRACT FROM AUTHOR]

This paper proposes constructive algorithms for ellipsoidal estimation of state vectors measured under bounded disturbances in families of linear and a rather wide class of nonlinear dynamic systems. The algorithms are based on the use of support functions and approximation of generally non-convex sets of estimates by ellipsoids. [ABSTRACT FROM AUTHOR]

To improve the value of the objective function, two algorithms for transforming the current base into a new one are proposed. It is shown that the maximum cut problem on an undirected graph can be reduced to finding the base of the extended polynomial, for which the value of the minimum cut that separates the source and the sink is maximum. The necessary and sufficient conditions for optimality of the solution of the maximum cut problem on undirected graphs in terms of flow theory are formulated. [ABSTRACT FROM AUTHOR]

The paper presents the results in the construction of high-accuracy computational algorithms for the classes of partial derivative problems with discontinuous solutions, including ill-posed and eigenvalue problems. The optimal control in complex distributed systems is investigated. On the basis of the optimal control theory, explicit expressions are obtained for gradients of residual functionals to identify different parameters of multicomponent distributed systems. The possibility of using pseudoinverse matrices to solve some linear inverse problems in a finite number of arithmetic operations is considered. [ABSTRACT FROM AUTHOR]

Two-base numeration systems are introduced in the paper. They are generalizations of standard numeration systems, which are based on powers of a given radix. The results are reviewed and applications for encoding numbers and trees are given. Further research fields are outlined. A new parallel algorithm for modular exponentiation and new classes of prefix codes are presented. [ABSTRACT FROM AUTHOR]

The concepts of forbidden strings and forbidden subsequences are generalized to traces. This paper presents algorithms for constructing sets of minimal forbidden traces and minimal forbidden subtraces for a given trace. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for estimating the spatial inhomogeneity of images that is characterized by the number of patterns in a definite zone, their surface areas, and the efficient gradient between them. The use of this algorithm for quantifying the spatial inhomogeneity of the electromagnetic field of different loop radiators for radiofrequency hyperthermia showed that an applicator in the form of a circular arc produces a more inhomogeneous field than an applicator with a rectilinear profile. [ABSTRACT FROM AUTHOR]

This paper proposes two new cellular methods of matrix multiplication that allow one to obtain cellular analogs of well-known matrix multiplication algorithms with reduced computational complexities as compared with analogs derived on the basis of well-known cellular methods of matrix multiplication. The new fast cellular method reduces the multiplicative, additive, and overall complexities of the mentioned algorithms by 15%. The new mixed cellular method combines the Laderman method with the proposed fast cellular method. The interaction of these methods reduces the multiplicative, additive, and overall complexities of the matrix multiplication algorithms by 28%. Computational complexities of these methods are estimated using a model of obtaining cellular analogs of the traditional matrix multiplication algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm that creates a digital signature in a nonpositional polynomial notation and forms three surplus residues modulo one extension polynomial base number. Such a signature allows for single-error detection and correction (which is shown to be a unique procedure) and multiple error detection. A formula of cryptographic security is obtained for such a digital signature. [ABSTRACT FROM AUTHOR]

This paper introduces the concept of radical-free pseudonormalized Φ-functions, which allows one to describe constraints on minimum and maximum allowable distances between two-dimensional φ-objects. Translations and rotations of φ-objects in a two-dimensional Euclidean space are allowable. The theorem on the existence of a radical-free pseudonormalized Φ-function for a pair of arbitrary-shaped φ-objects whose frontiers are formed by the union of line segments and circular arcs is formulated. An efficient algorithm is proposed to derive pseudonormalized Φ-functions. [ABSTRACT FROM AUTHOR]

This paper proposes an efficient parallel implementation of the Ramalingam algorithm for dynamically updating the single-sink shortest-path subgraph of a directed graph after adding an edge to the graph with the use of a model of associative (content addressable) parallel systems with vertical processing (the STAR machine). An associative version of this algorithm is described as the InsertNewArc procedure whose correctness is proved. We also consider the main advantages of the associative version of the Ramalingam incremental algorithm. [ABSTRACT FROM AUTHOR]

The paper analyzes the features of the presentation of parallel algorithms for the multiprocessing of vector data arrays by difference slices in the basis of a modified Glushkov SAA. [ABSTRACT FROM AUTHOR]

This paper analyzes nonlinear balance models of intersectorial ecological-economic interaction and proposes new approaches to solving them. The efficiency of these algorithms and possibility of using them in practice are substantiated. [ABSTRACT FROM AUTHOR]

This paper develops methods for calculating the semantic similarity (closeness)-relatedness of natural language words. The concept of semantic relatedness allows one to construct algorithmic models for the context-linguistic analysis with a view to solving problems such as word sense disambiguation, named entity recognition, natural language text analysis, etc. A new algorithm is proposed for estimating the semantic distance between natural language words. This method is a weighted modification of the well-known Lesk approach based on the lexical intersection of glossary entries. [ABSTRACT FROM AUTHOR]