Русский язык
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.
Current issue from 09.2016 - volume 20 issue 3 dedicated to the anniversary of Academician V.B. Kudryavtsev (PDF)
Low-density parity-check (LDPC) codes were first proposed by R. Gallager in [1], and were later rediscovered by D. McKay and R. Neale ([2]). They demonstrate error-correction capabilities close to the Shannon limit. In addition, they allow the implementation of a codec with a high degree of parallelism, which means the possibility of efficient software and hardware implementation. Therefore, LDPC codes are used in many areas: hard drives, wireless communications, etc. In this paper, an efficient coding algorithm is proposed for the case of a parity-check matrix of a certain type with incomplete rank. In [3], another efficient algorithm based on the Chinese remainder theorem is proposed.
Keywords: coding, LDPC codes, quasi-cyclic codes, Smith normal form.
This article proves that there is no algorithm by which a basis could be extracted from a finite complete system of polynomial functions with integer coefficients.
Keywords: polynomial, algorithm, unsolvability, completeness problem, basis, superposition operations, functional system, Hilbert's 10th problem.
The report is devoted to specifying logical processes by means of propositional calculuses. It will be discussed how logical systems are specified by calculuses, conditions for the existence of such a specification, properties of the lattice of logical systems generated by calculuses, conditions for the solvability of the inference problem for propositional calculuses, and the complexity of this inference.
Keywords: propositional calculuses, logical systems, inference problems, complexity of inference.
This article is devoted to the conditional testing of the Cardot scheme for three and four variables. It was found that for the Cardot scheme of four variables the minimal complete diagnostic conditional test has a length of 14, and for the Cardot scheme of three variables - 8.
Keywords: Cardot scheme, test, testing, test length, conditional diagnostic test.
The paper studies the relative influences of the variables of a Boolean function. The set of Boolean functions is divided into \[\tau-Inf\]-equivalence classes depending on the maximum relative influence of the variables. The lower and upper estimates of the number of \[\tau-Inf\]-equivalence classes for threshold functions are given. They are equal to \[2^{n/2}\] and \[n2^{2n}\].
Keywords: threshold functions, influence of variables of a Boolean function, relative influence of variables of a Boolean function, \[\tau-Inf\]-equivalence classes.
The paper considers the problem of covering a family \[A\] of natural numbers with a minimum number of arithmetic progressions with a ban on covering elements of another finite family \[B\]. More precisely, we are interested in finding the minimum number \[f(A)\] of elements in the family \[B\] that are sufficient to make the covering of the family \[A\] the most complex, i.e. having the maximum possible number of arithmetic progressions. The corresponding upper and lower bounds on \[f(A)\] are given depending on the cardinality of the family \[A\].
Keywords: arithmetic progression, natural numbers, covering complexity.
The article is devoted to the power complexity of flat circuits implementing functions from closed classes. A flat circuit can be represented as a laying of a circuit of functional elements on an integer lattice on a plane in such a way that the wires are replaced by cellular elements implementing identical functions. As a measure of the circuit power, the average and maximum potential are considered, equal to the average and, accordingly, the maximum number of ones at the outputs of the circuit elements. A theorem on the order of the Shannon function of the potential for a class of monotone functions will be formulated and it will be shown how, taking this result into account, estimates of the Shannon function for other closed classes are obtained.
Keywords:flat circuits, cellular circuits, circuit activity, circuit cardinality, Shannon function, Post classes, monotone Boolean functions.
A system of linear polynomials with integer coefficients is considered. A scheme for efficient calculation of this system is proposed. The calculation scheme allows eliminating redundancy in the presentation of the initial data, as well as simplifying the calculations by eliminating the multiple calculations of the same values with the same functionality as without using the scheme. An example of application of the proposed calculation scheme is given.
Keywords:linear polynomial, computational complexity, classification.
Let \[k > 2\], \[E_k = \{0, 1, \ldots, k-1\}\]. Denote by \[P_k\] the set of all finite-place functions on \[E_k\]. Due to A. V. Kuznetsov's theorem, for any \[k\] in \[P_k\] there are finitely many precomplete classes. All of them were described in 1965 by I. Rosenberg in terms of preserving some predicates. In this paper, a number of statements about embedding some intersections of precomplete classes into some (other) precomplete class are proved. Such statements help to construct the so-called intersection lattice for precomplete classes, which is, in a certain sense, the \["skeleton"\] of a continuous (for \[k > 2\]) lattice of closed classes in \[P_k\], in order to obtain a finite classification of closed classes. For \[k = 3\] the intersection lattice of precomplete classes in \[P_k\] was constructed by the author earlier, while for all \[k > 3\] the problem remains open.
Keywords: many-valued logic, precomplete classes, closed classes, lattice, intersection lattice.
The article presents studies of the problem of representing the number of Boolean solutions of a linear equation of many variables with integer coefficients as a function of the binary expansion of these coefficients.
Keywords:equation in integers, binary expansion.
The paper proposes a method for synthesizing non-redundant circuits from functional elements in the Zhegalkin basis that implement arbitrary Boolean functions without additional inputs and outputs and allow for relatively arbitrary constant faults at the inputs and outputs of elements, single verification tests, the length of which is limited from above by a constant of 16.
Keywords: circuit from functional elements, verification test, constant fault, Shannon function, easily tested circuit.
One of the areas of study of discrete functions is the study of functional systems: sets of functions and sets of operators defined over these functions. In particular, functional systems are actively studied in which, in contrast to classical systems over a set of \[k\]-valued functions, generalizations of functions of \[k\]-valued logic are considered: partial functions, multifunctions, and hyperfunctions. Hyperfunctions are functions defined on a finite set \[A\] and taking as their values all nonempty subsets of the set \[A\] with respect to the superposition operator. In addition to the superposition operator, stronger closure operators are of interest, providing a nontrivial classification of functions. For example, for hyperfunctions, a completeness criterion for the branching operator by the equality predicate was previously obtained. Also known strong operators are the parametric and positive closure operators. All closed classes on the set of Boolean functions are known for them.
Keywords: closure, parametric closure, hyperfunction, completeness criterion, superposition.
This paper considers the problem of stabilization of Boolean networks, namely, the question of the presence of point attractors in an asynchronous Boolean network. A stabilization criterion has been found depending on the choice of Boolean network components: graph, Boolean functions, initial state, update order.
Keywords: Boolean networks, stabilization.
The paper considers algebraic systems whose elements are mappings realized by finite automata. In terms of the richness of examples and expressiveness of means, automata are sometimes not inferior to classical algebraic systems. Semigroups, groups, rings, as well as functional systems of automata have made it possible to solve a number of difficult mathematical problems. These constructions are given in the book along with examples of specific automata. The book is intended for students, postgraduates, teachers and researchers.
Keywords: finite automaton, algebraic system, group, functional system.
The authors introduce the concept of extended superposition as a superposition with the obligatory presence in the system of \["delay"\] and the Sheffer function. For extended superposition, the authors managed to prove the algorithmic solvability of the expressibility problem for a wide class of automata functions: constant automata functions, Medvedev group automata functions, and also linear automata functions, which in the case of ordinary superposition was algorithmically unsolvable.
Keywords: automaton, deterministic function, superposition.
An automaton function (when all input words are supplied) generally does not produce some output words, and produces some of them repeatedly. If we associate a word with the number of its occurrences at the output of the automaton, a new function arises, called by the authors the histogram function of the automaton, and the set of output words itself becomes a multiset. The properties of such multisets are studied.
Keywords: automaton, deterministic function.
This paper shows that the optimal output function can be obtained by an algorithm that is used in proving the predictability criterion for generally regular super-events in a multi-valued alphabet, and that the degree of super-event prediction by the automaton obtained by using this algorithm can differ from the optimal by any number of times.
Keywords: predictive automaton, super-event prediction, automaton cycle.
The property of an automaton to contain a given regular set in the set of its output words is studied. It is established that this property can be verified by studying the structure of the set of output words of an automaton of limited length.
Keywords: abstract finite automaton, regular event, regular expression, generator, algorithmic decidability.
This work is devoted to the study of \["linearly realizable"\] automata, that is, automata with the property that there exists a coding for which the Boolean operator generated by the coding is linear. The paper presents a criterion for the linear realizability of an automaton. Also, the lower and upper bounds for the number of linearly realizable automata are given.
Keywords: automata theory, automaton, transition systems, permutation, substitution, coding, complexity.
The features of the K, S, and A-closure operators in the class of linear-automaton functions over a field of two elements are studied.
Keywords: finite automaton, linear-automaton function, composition operations, superposition operations, closed classes, maximal subclasses.
This work is the result of the analysis of the experience of creating distance learning systems by the staff of the \[\mbox{MaTIS}\] department of M. V. Lomonosov Moscow State University. Work on the creation of intelligent learning systems has been carried out at the department since 1991. During this time, learning systems in various subject areas have been developed, as well as a tool (author's system) to ensure the process of creating learning systems, see, for example, [2].
Keywords: distance learning, programming, practical training on a computer.
This paper proposes a formalization of M.M. Botvinnik's ideas, which reflect the peculiarities of human logical thinking. The approach is based on the concept of a chain as a sequence of actions aimed at achieving a goal. The existence of logical connections between chains leads to the representation of a chess position as a set of chains. A formal model for describing a position and an algorithm for heuristically finding an optimal representation are proposed.
Keywords: chess position, chain, optimization, mathematical modeling, cognitive processes.
A classification structure of hypothetical evolution of intelligent systems is proposed, based on the post-nonclassical information-evolutionary approach to system analysis and modeling of objective reality, the attribute-ingredient concept of information and the concept of controlled evolution of natural language. New subclasses of the expanded class of intelligent systems are introduced: autoanagenic, consential and psychoeinic systems.
Keywords: knowledge, information, modeling, autoanagenic systems, intelligent systems, consential systems, psychoeinic systems, phenomenology, evolution.
The article discusses a mathematical model of dynamic databases that processes three types of queries: search, insertion, and deletion. It is based on the interaction of an information graph and a finite deterministic automaton. The model allows solving dynamic search problems and assessing the complexity of their solution. In addition, the model allows building infinitely parallelizable solution algorithms.
Keywords: dynamic databases, information graph, automaton, query flows, parallel data processing.
An algorithm for synthesizing discrete control systems in the form of programmable logic matrices is considered. Programmable logic matrices are constructed based on polynomial normal forms of Boolean functions. For discrete control systems, the result on a certain subset of all input values is important. Such systems can be modeled using partially specified Boolean functions. It is proposed to use genetic algorithms to find polynomial representations of such functions that are close to minimal.
Keywords: logical synthesis, polynomial normal form, genetic algorithms, Boolean functions.
The paper considers an approach to recognizing visual images based on constructing image codes that are invariant with respect to geometric transformations.
Keywords: visual image recognition, image coding.
The relationship between generalizations of formal concepts to the case of fuzzy contexts is studied. Crisply generated fuzzy formal concepts (R. Belokhlavek et al.), proto-fuzzy concepts (O. Kridlo and S. Krajci), pattern structures (S. Kuznetsov and B. Gunter) are considered. The established correspondences between proto-fuzzy and crisply generated formal concepts allow us to reformulate the problems and use the previously obtained criteria and properties.
Keywords: fuzzy formal concepts, proto-fuzzy formal concepts, crisply generated formal concepts, interval formal concepts.
The work is devoted to the presentation of the results of computer modeling of logical processes in the logical system \[«Iskra»\]. The issues related to the training of computer problem solvers and automatic synthesis of techniques were studied.
Keywords: intelligent system, self-training, logical system, computer problem solver, automatic synthesis of techniques.
It is known that neural circuits implement piecewise constant functions. To ensure that neural networks comply with the McCulloch-Pitts model, it is necessary to allow the use of only \["solid neurons"\] In this case, the output of the neural circuit will take a value from the set \[\{0,1\}\], and the function implemented by the circuit will be an indicator function. The paper proves that an arbitrary indicator function can be represented by neural networks with no more than three layers. A criterion for the representability of indicator functions by two-layer neural networks is formulated.
Keywords: neural network, neural circuit, nonlinear depth, McCulloch-Pitts model.
The problems of automatic analysis of tactile images recorded instrumentally during endoscopic operations are relevant for medicine. An important element of this analysis is the automatic detection of inhomogeneities. In 2016, R. F. Solodova and co-authors proposed three methods for automatic detection of inhomogeneities based on the instrumentally recorded results of one press of a tactile mechanoreceptor on the area under study. The purpose of this study is a theoretical comparison of the consistency of these methods. More specifically, the question is studied whether the fact that one method has defined an area as non-uniform implies that other methods will also define this area as non-uniform.
Keywords: tactile images, automatic analysis, detection of non-uniformities, medical tactile endosurgical complex, tactile mechanoreceptor.
The main problems of the development of computer-based learning systems are considered. It is shown that the key task and growth point for such systems is the personalization of the learning process. The necessary conditions for the personalization of learning are formulated. The results of experiments with data accumulated in the learning process are presented. The main provisions are illustrated using the Uchi.ru platform as an example.
Keywords: computer learning systems, personalization, clustering, ranking.
The paper examines the complexity of solving the following problem. A system is given in which access control is based on the RelBAC model introduced in the articles by V. A. Vasenin et al., and a pair (subject, object). It is required to determine whether there are conditions under which a subject can obtain a given access to an object. We show that in the general case this problem is NP-complete. If the maximum path length is bounded by a constant, then the problem becomes polynomial.
Keywords: information and analytical systems, NP-completeness, graphs, information security.
The paper formulates a criterion for the polynomial completeness of a quasigroup of prime order, and also shows that the polynomial completeness can be tested in time polynomial in the order.
Keywords: quasigroup, polynomial completeness, algorithmic complexity.
The paper examines the model of long-term profiles of active audit systems proposed by A. V. Galatenko, A. E. Lebedev and I. N. Emelianov in 2009. It is proved that the sufficient condition for profile convergence proposed by the authors of the model is a criterion.
Keywords: intrusion detection, consistency of long-term profiles.
The proposed work examines the problem of synthesizing spatially distributed control systems in the context of the existing level of development of communication systems and computing devices, substantiates the advantage of the agent-based approach to the system of spatially distributed control systems. Special attention is paid to some aspects of ontological support and design of distributed multi-agent control systems.
Keywords: control system, agent-based approach, Internet of Things.
The secure C\[_s\] programming language and the operating system created by the compiler of this language provide complete protection against malware and cyber attacks. The system consisting of C\[_s\] and its operating system is open only to programs created by the C\[_s\] compiler or that meet the C\[_s\] standards. There is a robot that converts all existing programs to these standards.
Keywords: information security, programming languages, malware, cyber attacks.
The paper presents a model of cryptographic protocols based on the theory of message-passing processes. It is shown how this model can be used to solve problems of verification of cryptographic protocols (i.e., constructing mathematical proofs of statements that cryptographic protocols have given properties). As an example of such properties, the properties of integrity and secrecy are considered. These properties are defined formally as certain relations expressed in terms of the observable equivalence of message-passing processes. Examples of verification of these properties for some cryptographic protocols are shown.
Keywords: cryptographic protocols, verification, observable equivalence.
A parallel implementation of the breadth-first search algorithm on a graph developed at T-Platforms is described. The key feature is the optimized internal representation of the graph, which allows for ordered communications between computing processes and division of execution into threads within each process. A description of the optimization by direction and its multi-threaded implementation is given. The results of a performance study of the developed implementation are also presented.
Keywords: distributed computing, parallel computing, graphs, breadth-first search.
In mathematical modeling of electrohydrodynamic phenomena, the main difficulty is associated with the inclusion of physical parameters in the model, information about which is very uncertain. There is a need to develop mathematical models with a minimum set of \["effective"\] unknown variables and specified parameters. The paper describes three models of increasing complexity and presents the results obtained within each of them.
Keywords: electrohydrodynamics, electric field, weakly conducting media, mathematical models, volumetric electric charge, electrochemical reactions, electrification.
The paper studies the problem of unification of two systems, each of which implements the take-grant security policy. The unification is called safe if no new accesses appear within each of the unified systems. A criterion for the safety of the unification is proposed, as well as an easily verifiable sufficient condition for safety.
Keywords: formal security models, take-grant model, safe unification.
The paper discusses the depth of the hardware (circuit) implementation of the ZUC stream cipher and ways to minimize it. First, a simple implementation of the algorithm is given. After that, ways to optimize this implementation are shown.
Keywords: stream ciphers, circuit depth optimization.
06.2016 - Volume 20 Issue 2 (PDF)
On July 4, 2016, the founder and permanent editor-in-chief of the journal "Intelligent Systems", Doctor of Physical and Mathematical Sciences, Professor of the Mechanics and Mathematics Department of the Lomonosov Moscow State University Valery Borisovich Kudryavtsev turned 80 years old.
The solution to the problem of recognizing movements performed on an object has a wide range of applications in robotics, mobile device manufacturing and mobile applications. It is an example of a typical classification problem and in many cases can be solved by a relatively simple analysis of instrument readings: accelerometer, gyroscope, magnetometer and others. However, in cases where the graphs of instrument readings for different gestures are visually indistinguishable and superficial analysis does not yield meaningful results, it is necessary to use machine learning methods. The article considers one of such problems and highlights the topic of a general methodology for solving classification problems.
Keywords: machine learning, data analysis, gesture recognition, Hidden Markov Models, accelerometer
The paper considers the problem of creating a computer program that performs syntactic analysis of legal texts in Russian. This program should accept the text of one sentence as input, and should output a syntax tree constructed based on this sentence, the vertices of which contain the words of the sentence, and the edges are assigned syntactic relations between the words of the sentence. The paper presents rules that allow syntactic analysis to be carried out in the presence of morphological information about the words of the sentence.
Keywords: syntactic analysis, syntax tree, morphological characteristics, rules.
The article proposes an architecture of a hardware reconfigurable on-the-fly BCH decoder.
Keywords: hardware implementation, structural automata, error-correcting codes, BCH codes.
The article presents a result on finding the minimum number f(n) of arithmetic progressions necessary to obtain in union all natural numbers that are not comparable modulo n with 0 and −1. Here n is an arbitrary natural number. Progressions may intersect. The exact value of the function f(n) is given, as well as a constructive partition of this subset of the natural series into f(n) arithmetic progressions.
Keywords: natural series, arithmetic progression, decomposition.
This article considers the solution of two problems: one-dimensional packing in identical containers and two-dimensional tiling of a rectangular area with a software implementation in PHP. For the first task, an approximate solution will be obtained using the heuristic BFD algorithm and the branch and bound method. For the second task, due to the specific constraints on the input data and tiling methods, the branch and bound method will be used, which allows obtaining an exact solution in an acceptable running time.
Keywords: PHP, one-dimensional packing into containers, two-dimensional tiling.
The article presents a new fingerprint verification algorithm based on finding the maximum path in a graph. The central idea of this approach is to find the maximum path in a specially constructed acyclic graph. The average speed of the verification algorithm is 100 comparisons per second (Intel Core i5-2500 CPU @3.30 GHz 3.30GHz, 4 GB RAM, Windows 7 OS).
Keywords: fingerprints, verification, minutiae, graph, maximum path in graph.
The paper considers the problem of parameter-efficient decoding of linear functions of k-valued logic within the framework of the exact decoding model. Exact values of the decoding complexity are obtained for a small number of significant variables. Upper and lower bounds are obtained for the general case for two types of queries: for value and for comparison. As the number of variables tends to infinity, the order of complexity of decoding is obtained for both types of queries.
Keywords: exact decoding of functions, linear functions of k-valued logic, queries for value, queries for comparison.
The article consists of two parts. The first part considers the problem of verifying the uniqueness of alphabetic decoding in the class of regular languages. A number of restrictions on these languages are given, the implementation of which allows us to construct a new decision algorithm and significantly improve its complexity in comparison with the complexity of a similar algorithm from [4]. The second part of the article is devoted to the problem of verifying the uniqueness of alphabetic decoding for the class of regular languages with a polynomial growth function. The results obtained in the first part of the article form the basis of an algorithm that solves the problem under consideration. A technique has been developed that allows us to implement the assumptions given in the first part of the article for languages with a polynomial growth function.
Keywords: regular languages, polynomial growth function, alphabetic decoding.
The paper considers the problem of simultaneous minimization of the area, power and depth of flat circuits implementing partial Boolean operators. The maximum potential is considered as a measure of power; it is equal to the maximum number of outputs of elements that produce one on a given input set of the circuit, where the maximum is taken over all input sets. It is shown that with minor restrictions on the domain of the operator, there exists a circuit with an optimal order of power, area and depth. In particular, for everywhere defined operators with n inputs and m outputs, the order of power is \[({m\sqrt{2^n}})/({\sqrt{min(m,n)}})\], the order of depth is \[max(n,log_2m)\].
Keywords: gate arrays, flat arrays, cellular arrays, power, depth, Shannon function, upper bounds, Boolean operators.
The paper proposes new analytical formulas for phase equilibrium constants that take into account the influence of fluid composition and more accurately convey the phase behavior of multicomponent solutions. The approach allows constructing a thermodynamically consistent model convenient for numerical modeling of multicomponent filtration: the required computing resources are reduced, the reliability of calculations is increased.
Keywords: phase equilibrium constants, EOS, phase transition.
This paper is a continuation of the article [1] and uses the concepts and notations introduced in [1]. The paper presents the basic concepts of the theory of probabilistic Moore automata with numerical output and the theory of probabilistic languages. New proofs are given of classical results of the theory of probabilistic automata related to the equivalence and reduction of probabilistic Moore automata with numerical output, as well as to the regularity of probabilistic languages.
Keywords: probabilistic automata, probabilistic languages.
The set of words whose frequencies of adjacent letter pairs form the same matrix is a formal (bigram) language. The article describes matrices corresponding to regular and context-free bigram languages.
Keywords: bigram language, frequency matrix, adjacent letters, Euler cycles.
The paper studies how the class of automata that are "simply" realizable are related to the class of automata that have the property that all operators defined by all possible codings are different. It is shown that the specified classes of automata have a non-empty intersection, and none of the classes lies in the other.
Keywords: automaton, coding, maximality property.
03.2016 - Volume 20 Issue 1 (PDF)
The article is devoted to the optimal strategy for managing credit and deposit rates in order to maximize bank capital. A dynamic system with discrete time and a number of regulatory restrictions is used to describe the Bank's work. The model contains expert hypotheses about market behavior, which allows it to be used in the absence of sufficient statistics, including when serious changes occur in the country's economy. The main stages of constructing the model are presented, the behavior of bank rates in two periods is studied: in normal times and during a crisis.
Keywords: bank, bank rates, management, modeling.
I.A. Rachkovskaya On the issue of ensuring traceability in the context of non-industrialization
The article shows the impact of neo-industrialization or the new industrial revolution on ensuring traceability in the supply chain. The main trends in the development of Industry 4.0 and their impact on market participants are considered. The traceability procedure is considered using the example of food industry enterprises.
Keywords: neo-industrialization, Industry 4.0, Internet of Things, traceability, supply chain management.
Entropy-linear programming problems often arise in various applications (transport problems, chemical reaction studies, etc.). Such problems are usually formulated as entropy maximization problems (or minus entropy minimization problems) with affine constraints and linear inequality constraints. The paper investigates a method for solving such a problem based on solving a dual problem with recovery of the solution to the direct problem: each point in the dual space calculated by the method is assigned a certain point in the direct space. For this method, an upper bound for the number of iterations required to achieve a solution with a given accuracy is obtained. The presented method is also applicable to a wider class of strongly convex functionals with a similar admissible set.
Keywords: entropy-linear programming, fast gradient method, dual problem, primal-dual method.
The paper examines the depth of hardware (circuit) implementation of the Kuznechik block cipher. A comparison of the depth of implementation of the Kuznechik algorithm with other common block cipher algorithms is also carried out.
Keywords: circuit depth optimization, block ciphers.
The article discusses the mathematical model and methods of verification of functional programs. The main attention is paid to the theory of functions calculated by functional programs (these functions are called the smallest fixed points of functional programs). The main methods of verification of functional programs are also presented: the method of computational induction and the method of structural induction.
Keywords: verification of functional programs, method of computational induction, method of structural induction.
This article discusses the application of the two-dimensional packing algorithm when cutting rectangular panels of arbitrary sizes from standard rectangular panels of fixed sizes (sandwich panels). It is necessary to determine the minimum number of sandwich panels necessary to produce all the required panels. The solution to this problem will be considered using the HBF algorithm with implementation in the PHP programming language.
Keywords: PHP, two-dimensional packing, HBF algorithm
The paper investigates the relative influences of variables of a Boolean function. The lower and upper bounds of the maximum relative influence for threshold functions of n variables are found depending on n. They are equal to \[1/n\] and \[({2^{n-1}})/({2^{n-1}+n-2})\]. A division of all threshold functions of a four-dimensional space into classes is given depending on the maximum relative influence of variables.
Keywords: threshold functions, influence of variables of a Boolean function, relative influence of variables of a Boolean function, τ -regular Boolean functions.
The article considers the estimation of one of the parameters of finite automata — the degree of distinguishability of states. In this paper, we consider sets of finite automata with arbitrary output and transition functions. The states of a finite automaton are called r equivalent if the corresponding automaton functions are the same on words of length r. The states are called r-distinguishable if they are (r–1)-equivalent and the corresponding automaton functions differ on words of length r. The maximum degree of distinguishability of the states of an automaton is called its degree of distinguishability. In the absence of restrictions, an achievable upper bound for the degree of distinguishability is known, equal to s − 1, where s is the number of states of the automaton. In each of its states, the finite automaton implements a function whose arguments (whose values) are elements of the input (output) alphabet. The number of such different functions will be called the static functionality of the automaton. Automata with a given static functionality are considered. An achievable upper bound for the degree of distinguishability is obtained, equal to s + 1 − F, where F is the static functionality of the automaton. The set \[\{s_1, s_2, . . . , s_F\}\], where \[s_i\], \[1\leq {i}\leq {F}\], is the cardinality of the i-th 1-equivalence class will be called the spectrum of the finite automaton. The dependence of the maximum degree of distinguishability of the states of a finite automaton on its spectrum is shown.
Keywords: finite automaton, automaton function, distinguishability of states.
The dynamic identical object search problem (DIOSP) is considered. This paper presents a finite IOG with visibility radius one and branching degree two, processing an arbitrary flow of queries. This is the smallest possible IOG in terms of branching degree with visibility radius one, solving the stated problem.
Keywords: dynamic databases, information graph, automaton, query flows.
In this paper, a lower bound for the number of vertices of (t,s)-biregular graphs of girth 6 for 2 < t < s is proved. An algorithm for constructing (t,s)-biregular graphs is devised. It is proved that for certain values of t and given values of s, the "(t,s)-construction" algorithm constructs a graph of girth 6.
Keywords: biregular graph, bipartite graph, girth, LDPC code.