Русский
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.