2021, volume 25, issue 2 (PDF)

Berger I.O. Algorithms of moving of the end of the chain to the given point in space with the taxicab metric

The paper considers the problem of moving a three-link chain with one fixed edge from the initial position to the position in which the second edge is placed in a given point. The initial position is the position at which all chain links lie on the abscissa axis. Moreover, each chain link has a fixed length, but it can bend at an angle of 90 degrees at any point. The paper proposes an algorithm that minimizes the distance between the initial and final positions of the chain, and the distance measure is based on the metric of taxicab geometry.

Keywords: Manhattan chains, Manhattan distance, algorithm, taxicab geometry.

Gornyi B.E., Ryjov A.P., Strogalov A.S., Zhuravlev A.D., Khusaenov A.A., Shergin I.A., Feshchenko D.A., Abdullaev A.M., Kontsevaya A.V. The adverse clinical outcome risk assessment by in-depth data analysis methods

The adverse events in the medical care providing process occurs in 10-15% of hospitalized patients. Even a few percent reducing of such events will save thousands of lives. One of the ways to solve this crucial problem is the usage of intelligent information technologies that allow the predicting of an unfavorable clinical outcome risk in patients. The paper presents the study results carried out jointly by the scientist of the National Research Center for Therapy and Preventive Medicine of the Ministry of Health of the Russian Federation and the the scientist of Faculty of Mechanics and Mathematics of the Lomonosov Moscow State University, showing the applicability of data analysis methods in this important problem solving.

Keywords: preventive medicine, adverse clinical outcome, in-depth data analysis.

Konovalov A.Yu. Basic Logic is sound with respect to absolute L-realizability

An absolute L-realizability of predicate formulas is introduced for all countable extensions L of the language of arithmetic. It is proved that the basic logic is sound with this semantics.

Keywords: constructive semantics, realizability, absolute realizability, formal arithmetic, basic logic.

Panteleev V. I., Taglasov E. S. \( ES_I \)-closure of rank 2 multi-functions: completeness criterion, classification, and types of bases

Multifunctions are functions that are defined on a finite set and return subsets of the considered set as their values. This paper deals with the closure of multifunctions that can be obtained using the operations of adding dummy variables, composition operator, and operator with the equality predicate branching. We obtain nine precomplete closed classes of multifunctions of rank two and prove the completeness criterion. A classification of multifunctions based on belonging to precomplete classes is presented, and all types of bases are described.

Keywords: closure, equality predicate, multioperation, closed set, composition.

Tropin A.M. An estimate for the length of a minimal parametric network in hyperspaces under deformation of the boundary set

The Fermat—Steiner problem is to find a point in the metric space Y (which we will call the Steiner astrovertex) such that the sum of the distances from it to the points of some finite fixed subset \( A \subset Y \), called the boundary, is minimal. We will call the minimal sum of distances the length of the minimal astronet. We consider this problem in the hyperspace \( Y = H(X) \) of nonempty, closed, and bounded subsets of the proper space X, which are compact in this space. This article describes a wide class of deformations of boundary compact sets that do not increase the length of the minimal astronet. Averaging in the sense of the Minkowski sum of a finite number of boundaries consisting of an equal number of elements is also considered, and it is shown that such averaging also does not increase the length of the minimal astronet.

Keywords: Fermat—Steiner problem, Steiner minimal tree, minimal parametric network, minimal astronet, Steiner astrocompact, hyperspace, Hausdorff distance.

Demidova A.A. Automaton analysis of the properties of a graph to be a tree and a pseudo-tree

In this paper, we investigate the use of automata with erasable colors to determine the properties of connected planar undirected simple graphs. The following facts are proved: two erasable colors are enough for automata to determine whether the graph is a tree or a pseudo-tree.

Keywords: Automata, graphs, trees, pseudotrees.

Nosov M.V. On the formulaic representation of the Shannon function

The paper presents a formula for the Shannon function for schemes in the basis of the Schaeffer stroke.

Keywords: Schaeffer’s stroke, schema of functional elements, Shannon function.

Sitdikov T. R., Kalachev G. V. The complexity of multilayer d-dimensional circuits

In this paper we research a model of multilayer circuits with a single logical layer. We consider \( \lambda \)-separable graphs as a support for circuits. We establish the Shannon function lower bound \( \max \left(\frac{2^n}{n}, \frac{2^n (1 - \lambda)}{\log k} \right)\) for this type of circuits where k is the number of layers. For d-dimensional graphs, which are \( \lambda \)-separable for \( \lambda \) = \( \frac{d - 1}{d} \), this gives the Shannon function lower bound \( \frac{2^n}{\min(n, d \log k)} \). For multidimensional rectangular circuits the proved lower bound asymptotically matches to the upper bound.

Keywords: multilayer circuits, multidimensional circuits, Shannon function asymptotics, circuit complexity, graph separators.

Chasovskikh A.A. Linear p-automata classes with superposition operations

All precomplete classes are found for classes of linear automata over simple finite fields with superposition operations.

Keywords: finite automaton, linear automaton, operation of superposition, completeness, closed class, maximum subclass, finite field.

Reports of the seminar "Questions of complexity of search algorithms"

← Back to archive