Русский
12.2016 - Volume 20 Issue 4 (PDF)
The paper is devoted to the issue of the complexity of restoring a partial order on a finite set, if it is known that the partial order has some predetermined properties. A computation model is considered in which complexity is understood as the number of comparisons required to restore the partial order. Classes of partially ordered sets are studied for which the problem of restoring the order is solved in less than a quadratic number of comparisons relative to the number of elements in the set.
Keywords: partial order, finite set, order restoration, sorting, comparison.
The article describes the use of Kalman filter to reduce the error in estimating the position of an object during detection and to extrapolate the position of an object in the next frame.
Keywords: Kalman filter, image processing, object tracking.
Methods for solving unconstrained minimization problems are proposed, in which the iterative process is restarted according to a certain rule after a predetermined number of steps (restart). The results of a numerical experiment comparing the efficiency of the proposed methods with methods without restart are presented.
Keywords: unconstrained minimization, restart, relaxation, modified conjugate gradient method, gradient method, Fletcher-Reeves method.
The paper studies the possibility of computing arithmetic functions on the integer line by small groups of automata. We will say that the group of automata \((W_1, W_2)\) is in the \(a\)-arrangement (\(a\geqslant 0\)) if the automaton \(W_2\) is \(a\) divisions to the right of the automaton \(W_1\). We will say that a collective of automata \((W_1, W_2)\) computes an integer function \(f(x)\) if for any non-negative integer \(x\), starting from the \(x\)-arrangement, the collective stops in the \(f(x)\)-arrangement. Depending on the constraints on the mobility of the automata of the collective, strong computability of functions by a collective of automata, weak computability, and simple computability are defined. The paper completely describes the class of integer functions computable by collectives of two automata. This class is a composition of "periodic" functions and functions of the form \(f(x)=x+c\). It is shown that the classes of all functions computable by collectives of two automata, weakly computable by collectives of two automata, and strongly computable by collectives of two automata coincide. It is also shown that the class of functions computable by groups of three automata is much wider.
Keywords: automata group, labyrinth, computability, integer functions.
New generalized versions of Strassen's "\(r\)-fast" convergence for a sequence of random variables are proposed. Necessary and sufficient conditions for "\(\Phi\)-fast" convergence of a sequence of sums of random variables with discarded extremal terms are established.
Keywords: random variables, convergence, random walk, tail probabilities, law of large numbers, "\(r\)-fast", "\(\Phi\)-fast", ordinal statistics, convergence rate.
Mappings are constructed between automaton models of information systems described in the works of Moskowitz-Kostich and Grusho-Shumitskaya, preserving security properties.
Keywords: automata models, covert channels, non-influence model, probabilistic non-influence.
The paper describes the methodology for constructing models of data structures, the goals, objectives and results of developing a software package for managing medical data on research into treatment methods for \(\beta\)-thalassemia. The purpose of developing and implementing an original software package for managing medical data on research into treatment methods for \(\beta\)-thalassemia is to accumulate, store and analytically process clinical and laboratory diagnostic data of patients with the possibility of subsequently applying pharmacoeconomic analysis tools to them. The main result of the development and implementation of the software package is the formalization and automation of research processes in the field of treatment methods for this hematological disease in scientific and clinical institutions of the Russian Federation healthcare system.
Keywords: medical informatics, information systems and technologies in healthcare, scientific and clinical research, hematological diseases, treatment methods for \(\beta\)-thalassemia.
This work is devoted to the semantic analysis of text written in natural language and recognition of named entities. The main goal of the study was to compare latent Dirichlet allocation and latent semantic analysis for identifying elements of human appearance in text. The completeness of information retrieval was chosen as a comparative characteristic of the methods.
Keywords: named entity recognition, LSA, LDA, coreference resolution, human appearance recognition.
The article considers the problem of access control to objects of information systems for managing scientometric information. A relational model of logical access control to objects of such systems is presented, which has a number of properties that are important in the context of the task at hand and that other models of logical access control do not have.
Keywords: information security, scientometrics, access control, relational model.
The paper proposes an algorithm for localization and recognition of objects in images based on neural networks with deep architectures. The neural network architecture proposed in this paper solves both problems of localization and recognition in a single pass of calculations. This allows all calculations to be performed on graphics processors and significantly speeds up localization and recognition.
Keywords: pattern recognition, object localization, neural networks, deep learning.
A hypothesis on the nature of the dependence of the total length of contours in a halftone image on the threshold of the contour detection method is formulated and experimentally confirmed. Based on this model, an original heuristic threshold selection method is proposed, ensuring high quality of contour detection according to multiple expert assessments.
Keywords: halftone images, contour detection, Canny method, Sobel method, L-curve, curvature assessment, adaptive threshold, noise resistance.
The paper considers self-comparison matrices of a one-dimensional signal (in particular, speech). A method for nonlinear stretching of these symmetric matrices is proposed to find the optimal distance between them in terms of signal similarity.
Keywords: one-dimensional signal, self-comparison matrix, nonlinear stretching.
Galois correspondences for classes of discrete functions generated by the conservation relation between functions \(f\) on the set \(A\) and sets \(H\) of functions \(f:Q\to A\) for an arbitrary set \(Q\) are a convenient tool for studying a number of abstract and applied problems. In this paper, one of the main problems of social choice theory is formulated in the language of Galois functional correspondences and a convenient characterization of symmetric classes of decision rules without the Arrow property is proposed.
Keywords: Galois correspondence, closed class, clone, Arrow property.
The article describes a formalized representation of the structure of medical data in accordance with the objectives of scientific and clinical research in the field of hematopoietic stem cell transplantation. Based on the representation of the structure of medical data, a software package for accumulating and storing clinical and laboratory diagnostic data of patients has been developed for the purpose of subsequent computational experiments and analysis of the results of applying this treatment method.
Keywords: hematopoietic stem cell transplantation, scientific and clinical research, medical and laboratory information systems, medical informatics.
The article describes an attack on the GOST 34.12-2015 cipher with a block length of 128 bits, implemented by introducing errors into the encryption process. It is shown that by analyzing the introduced errors with known replacement blocks, the key value can be calculated on average in \(2^{13}\) fault injections, using about 128 KB of plaintext.
Keywords: cryptanalysis, GOST 34.12-2015, error injection attack, attack on a block cipher.
The article describes a software complex developed by a research team for the construction and analysis of a terminology system. The project is an expert system containing a thesaurus dictionary (TSReader), a system for identifying and classifying terms (TSBuilder), and a terminology database. Automated creation of a terminology system is achieved through the use of a heuristic algorithm for identifying terms and a modified Rosenblatt perceptron for classifying terms.
Keywords: text mining, neural network modeling, term system modeling, automated term identification, automated term categorization.
The problem of implementing Boolean functions by initial Boolean automata with constant states and \(n\) inputs, \(n \geqslant 1\) is considered. All sets of maximum power, consisting of Boolean functions, which can be implemented by one automaton of this type with two or three states, provided that an arbitrary order of supplying sets of values of input variables to the automaton inputs is possible, are found.
Keywords: Boolean function, initial automaton, implementation of Boolean functions.
This article considers the issue of constructing a mathematical model of LED marker noise to improve the accuracy of the motion capture problem, which is based on the principles of pattern recognition. The algorithm for creating a mathematical model is based on synthesizing an artificial LED marker with the addition of Gaussian noise. To evaluate the prototype of the mathematical model, the method of minimizing the standard deviation functional was chosen. The results are visually presented in histograms.
Keywords: pattern recognition, motion capture, mathematical model of noise, synthesizing an artificial LED.
New capabilities of using the recursive construction of plateaued Boolean functions with a step of 3 variables with intersecting carriers of the spectrum of generating functions, constructed earlier in [6], providing stability growth, are presented, a new example of initial functions is given.
Keywords: Boolean functions, correlation immunity, stability, plateauedness, recursive constructions.
In this paper, a protocol for generating a common key using a group of matrices over a finite field is proposed. As one of the stages of the protocol, a linear factorization attack is used, recently proposed by V. A. Romankov to compromise protocols in which the platform is a linear group. The resistance of the proposed cryptosystem against various known attacks is analyzed.
Keywords: matrix group over a finite field, non-commutative cryptography, public-key cryptography, shared-key generation protocol, linear factorization attack.
Based on a systems approach, mathematical methods for studying various electrohydrodynamic phenomena are described. Three models with a minimal set of "effective" variables and specified parameters and some results obtained within the framework of each of them are discussed.
Keywords: electrohydrodynamics, electric field, weakly conducting media, mathematical models, volumetric electric charge, electrochemical reactions, electrification.
The paper presents a mathematical discrete model of the process of lung self-cleaning from various substances, both brought there from outside and obtained due to the life and activity of the organism. Shannon functions of the lung self-cleaning time are presented both in a healthy case and in the case of two types of pathologies.
Keywords: lungs, self-cleaning process, automata, Shannon function.
For superposition, an example is constructed that does not extend to a precomplete class, a set of automata.
Keywords: automaton, superposition, precomplete class.
The author previously proved that pushdown automata store periodic sequences, and provided an upper bound for the maximum period length that is exponential in the automaton characteristics. For the case where the pushdown alphabet consists of one symbol, the author managed to lower the overall bound to a quadratic one. In the case of an alphabet consisting of at least two symbols, the author proved that it is impossible to significantly lower the upper bound. This paper provides an improvement on the previously proposed lower bound. The new proof is noticeably simpler than the previous construction.
Keywords: pushdown automaton, deterministic function, periodic sequences.
The paper considers the main results related to the decomposition of graphs into unions of trees, pseudotrees, and star trees. Own results on the chromatic number of these graphs are presented.
Keywords: arborescence, chromatic number.
Work on the theory of abstract clones. Binary predicates on a \(k\)-element set and operations on these predicates are studied. A list of operations on binary predicates is given, the closure with respect to which for \(k \in \{2, 3\}\) is equivalent to the closure with respect to all primitive positive formulas. For \(k \geqslant 4\), it is shown that the closure with respect to the indicated operations is strictly weaker than the closure with respect to all primitive positive formulas.
Keywords: clone theory, binary predicates, binary relations, operations on predicates, primitive positive formulas, closure operator, \(k\)-valued logic.
The class of linear 2-adic automata with composition operations is considered. An algorithm for checking the completeness of finite subsets of such automata is obtained. All maximal subclasses are found, the number of which turned out to be countable.
Keywords: finite automaton, p-adic number, linear 2-adic automaton, composition operations, feedback, completeness problem, completeness checking algorithm, serial binary adder, delay.