Перевірка структурних представлень комп'ютерних мереж на основі пошуку ізоморфізму
Вантажиться...
Дата
2023
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Актуальність теми. Задача визначення ізоморфізму графів містить низку проблем, які потребують багато часу для свого вирішення, та має розв’язок, який можна легко перевірити, але не обов'язково швидко знайти.
Угорський математик Ласло Бабай (Laszlo Babai), розробив математичний алгоритм визначення ізоморфізму графів за набагато меншу кількість кроків, ніж попередній найкращий алгоритм. В основі алгоритму лежить аналіз однакових взаємозв’язків між вершинами графів. На даний момент немає системи з програмною реалізацією алгоритму, який розробив Ласло Бабай. В ході аналізу даного методу визначення ізоморфізму графів виникли два способи реалізації:
— алгоритм реалізації на основі перевірки гіпотези;
— алгоритм реалізації з використанням матриць.
На сьогоднішній день існує багато комп’ютерних мереж і для пришвидшення процесу їх оптимізації виникає потреба у визначенні мереж, що мають однакову фізичну топологію. В зв’язку з цим виникла ідея створення системи пошуку ізоморфних структурних представлень комп’ютерних мереж, яка б дозволяла порівняти ефективність алгоритмів визначення ізоморфізму.
Метою роботи є створення системи пошуку ізоморфних структурних представлень комп’ютерних мереж, яка б дозволяла порівнювати ефективність методів визначення ізоморфізму.
Завдання дослідження:
— проаналізувати існуючі алгоритми пошуку ізоморфізму та обрати методи для програмної реалізації;
— вибрати технології для розробки системи;
— створити бібліотеку класів визначення ізоморфізму графів, яка повинна містити весь необхідний набір класів та методів для програмної реалізації ефективних алгоритмів пошуку ізоморфізму графів;
— створити базу даних фізичних топологій комп’ютерних мереж, яка встановлюватиме взаємозв’язок між фізичним топологіями, вузлами та з’єднаннями комп’ютерних мереж;
— розробити веб-інтерфейс для роботи з системою, який дозволятиме порівняти ефективність методів визначення ізоморфізму.
Об’єкт дослідження – математичні методи визначення ізоморфізму.
Предмет дослідження – математичні методи визначення ізоморфізму структурних представлень комп’ютерних мереж.
Практична цінність отриманих в роботі результатів полягає в наданні можливості встановлення відповідності між вузлами двох комп’ютерних мереж, що дозволить визначати комп’ютерні мережі з однаковими структурними представленнями. Наявність однакових фізичних топологій комп’ютерних мереж пришвидшить процес їх оптимізації.
Апробація результатів дисертації. Основні положення даної роботи доповідались та обговорювались на:
VІІІ Міжнародній Науково-Практичній Конференції «Сталий Розвиток – ХХІ Століття: Управління, Технології, Моделі (Наукові Читання Імені Ігоря Недіна)», 16-17 Листопада 2023 р., м. Київ, Україна.
Дисертація складається з вступу, шести розділів, висновків та додатку. Повний обсяг дисертації складає 88 сторінок, в тому числі 80 сторінок основного тексту, 18 таблиць, 31 рисунок, 3 сторінки списку використаних джерел у кількості 37 найменувань.
Опис
Створено систему пошуку ізоморфних структурних представлень комп’ютерних мереж, яка дозволяє порівнювати ефективність методів визначення ізоморфізму. Система включає в себе бібліотеку класів визначення ізоморфізму графів, базу даних фізичних топологій комп’ютерних мереж та веб-інтерфейс для роботи з системою. Для розробки системи вибрано мову програмування C# та платформу ASP.NET Core. Для створення бази даних фізичних топологій комп’ютерних вибрано СУБД MySQL Server.
Ключові слова
Бібліографічний опис
Власов, Р. І. Перевірка структурних представлень комп'ютерних мереж на основі пошуку ізоморфізму : магістерська дис. : 122 Комп’ютерні науки / Власов Ростислав Ігорович. – Київ, 2023. – 88 с.