The dissertation is devoted to the study of a stable methodology for solving the mathematical safe problem on graphs and matrices and to solving the question of necessary and sufficient conditions for the existence of a solution to a system of linear comparisons of finite modulus composed for a certain class of graphs or for corresponding matrices of arbitrary size that determine the mathematical content of such a specific positional game as the mathematical safe problem. New solution methods are presented and mechanisms for adjusting the initial data so that the problem has a solution are proposed. Another urgent problem is the development of universal efficient algorithms for mathematical safe problems, taking into account the growth of their dimensionality, since the existing solution methods at the time of writing this thesis are largely imperfect and do not form a coherent methodology, depending on specific types of graphs, initial conditions, etc.
The thesis outlines the theoretical foundations of a number of well-known methods for optimizing and solving positional games on graphs and matrices, describes their development, and considers all existing and relevant methods for solving mathematical safe problems on graphs and matrices (T-matrix method, TSS method). Subsequently, the thesis presents a methodology for finding a more efficient solution by taking into account the topology of the graph that defines the mathematical safe. This approach is demonstrated for a more complex type of graph, such as a "fan".
We analyze the algorithms of the TSS-method, which find the basis of the set of solutions of systems of linear homogeneous and inhomogeneous Diophantine comparisons over rings Fk and fields of redundancies Zk modulo prime and composite numbers (mod K).
This thesis proposes a new method of total representations for the problem of a mathematical safe on graphs, the main idea of which is that a certain type of graphs admits the existence of a limited number of equation elements, which in total is equal to the sum of all equation variables. As shown by the examples above, the method of summation is universal for solving problems about mathematical safes on undirected graphs. Exceptional cases are described, and a correction of the initial state of the safe is proposed.
Thanks to an in-depth analysis, the thesis develops a parametric method for mathematical safe problems on graphs, the essence of which is to designate variables corresponding to the vertices of the graph with certain parameters through which all other variables of the safe problem are located.
The thesis presents new methods for solving the problem of a mathematical safe on matrices: the method of forming (selecting) subsystems and the method of total representations. In the method of subsystem formation (selection), subsystems of two types are distinguished from the ascending system of equations, which reduces the computational complexity of the algorithm. Through further analysis, the problem with two types of locks is described - the problem is completely solved by the method of subsystem formation, the necessary and sufficient conditions for the existence of the solution are found, and explicit solution formulas are derived.
The methods are compared in terms of the arithmetic complexity of the algorithms for locks over a field of redundancies modulo a prime number.
The combinatorial methods for solving mathematical safe problems on graphs and matrices proposed in this thesis are of theoretical and practical importance, which allows them to be used to build models and find solutions to many practical problems that are reduced to positional games of this class and can be used to solve problems in decision theory, coding theory, and information security theory. Examples of encoding messages in messengers were given for encoding and protecting information.
The main scientific research on the subject of the dissertation was conducted at the Department of Economic Cybernetics of the Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine in connection with the implementation of research works:
WF 110.15 "Develop methods and algorithms for solving optimization problems on combinatorial configurations and trajectories of dynamic systems" (state registration number 0117U000473, protocol of acceptance and evaluation of scientific work No. 15 of 02.11.2021, deadline 01.01.17-31.12.21);
WF 110.18 "Construction of guaranteed control of system dynamics under different information assumptions" (state registration number 012U000663, approval protocol No. 1 of 08.07.2021, deadline 01.01.22-31.12.26).
