Методы решения задач о математическом сейфе на элементарных графах
Рассмотрена задача о математическом сейфе, представляющим собой некоторую систему взаимосвязанных замков с заданными начальными состояниями. Розглянуто задачу про математичний сейф, який представляє собою деяку систему взаємопов’язаних замків із заданими початковими станами. Таку систему можна предс...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2019 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/180818 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Методы решения задач о математическом сейфе на элементарных графах / А.Л. Гурин, А.Г. Донец, С.П. Загороднюк // Проблемы управления и информатики. — 2019. — № 4. — С. 36-47. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-180818 |
|---|---|
| record_format |
dspace |
| spelling |
Гурин, А.Л. Донец, А.Г. Загороднюк, С.П. 2021-10-20T11:51:32Z 2021-10-20T11:51:32Z 2019 Методы решения задач о математическом сейфе на элементарных графах / А.Л. Гурин, А.Г. Донец, С.П. Загороднюк // Проблемы управления и информатики. — 2019. — № 4. — С. 36-47. — Бібліогр.: 5 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180818 519.1 Рассмотрена задача о математическом сейфе, представляющим собой некоторую систему взаимосвязанных замков с заданными начальными состояниями. Розглянуто задачу про математичний сейф, який представляє собою деяку систему взаємопов’язаних замків із заданими початковими станами. Таку систему можна представити у вигляді орієнтованого чи неорієнтованого графа, вершинами якого є замки. В даній роботі розглядаються графи з достатньо простою конструкцією. До них відносяться такі графи як шлях, контур, ланцюг, цикл, віяло, драбинки з визначеною кількістю щаблинок та ускладнені драбинки. Розв’язок такої задачі в загальному випадку зводиться до розв’язування системи лінійних рівнянь в класі віднімань за модулем, що дорівнює числу станів кожного замка сейфа. Насправді таке число являє собою кількість поворотів ключа в кожному замку таку, щоби врешті-решт сейф перейшов у стан, у якому всі замки будуть відкритими. Для розв’язання задачі пропонується два оригінальних метода — метод виділення змінних та метод сумарних представлень. Суть першого методу полягає в наступному. Для деяких простих графів існує можливість виділення деяких рівнянь для безпосереднього їх розв’язання відносно будь-якої однієї змінної. Після, підставляючи послідовно отримані значення у відповідні рівняння, отримаємо розв’язок системи. Цей метод був застосований при розв’язанні задачі для графа типу цикл. Суть другого методу полягає у введенні спеціального параметра, який називається сумою невідомих. Деякі графи дозволяють представити змінні системи через такий параметр. Просумувавши ці змінні, отримаємо рівняння відносно нього. Розв’язавши це рівняння, отримаємо значення цього параметру, а разом з ним значення всіх змінних. Цей метод був застосований при розв’язанні задачі для графа типу віконця та драбинок. Кожна задача для відповідного типу сейфа ілюструється прикладами та супроводжується перевіркою розв’язку. We consider the problem on mathematical safe, consisting of certain system of inter-related locks with given initial states. Such system can be presented in the form of oriented or non-oriented graph, which tops are locks. In this paper we deal with graphs of sufficiently simple design, such as path, contour, chain, cycle, umbrella, stairs with prescribed quantity of steps, and complicated stairs. In general case, solution of this problem reduces to solving a system of linear equations in the class of residues in modulo, which equal to the number of states of each safe lock. In fact, it equals to the number of key turns in each lock, sufficient for safe to switch info the state with all open locks. To solve this problem, two original methods are suggested, namely, the method of variables separation and the method of combined representations. The gist of first method consists in the following. For some elementary graphs some equations can be separated and solved in certain variable. Then, upon successive substation of obtained solutions into corresponding equations, we come to solution of the system. This method was applied to solve the problem for the graph of cycle type. The gist of second method consists in introduction of special parameter, called the sum of unknowns. For some graphs, to present the system variables through this parameter is a possibility. Upon summing these variables, we obtain equation in the mentioned parameter. We add these variables and come to the equation in this parameter. Upon solving this equation we obtain value of this parameter as well as the values of all variables. This method was applied to solve the problem for the graphs of window and complicated stairs types. Each problem for prescribed safe types is illustrated by examples and accompanied by solution verification. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы оптимизации и оптимальное управление Методы решения задач о математическом сейфе на элементарных графах Методи розв’язування задач про математичний сейф на елементарних графах Methods of solving the problems on mathematical safe on elementary graphs Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Методы решения задач о математическом сейфе на элементарных графах |
| spellingShingle |
Методы решения задач о математическом сейфе на элементарных графах Гурин, А.Л. Донец, А.Г. Загороднюк, С.П. Методы оптимизации и оптимальное управление |
| title_short |
Методы решения задач о математическом сейфе на элементарных графах |
| title_full |
Методы решения задач о математическом сейфе на элементарных графах |
| title_fullStr |
Методы решения задач о математическом сейфе на элементарных графах |
| title_full_unstemmed |
Методы решения задач о математическом сейфе на элементарных графах |
| title_sort |
методы решения задач о математическом сейфе на элементарных графах |
| author |
Гурин, А.Л. Донец, А.Г. Загороднюк, С.П. |
| author_facet |
Гурин, А.Л. Донец, А.Г. Загороднюк, С.П. |
| topic |
Методы оптимизации и оптимальное управление |
| topic_facet |
Методы оптимизации и оптимальное управление |
| publishDate |
2019 |
| language |
Russian |
| container_title |
Проблемы управления и информатики |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Методи розв’язування задач про математичний сейф на елементарних графах Methods of solving the problems on mathematical safe on elementary graphs |
| description |
Рассмотрена задача о математическом сейфе, представляющим собой некоторую систему взаимосвязанных замков с заданными начальными состояниями.
Розглянуто задачу про математичний сейф, який представляє собою деяку систему взаємопов’язаних замків із заданими початковими станами. Таку систему можна представити у вигляді орієнтованого чи неорієнтованого графа, вершинами якого є замки. В даній роботі розглядаються графи з достатньо простою конструкцією. До них відносяться такі графи як шлях, контур, ланцюг, цикл, віяло, драбинки з визначеною кількістю щаблинок та ускладнені драбинки. Розв’язок такої задачі в загальному випадку зводиться до розв’язування системи лінійних рівнянь в класі віднімань за модулем, що дорівнює числу станів кожного замка сейфа. Насправді таке число являє собою кількість поворотів ключа в кожному замку таку, щоби врешті-решт сейф перейшов у стан, у якому всі замки будуть відкритими. Для розв’язання задачі пропонується два оригінальних метода — метод виділення змінних та метод сумарних представлень. Суть першого методу полягає в наступному. Для деяких простих графів існує можливість виділення деяких рівнянь для безпосереднього їх розв’язання відносно будь-якої однієї змінної. Після, підставляючи послідовно отримані значення у відповідні рівняння, отримаємо розв’язок системи. Цей метод був застосований при розв’язанні задачі для графа типу цикл. Суть другого методу полягає у введенні спеціального параметра, який називається сумою невідомих. Деякі графи дозволяють представити змінні системи через такий параметр. Просумувавши ці змінні, отримаємо рівняння відносно нього. Розв’язавши це рівняння, отримаємо значення цього параметру, а разом з ним значення всіх змінних. Цей метод був застосований при розв’язанні задачі для графа типу віконця та драбинок. Кожна задача для відповідного типу сейфа ілюструється прикладами та супроводжується перевіркою розв’язку.
We consider the problem on mathematical safe, consisting of certain system of inter-related locks with given initial states. Such system can be presented in the form of oriented or non-oriented graph, which tops are locks. In this paper we deal with graphs of sufficiently simple design, such as path, contour, chain, cycle, umbrella, stairs with prescribed quantity of steps, and complicated stairs. In general case, solution of this problem reduces to solving a system of linear equations in the class of residues in modulo, which equal to the number of states of each safe lock. In fact, it equals to the number of key turns in each lock, sufficient for safe to switch info the state with all open locks. To solve this problem, two original methods are suggested, namely, the method of variables separation and the method of combined representations. The gist of first method consists in the following. For some elementary graphs some equations can be separated and solved in certain variable. Then, upon successive substation of obtained solutions into corresponding equations, we come to solution of the system. This method was applied to solve the problem for the graph of cycle type. The gist of second method consists in introduction of special parameter, called the sum of unknowns. For some graphs, to present the system variables through this parameter is a possibility. Upon summing these variables, we obtain equation in the mentioned parameter. We add these variables and come to the equation in this parameter. Upon solving this equation we obtain value of this parameter as well as the values of all variables. This method was applied to solve the problem for the graphs of window and complicated stairs types. Each problem for prescribed safe types is illustrated by examples and accompanied by solution verification.
|
| issn |
0572-2691 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/180818 |
| citation_txt |
Методы решения задач о математическом сейфе на элементарных графах / А.Л. Гурин, А.Г. Донец, С.П. Загороднюк // Проблемы управления и информатики. — 2019. — № 4. — С. 36-47. — Бібліогр.: 5 назв. — рос. |
| work_keys_str_mv |
AT gurinal metodyrešeniâzadačomatematičeskomseifenaélementarnyhgrafah AT donecag metodyrešeniâzadačomatematičeskomseifenaélementarnyhgrafah AT zagorodnûksp metodyrešeniâzadačomatematičeskomseifenaélementarnyhgrafah AT gurinal metodirozvâzuvannâzadačpromatematičniiseifnaelementarnihgrafah AT donecag metodirozvâzuvannâzadačpromatematičniiseifnaelementarnihgrafah AT zagorodnûksp metodirozvâzuvannâzadačpromatematičniiseifnaelementarnihgrafah AT gurinal methodsofsolvingtheproblemsonmathematicalsafeonelementarygraphs AT donecag methodsofsolvingtheproblemsonmathematicalsafeonelementarygraphs AT zagorodnûksp methodsofsolvingtheproblemsonmathematicalsafeonelementarygraphs |
| first_indexed |
2025-12-07T17:25:13Z |
| last_indexed |
2025-12-07T17:25:13Z |
| _version_ |
1850871186108448768 |