Русский язык
12.2015 - Volume 19 Issue 4 (PDF)
The article is devoted to the logic of the human endocrine system using the example of the functioning of α- and β-cells of the pancreas. Several levels of abstraction for this system are presented. The interactions of α- and β-cells of the pancreas with each other, as well as with individual organs and peripheral tissues of the body are considered. In the state space of this system, "alarm states" are identified.
Keywords: endocrine system, pancreas, α-cell, β-cell, automata modeling in biology.
This article provides a brief introduction to classifier ensembles in machine learning and describes an algorithm that improves the quality of classification by recommending classifiers to objects. The hypothesis underlying the algorithm is that a classifier is more likely to correctly classify an object if it correctly predicts the labels of the neighbors of this object from the training set. The author illustrates the principle of the algorithm with a simple example and describes testing on real data.
A discrete model of CO gas exchange in human lungs has been constructed, allowing one to calculate the concentration of CO in exhaled air depending on physiological and real spirometric parameters. Formulas have been obtained for calculating the measured concentration of CO in spontaneous and forced breathing modes. An inverse problem has been formulated, the solution of which, based on the values of the measured concentration of CO and detailed spirometric data, can be used to calculate the diffusion capacity of the membrane and the alveolar volume of the lungs. Based on the obtained results, software can be developed for processing data from functional diagnostic devices for diseases characterized by impaired permeability of the alveolar-capillary membrane, such as chronic obstructive pulmonary disease, pulmonary arterial hypertension, etc.
Keywords: gas exchange, carbon monoxide, diffusion capacity of the lungs, alveolar volume, mathematical modeling.
The paper presents the basic concepts of the theory of probabilistic automata, provides new proofs of classical results of the theory of probabilistic automata related to the equivalence and reduction of probabilistic automata, and presents and proves a criterion for the feasibility of probabilistic responses by finite probabilistic automata of general form, which is a strengthening of the corresponding criterion of R.G. Bukharaev and H. Chomut ([22], [23]).
Keywords: probabilistic automata, probabilistic responses, random functions.
The dynamic identical object search problem (IOSP) is considered. In [1, 2, 3], the author showed how this problem can be solved using a multi-automaton dynamic information graph (MADIG) for any query flow. In this paper, it is shown that there is no finite MADIG with visibility radius one and branching degree two that processes an arbitrary query flow.
Keywords: dynamic databases, key search, information graph, automaton, query flows.
The paper considers a Frege system in the signature {∧, ∨, ¬}. For this system, a nontrivial lower bound for the length of the minimal output is proved.
Keywords: Frege systems, output length, lower bounds.
The paper considers the problem of decoding arithmetic sums of monotone conjunctions defined on an n-dimensional Boolean cube in the model of exact decoding using queries for the value of the function. A decoding algorithm is proposed, based on which an upper bound for the complexity of decoding is obtained. An algorithm for answering queries is also proposed, with the help of which lower bounds for the complexity of decoding the studied class of functions for a small number of monotone conjunctions were obtained.
Keywords: decoding of discrete functions, sums of monotone conjunctions.
An algorithm for restoring the correspondence between two N-point images in a finite-dimensional real Euclidean space related by a non-degenerate affine transformation is proposed. Invariants for finding the correspondence in linear time are studied.
Keywords: tracking the dynamics of images, affine transformation, multidimensional images, correspondence of key points.
The paper considers the problem of the possibility of constructing a signal routing tree with given values of signal delays to tree leaves. A class of trees with signal delay functions, on which some restrictions are imposed, is studied. An algorithm is proposed that solves this problem. For a fixed set of signal delay functions, the running time of the algorithm is polynomial in the number of tree leaves.
Keywords: Synthesis of large-scale integrated circuits, signal routing, buffer tree.
The paper considers two types of circuits made of functional elements. The problem of obtaining a lower bound for the complexity of implementing Boolean functions for one type of circuit is reduced to the problem of obtaining an upper bound for another type of circuit. An exact lower bound for the complexity of laying a binary tree graph in a cellular structure is obtained.
Keywords: Boolean functions, implementation complexity, circuits made of functional elements.
09.2015 - Volume 19 Issue 3 (PDF)
The article presents a result on finding the minimum number \[f(n)\] of arithmetic progressions needed to obtain in union all natural numbers not divisible by n. Here n is an arbitrary natural number. In this case, two cases are investigated. In the first case, the progressions can intersect, in the second they cannot. In both cases, the authors of the article managed to find the exact value for the function \[f(n)\] and provide a constructive partition of this subset of the natural numbers into \[f(n)\] arithmetic progressions.
Keywords: Natural numbers, arithmetic progression, decomposition.
The authors introduce an extended superposition of automata. An extended superposition is a superposition of automata with a fixed addition of Boolean functions and a delay. The authors proved the algorithmic solvability of the expressibility problem for Medvedev group automaton functions, as well as linear automaton functions for the Medvedev group of automata, constant automata, linear automata.
Keywords: Automaton, superposition, algorithm.
The paper considers a model of a dynamic system consisting of a graph, each vertex of which is assigned the characteristics of "favorability" and "the number of elements in a given vertex". Each element tends to get to the most favorable vertex, while the presence of elements in a vertex is an unfavorable factor. It is shown that such a system always has a limit state, a class of systems is indicated for which this limit state depends only on the number of elements in the entire graph, but not on their distribution among the nodes
Keywords: dynamic systems, stabilization, automata modeling of migration processes.
This article considers the problem of selecting a fan according to specified parameters. Air flow and pressure will be used as the main parameters. For fans whose characteristics do not allow obtaining the required air flow and pressure, the problem of changing the characteristic by adjusting the operating frequency will be considered.
Keywords: PHP, industrial ventilation, frequency regulation.
This article considers the problem of calculating the characteristics of a water cooler. Given the input parameters for air (inlet air temperature, inlet air relative humidity, etc.), coolant (direct and return coolant temperature, impurity percentage, etc.) and the cooler itself (cross-sectional area, heat exchange area, number of circuits, distance between plates, etc.), it is necessary to calculate such values as outlet air temperature, outlet relative air humidity, total battery thermal power, condensate amount, battery hydraulic resistance and other important physical characteristics.
Keywords: PHP, industrial ventilation, heat exchangers.
The paper constructs a mathematical model of recommender systems. Estimates of the number of user types in the user matrix are provided. The NP-hardness of the problems of finding a representative and enumeration of user matrices is proved in the general case, and a polynomial algorithm for finding a representative of user matrices is given in the case where the number of user types is equal to two.
Keywords: recommender systems, matrix restoration, matrix replenishment, finding a representative of user matrices, enumeration of user matrices, estimating the number of user types, NP-hardness
An example of a closed class of automata with the operation of superposition, non-extensibility to a pre-complete class, is given.
Keywords: Automaton, superposition, pre-complete class.
In this paper, an undecidable superintuitionistic propositional calculus is constructed whose axioms contain only three variables.
Keywords:Superintuitionistic propositional calculus, undecidable calculus, Minsky machine.
The paper considers the problem of exact decoding of a linear Boolean function of arity n, which essentially depends on k variables. Exact values of the complexity of decoding for small k, and upper bounds for the general case are obtained.
Keywords: exact decoding of functions, linear Boolean functions.
The article proves the criterion of predictability of general regular super-events and the criterion of predictability of super-iterations of regular events. Algorithms for constructing predictive automata are given.
Keywords: event forecasting, automata, general regular events.
The article considers the class T of thin languages of regular languages with at most linear growth function. For these languages, the concept of two dimensions dim and Dim is introduced. A result is given on the values taken by these quantities on T. In addition, the set of all realizable pairs (dimP, DimP) is found, where on P ∈ T.
Keywords: spectrum, thin languages, dimension, growth function.
The author previously proved that pushdown automata preserve periodic sequences, and an upper bound for the maximum period length, exponential in the automaton characteristics, was given. Further, for the case when the alphabet of the store consists of one symbol, the author managed to lower the general estimate to a quadratic one. In this work, it is shown that in the case when the automaton store contains at least two symbols, it is impossible to significantly lower the upper estimate, since it was possible to construct examples of automata that generate sequences with an exponential period length.
Keywords: automaton with store memory, deterministic function, periodic sequences.
Countable criterion systems of closed subclasses in classes of linear-automaton functions over finite fields are obtained.
Keywords: finite automaton, linear-automaton function, composition operations, superposition operations, feedback, completeness problem, closed subclass, criterion system, adder, delay.
06.2015 - Volume 19 Issue 2 (PDF)
Unlike CO2, with successive breath holds, with increasing time, the concentration of carbon monoxide (CO) tends to a certain equilibrium value (equilibrium concentration), depending on the content of carboxyhemoglobin in the blood. It is shown that the diffusion capacity of the lungs calculated by the rate of increase in CO concentration in the alveolar volume is approximately twice as large as their total diffusion capacity determined by the well-known "single breath" method, i.e. it corresponds to the diffusion capacity of the alveolar-capillary membrane. Based on mathematical modeling of the process of CO gas exchange in human lungs, a formula was obtained for calculating the integral measured concentration of CO in exhaled air, taking into account the effect of the dead (anatomical and instrumental) volume on the measurement results. The effect of the dead volume was taken into account under the assumption that gas exchange does not occur in it, but the CO contained in the inhaled air first enters the exhaled volume from it, and then the exhaled part of the alveolar CO. It was also taken into account that at the beginning of inhalation the dead volume is filled with the final portion of alveolar air that entered it as a result of the previous exhalation. Two models are considered: the linear model (LM), when CO gas exchange in the changing alveolar volume occurs at a constant transfer coefficient, and the elastic shell model (ESM), when the transfer coefficient during breathing changes proportionally to the membrane surface area and inversely proportional to its thickness. As a result of the analysis of the obtained results, it is shown that calculations in the ESM approximation more adequately describe the experimental data and can be used to solve the inverse problem, that is, calculating the diffusion capacity of the alveolar-capillary membrane, the alveolar volume of the lungs and the equilibrium concentration of CO, based on three values of the measured concentration of CO in different breathing modes. Thus, the proposed method, unlike "single breath", allows determining the indicated important physiological parameters without using test gas mixtures.
Keywords: gas exchange, carbon monoxide, diffusing capacity of the lungs, alveolar volume, mathematical modeling.
The paper presents the formulation of the problem, within the framework of which the Medical Protocol Description Language (MPDL) was developed, describes this language, which is essentially a specialized high-level programming language, and lists the areas in which MPDL is in demand.
Keywords: specialized high-level programming language, medical decision support systems.
The paper will prove sufficient conditions for the continuity of the lattice of propositional calculuses with the substitution operation and arbitrary circuit operations of inference. In addition, the cardinalities of the sets of all closed classes, precomplete and dual-precomplete classes of tautologies in the lattice of propositional calculuses will be described. The types of criteria systems for propositional calculuses will also be described.
Keywords: lattice of propositional calculi, precomplete classes, dual-precomplete classes, criteria systems.
This paper presents the results of an experimental analysis of the properties of Abelian groups in connection with their cryptographic applications. Due to the complexity of the computational problem, groups of small order are considered.
Keywords: order of 2-transitivity, Abelian group, finite group, symmetric cipher.
This paper considers shape models of objects in an image: binary and multi-class Boltzmann models. A new algorithm for training a multi-class Boltzmann shape model is proposed, for the application of which it is sufficient to have incomplete data labeling, namely: binary labeling and specifying seeds indicating the approximate location of object parts.
Keywords: Boltzmann shape model, multi-class Boltzmann shape model, graphical models, EM algorithm.
This article describes the process of creating a web application that implements the functionality of a geographic map. The material is divided into two parts. The first part solves the problems of drawing a map on the screen, scaling the map, moving around the map, displaying objects on the map. The second part considers the problem of clustering a predetermined set of objects located on the map using the k-means method and the distance method.
Keywords: online map, single-page applications, tiles, php, jQuery, ajax, SQL, k-means method, distance method, clustering.
The paper considers one-variable iterative propositional calculi, which are finite sets of propositional formulas in one variable together with the modus ponens operation and the superposition operation defined by the set of Mal'tsev operations. For such calculi, the problem of derivability of formulas will be reduced to the problem of deriving words in linear canonical systems. In particular, it will be shown that all one-variable iterative propositional calculi are decidable.
Keywords: iterative propositional calculi, derivability problem, linear canonical systems.
The article studies the relationship between the membership of automaton internal functions in precomplete classes of Boolean functions and the automaton's implementation of a dictionary function from the same class.
Keywords: automata theory, precomplete classes, dictionary function.
The article considers two problems: the problem of embedding admissible classes of alphabetic coding and the problem of embedding admissible classes of regular languages. In the first case, for an arbitrary pair of regular languages in a common alphabet, it is necessary to understand whether it is true that any alphabetic coding that is bijective in the first language will also be bijective in the second. In the second case, for an arbitrary pair of alphabetic codings in common input and output alphabets, it is necessary to understand whether it is true that an arbitrary regular language in which the first coding is bijective will have the same property in the second coding. It is shown that the first problem is algorithmically solvable for the case when the cardinality of the input alphabet is two. In the second case, it is shown that the problem is always algorithmically solvable.
Keywords: alphabetic coding, regular languages, embedding problem, admissible classes.
The paper formulates and proves a criterion for the realizability of functions on strings by probabilistic Moore automata with numerical output.
Keywords: probabilistic automata, Moore automata, reactions, random functions.
The article considers languages in the alphabet \[\{a_1, . . . , a_n\}\], in whose words the share of all consecutive pairs \[a_ia_j\] is fixed. This share is described by the generating matrix of the language Θ. The author called such languages bigram languages. Natural languages have a similar property. It turns out that the properties of such languages to be empty, finite, regular, context-free or context-dependent are verified by the matrix Θ. In this paper, the issue of infinite context-free languages is considered in detail.
Keywords: bigram, bigram multiplicity matrix, bigram language, context-free language, directed graph, Euler graph.
The paper constructs a generalization of the non-influence automaton model for the case of quantum automata. A "spin-up theorem" is proved, which describes sufficient security conditions.
Keywords: finite automata, system security, non-influence model.
03.2015 - Volume 19 Issue 1 (PDF)
The paper describes the technology of complex process assessment and monitoring developed at the MATIS Department since the early 90s. A substantive statement of the information monitoring problem is given, and technological and mathematical aspects of information monitoring systems development are described. An overview of the main results is given.
Keywords: assessment and monitoring systems, fuzzy sets, fuzziness assessment, search in fuzzy databases.
The article generalizes the results of [1] to the case of k-valued logics. The concept of a predictive automaton is introduced, which for each super-word from a given set fed to its input, starting from a certain step at each moment t, produces the value of the input word at the moment t + 1, i.e. predicts the input super-word. A criterion for the predictability of sets of super-words is obtained. The best order method for constructing a predictive automaton for an arbitrary predicted set of super-words is given.
Keywords: finite automaton, predictive automaton, event prediction.
The class P L of piecewise linear functions together with superposition operations is considered [1]. In this paper, it is shown that in P L there are three precomplete classes containing the class L of all linear functions: the class of finite functions, the class of continuous functions, and the class of consistent functions. A criterion has been obtained that allows one to check the completeness of the set M ∪ L for a finite set M ∈ P L.
Keywords: class of piecewise linear functions, class of finite functions, class of continuous functions, class of consistent functions, Heaviside function, superposition operations, essential discontinuity.
The paper presents an algorithm for constructing a set based on given parameters, for which the actual number of steps reaches half the upper estimate of the number of steps for this set in Novikov's theorem. It is additionally proved that for a set consisting of two points, the actual number of steps is no more than \[({D^2}/{2*r^2})+2\].Keywords: neural networks, Novikov's theorem.
The paper considers two problems: classification of music files by genre and classification of images. In the first case, it is necessary to implement a web application that determines the genres of music files loaded into it (jazz, classical, disco, metal, blues). In the second case, it is necessary to implement a web application with the ability to load reference images. When subsequently loading images, the system must determine which of the reference images the loaded image is most similar to and assign it to the appropriate class.
Keywords: classification, music files, mfcc, hog, php.
The task is to build a web page search engine. The main task of the system is to return a sorted list of results that satisfy a given user search query. The system is divided into several parts: crawler, indexer, ranking, and search interface. The article contains a detailed description of each of these parts. In addition, an implementation is provided for each part.
Keywords: Internet, search engine, crawler, indexer, ranking, HITS, PageRank, TF-IDF.
The problem considered in the paper is as follows: let a set of words be given; for an arbitrary subword it is required to find all occurrences of this subword in words from this set. In this paper a lower bound for the running time of algorithms that allow such a search is given, and the order of the memory volume for algorithms that perform the search in the minimum time by order is obtained.
Keywords: search for occurrences of subwords, lower bound, upper bound.
This paper considers the solution of a dynamic problem of searching for an identical object for an arbitrary query flow. The complexity of parallel query processing over a common data structure lies in avoiding conflicts that arise when changing the same memory area. At the same time, we assume that reading from one memory area is acceptable for several processes. The solution is obtained using a dynamic information graph [1], [2], which in turn is a generalization of the information graph [3] for the cases of insertion and deletion of a record.
Keywords: dynamic databases, information graph, finite state machine, query flows, parallel data processing.
Earlier, the author proved that pushdown automata preserve many periodic sequences and gave an exponential estimate for the period extension in this case. For automata with a unary store, this estimate was reduced to quadratic.
Keywords: pushdown automaton with a single-letter store, deterministic function, periodic sequences.
The algorithmic solvability of the problem of expressibility of linear automata through an arbitrary finite system of automata with respect to extended superposition is proved.
Keywords: automaton, linear automaton, expressibility, superposition, algorithmic solvability.
This paper considers the solution of a dynamic problem of searching for identical objects for an arbitrary query flow with logarithmic complexity. The complexity of parallel query processing over a common data structure lies in avoiding conflicts that arise when changing the same memory area. In this case, we believe that reading from one memory area is acceptable for several processes. The solution is obtained using a multi-automaton dynamic information graph [1].
Keywords: dynamic databases, information graph, automaton, query flows, parallel data processing, balanced trees.
The paper considers the problem of deciphering polynomial ranking functions. In the case when the ranking function depends linearly on a known variable, an algorithm for decoding with an accuracy of up to a multiplicative factor with a known error is proposed, as well as an estimate of its complexity. A class of functions is presented for which there is an algorithm that determines for which of the variables the corresponding monomial has the lowest degree and the smallest major coefficient in absolute value. An estimate of the complexity of this algorithm is given.
Keywords: decoding functions, ranking functions, website promotion.