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