Открытый доступ
Доступ предоставлен
Только для подписчиков
Том 43, № 1 (2019)
- Год: 2019
- Статей: 7
- URL: https://journals.rcsi.science/0278-6419/issue/view/10814
Article
FPT-Algorithm for Computing the Width of a Simplex Given by a Convex Hull
Аннотация
The problem of computing the width of simplices generated by the convex hull of their integer vertices is considered. An FPT algorithm, in which the parameter is the maximum absolute value of the rank minors of the matrix consisting from the simplex vertices, is presented.
1-11
Applying a Generalized Allocation Scheme to Analyzing a Class of Sequences Generated by a Shift Register
Аннотация
An example of applying a generalized allocation scheme to studying the asymptotic behavior of combinatorial objects is considered. The allocation of tuples of zeros and ones onto a circle generated by a shift register under certain conditions is analyzed.
12-16
Analysis of a Discrete Model of an Adaptive Control System for Conflicting Nonhomogeneous Flows
Аннотация
Using the Lyapunov–Yablonsky approach based on cybernetics, we construct and study a mathematical model of an adaptive control system for conflicting flows of nonhomogeneous customers. The state of the facility and queue lengths for conflicting input flows are chosen as the state of the control system. The Markov property of the sequence of states of the system is proved and they are classified. A necessary condition is found for the existence of a stationary mode in the system.
17-24
A Family of Closed Classes in k-Valued Logic
Аннотация
We consider functions of k-valued logic closed with respect to superposition classes containing all functions linear modulo k (these classes are related to divisors d of number k). Canonical relations are determined for the elements in such classes, and complete systems and bases are found. The lattice of the introduced classes with respect to the inclusion relation is described. Earlier results are generalized and complemented. This is true in particular for results on d-periodic functions and preservation of d-differences.
25-31
Adjacent Vertices Can be Hard to Find by Quantum Walks
Аннотация
Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Ω(N) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjacent marked vertices. The analysis is done for the two-dimensional grid and hypercube, and then is generalized for any graph.
Additionally, we consider an algorithmic application of the found effect. We investigate a problem of detection of a perfect matching in a bipartite graph. We use the found effect as an algorithmic building block and construct quantum algorithm which, for a specific class of graphs, outperforms its classical analogs.
32-39
The Elements of Associative Stegnanography Theory
Аннотация
The results of the author’s collective research on the theory of associative steganography are systematized in order to bring them to a wide range of developers and users of stegosystems. The concept of associative steganography is associated with the associative protection of a finite set of object types and their coordinates, the decimal code symbols of which are represented by masked binary matrices of the same size. Consideration is carried out from positions of constructive modeling of systems. The accepted postulates on the principles of concealment, the logical interpretation of the criterion of Shannon’s perfect secrecy, the choice of the sizes of matrices and the randomizing gamma are explained. The masking algorithm is described. Estimates of the effectiveness of associative protection are given: the proof of the basic theorem, the estimation of speed, stiffness and noise immunity.
40-46
Quantum Algorithm for Shortest Path Search in Directed Acyclic Graph
Аннотация
In this work, we consider a well-known “Single Source Shortest Path Search” problems for weighted directed acyclic graphs (DAGs). We suggest a quantum algorithm with time complexity \(O(\sqrt {nm} \,\log \;n)\) and O(1/n) error probability, where n is a number of Vertexes, m is the number of edges. We use quantum dynamic programming approach (Khadiev, 2018) and Dürr and Høyer minimum search algorithm to speed up our search. Our algorithm is better than C. Dürr and coauthors’ quantum algorithm for an undirected graph. The time complexity of C. Dürr’s algorithm is \(O(\sqrt {nm} \,{(\log \;n)^2})\). The best known deterministic algorithm for the problem is based on a dynamic programming approach and its time complexity is O (n + m). At the same time, if we use algorithms for general graphs, then we do not get better results. The time complexity of best implementations of Dijkstra’s algorithm with Fibonacci heap is O (m + n log n).
47-51