Дисертація доктора філософії. Гурін Артем Леонідович. Комбінаторні методи розв'язання задач про математичний сейф на графах та матрицях

Реєстраційний номер

0823U100852, Дисертація доктора філософії

На здобуття

Доктор філософії

Дата захисту

15-11-2023

Статус

Наказ про видачу диплома

Назва роботи

Комбінаторні методи розв'язання задач про математичний сейф на графах та матрицях

Здобувач

Гурін Артем Леонідович,

Керівник Донець Георгій Панасович
Керівник Кузьменко Віктор Миколайович
Опонент Кривий Сергій Лук'янович
Опонент Гороховський Семен Самуїлович
Рецензент Гуляницький Леонід Федорович
Рецензент Стецюк Петро Іванович

Установа, організація, у вченій раді якої відбудеться/відбувся захист

Інститут кібернетики імені В. М. Глушкова Національної академії наук України

Опис

Дисертаційна робота присвячена дослідженню сталої методології розв’язання задачі про математичний сейф на графах та матрицях та вирішенню питання про необхідні та достатні умови існування рішення системи лінійних порівнянь за кінцевим модулем, складеної для певного класу графів, або для відповідних матриць довільного обсягу, що визначають математичний зміст такої специфічної позиційної гри, як задача про математичний сейф. Наведені нові методи розв’язку та запропоновані механізми корегування початкових даних таким чином, щоб задача мала рішення. Іншою актуальною проблемою є розробка універсальних ефективних алгоритмів для задач про математичний сейф з урахуванням зростання їхньої розмірності, оскільки існуючі на момент написання дисертації методи розв’язання багато в чому недовершені і не складаються у цілісну методологію, залежачи від конкретних типів графів, початкових умов, тощо. В дисертації викладено теоретичні основи низки відомих методів оптимізації та розв’язання позиційних ігор на графах та матрицях, описано їхній розвиток, розглянуто всі існуючі та актуальні методи розв’язання задач про математичний сейф на графах та матрицях (метод Т-матриць, TSS-метод). У подальшому в дисертації наводиться методологія знаходження більш ефективного розв’язку, завдяки урахуванню топології графу, що задає математичний сейф. Цей підхід продемонстровано для більш складного типу графу, такого як «віяло». Проведено аналіз алгоритмів TSS-методу, які знаходять базис множин розв’язків систем лінійних однорідних і неоднорідних диофантових порівнянь над кільцями Fk і полями лишків Zk за модулем простого і складеного числа (mod K). У дисертації запропонований новий метод сумарних представлень для задачі про математичний сейф на графах, основна ідея якого полягає у тому, що певний тип графів допускає існування обмеженої кількості елементів рівняння, що в сумі дорівнює сумі всіх змінних рівнянь. Як показали наведені приклади, метод сумарних представлень є універсальним для розв’язання задач про математичні сейфи на неорієнтованих графах. Описані виняткові випадки, запропоноване корегування початкового стану сейфу. Завдяки поглибленому аналізу в дисертації розроблено параметричний метод для задач про математичний сейф на графах, сутність якого полягає у позначенні змінних, які відповідають вершинам графа визначеними параметрами, через які знаходяться всі інші змінні задачі про сейф. У дисертації викладено нові методи для розв’язку задачі про математичний сейф на матрицях: метод формування (виділення) підсистем та метод сумарних представлень. У методі формування (виділення) підсистем з висхідної системи рівнянь виділяють підсистеми двох типів, що дозволяє зменшити обчислювальну складність алгоритму. Завдяки подальшому аналізу, описано задачу з двома типами замків – задача повністю розв’язана методом формування підсистем, знайдено необхідні та достатні умови існування розв’язку, виведено явні формули розв'язку. Проведено порівняння методів за арифметичною складністю алгоритмів для замків над полем лишків за модулем простого числа. Запропоновані в дисертації комбінаторні методи розв’язання задач про математичний сейф на графах та матрицях мають теоретичне та практичне значення, що дозволяє їх застосовувати для побудов моделей та знаходження розв’язків багатьох практичних завдань, які зводяться до позиційних ігор подібного класу і можуть бути використані для розв’язання задач теорії прийняття рішень, теорії кодування та теорії захисту інформації. Для кодування та захисту інформації були наведені приклади кодування повідомлень у месенджерах. Основні наукові дослідження за тематикою дисертації проводилися у відділі економічної кібернетики Інституту кібернетики НАНУ імені В.М. Глушкова у зв'язку із виконанням науково-дослідних робіт: ВФ 110.15 «Розробити методи та алгоритми розв’язання оптимізаційних задач на комбінаторних конфігураціях і траєкторіях динамічних систем» (державний реєстраційний номер 0117U000473, протокол приймання та оцінки наукової роботи № 15 від 02.11.2021, термін виконання 01.01.17–31.12.21); ВФ 110.18 «Побудова гарантованих керувань динаміки систем при різних інформаційних припущеннях» (державний реєстраційний номер 012U000663, протокол затвердження №1 від 08.07.2021, термін виконання 01.01.22–31.12.26).

Дата реєстрації

2023-10-12

Додано/оновлено в НРАТ

2023-11-08 / 2026-07-01