Русский
2021 year, volume 25, issue 3 (PDF)
A combinatorial approach to the strict consensus ranking problem for a given set of nonstrict orderings of alternatives is considered. A concept of light score matrix (skew-symmetric) is introduced providing more simple and clear optimization process and its result. Some heuristic search procedures are formulated allowing optimal strict consensus rankings (including multiple) to be found in different cases.
Keywords: rankings, Kemeny median, skew-symmetric matrices, parallel generation of permutations, Julia language, OpenCL.
The Fermat—Steiner problem is to find a point in the metric space \( Y \) 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 minimum astronet. We consider this problem in the hyperspace \( Y = H(X) \) of nonempty, closed and bounded subsets of the proper metric space \( X \); moreover, the Hausdorff metric is introduced on \( H(X) \). Since \( X \) is proper space, all elements of \( H(X) \) are compact. Each solution of the Fermat—Steiner problem will be called the Steiner astrocompact; its set is divided into classes with equal weight, each of which corresponds to its own vector of distances to the boundary compact sets. In this article, we prove three sufficient conditions for the given compact set to be a Steiner astrocompact for a given boundary. Also, these conditions guarantee the uniqueness of the class of Steiner astrocompact spaces with equal weight. This theory is used to completely solve the Fermat—Steiner problem for some symmetric convex three-element boundaries in \( \mathbb {R}^2 \), and this is demonstrated by examples.
Keywords: Fermat-Steiner problem, star network, minimal astronet, Steiner astrocompact, hyperspace, Hausdorff distance, metric projection, point-to-set distance function, first variation.
It is proved that the Shannon function for the test length with respect to a read-once alternative in the elementary basis augmented with all weakly read-multiple unate functions does not exceed \( 3n − 2 \).
Keywords: read-once functions, checking test, weakly read-multiple functions.
The paper studies one special type of interaction of automata collectives in labyrinths. The following problem is considered for a given class of labyrinths: for which pairs of collective types there is a collective of the first type and a collective of the second type that will certainly meet, if at the starting moment they are placed in any two vertices of any labyrinth of the given class. We call this the problem of the ‘type meeting’ for automata in the given class of labyrinths. Here the problem is completely solved both for the case of the class of all finite plane mosaic labyrinths and for the case of the class of all finite plane rectangular labyrinths. The problem remains unsolved so far for the case of all (finite and non finite) mosaic labyrinths for some pairs of collective types, whereas for the case of the class of all plane rectangular labyrinths, the problem of type meeting is completely unexplored.
Keywords: collective of automata, collective type, plane rectangular labyrinth, plane mosaic labyrinth, type meeting.
The paper presents a number of formulas for the characteristic function of the Boolean solution linear equation with integer coefficients. The function arguments are binary expansions of these coefficients.
Keywords: linear equation, Boolean solution, characteristic function.
For a finite system of piecewise parallel functions implemented by schemes of linear elements and Heaviside functions, the criterion for the expressiveness of piecewise constant functions is obtained, supplemented by all single linear functions. Thus, the criterion of expressiveness of the binary classifier implemented by the McCulloch-Pitts neural scheme is obtained.
Keywords: Piecewise constant function, piecewise parallel function, completeness problem, expressibility problem, McCulloch-Pitts neural circuits.
There is a function \( d_{(A,M )} (n) \) called growth rate that is defined for an arbitrary finite set \(A\) with a set of operations \(M\) defined on it. It characterizes the strength of given operations. It has been proved that growth rate is either \( O(n^k) \) for some \( k \in \mathbb {N} \), either \( 2^{\Theta(n)} \). We research classes of exponential growth rates that appear after splitting the class with asymptotic bound in the exponent to classes with outward asymptotic bounds. We show that there exists a pair \((A, M)\) with the growth rate \( d_{(A,M)}(n) \in \Theta (n^k \cdot c^n)\) for arbitrary predefined natural numbers \(k\) and \(c\). In addition, if \(c > k + 1\) then there exists a pair \((A, M)\) with the growth rate \(d_{(A,M)}(n) \in \Theta (\log n \cdot n^k \cdot c^n)\).
Keywords: growth rate, generating sets, finite sets, EGP.
In this paper, we examined the computational complexity (minimum possible number of operations) of systems of monomials by circuits using two-input composition operation, which can be considered as a generalization of multiplication operation. We found that growth asymptotic of the Shannon function, characterizing the maximum complexity among systems of \(p\) monomials of \(q\) variables with exponents no more than \(K\), given that \(pq \log K \rightarrow \infty\) and some additional restrictions, has the form \( \min(p,q) \log_2 K + \frac{pq}{\log_2(pq)}\).
Keywords: set of monomials, computation complexity, circuit complexity, composition circuit, Shannon function.
The work schematically proves an intuitive fact on the correspondence of the polynomial complexity of the SFE in the basis of the Schaeffer prime polynomial number of steps of the Turing machine. Numerical estimates are given.
Keywords: circuit complexity, Schaeffer’s stroke, Turing machine.
This work concerns property of being finitely generated by operations of \(A\)-closing of found earlier maximum subclasses in the class of linear automata over the ring of dyadic rationals. We present the proof of the fact that two of them are not finitely generated, while others are finitely generated.
Keywords: finite state automata, linear automata, dyadic rationals, \(A\)-completeness, maximum subclasses, finitely generated.