Перевірка структурних представлень комп'ютерних мереж на основі пошуку ізоморфізму

Скорочена інформація про документ
dc.contributor.advisorКузьменко, Ігор Миколайович
dc.contributor.authorВласов, Ростислав Ігорович
dc.date.accessioned2024-02-19T13:10:16Z
dc.date.available2024-02-19T13:10:16Z
dc.date.issued2023
dc.descriptionСтворено систему пошуку ізоморфних структурних представлень комп’ютерних мереж, яка дозволяє порівнювати ефективність методів визначення ізоморфізму. Система включає в себе бібліотеку класів визначення ізоморфізму графів, базу даних фізичних топологій комп’ютерних мереж та веб-інтерфейс для роботи з системою. Для розробки системи вибрано мову програмування C# та платформу ASP.NET Core. Для створення бази даних фізичних топологій комп’ютерних вибрано СУБД MySQL Server.
dc.description.abstractАктуальність теми. Задача визначення ізоморфізму графів містить низку проблем, які потребують багато часу для свого вирішення, та має розв’язок, який можна легко перевірити, але не обов'язково швидко знайти. Угорський математик Ласло Бабай (Laszlo Babai), розробив математичний алгоритм визначення ізоморфізму графів за набагато меншу кількість кроків, ніж попередній найкращий алгоритм. В основі алгоритму лежить аналіз однакових взаємозв’язків між вершинами графів. На даний момент немає системи з програмною реалізацією алгоритму, який розробив Ласло Бабай. В ході аналізу даного методу визначення ізоморфізму графів виникли два способи реалізації: — алгоритм реалізації на основі перевірки гіпотези; — алгоритм реалізації з використанням матриць. На сьогоднішній день існує багато комп’ютерних мереж і для пришвидшення процесу їх оптимізації виникає потреба у визначенні мереж, що мають однакову фізичну топологію. В зв’язку з цим виникла ідея створення системи пошуку ізоморфних структурних представлень комп’ютерних мереж, яка б дозволяла порівняти ефективність алгоритмів визначення ізоморфізму. Метою роботи є створення системи пошуку ізоморфних структурних представлень комп’ютерних мереж, яка б дозволяла порівнювати ефективність методів визначення ізоморфізму. Завдання дослідження: — проаналізувати існуючі алгоритми пошуку ізоморфізму та обрати методи для програмної реалізації; — вибрати технології для розробки системи; — створити бібліотеку класів визначення ізоморфізму графів, яка повинна містити весь необхідний набір класів та методів для програмної реалізації ефективних алгоритмів пошуку ізоморфізму графів; — створити базу даних фізичних топологій комп’ютерних мереж, яка встановлюватиме взаємозв’язок між фізичним топологіями, вузлами та з’єднаннями комп’ютерних мереж; — розробити веб-інтерфейс для роботи з системою, який дозволятиме порівняти ефективність методів визначення ізоморфізму. Об’єкт дослідження – математичні методи визначення ізоморфізму. Предмет дослідження – математичні методи визначення ізоморфізму структурних представлень комп’ютерних мереж. Практична цінність отриманих в роботі результатів полягає в наданні можливості встановлення відповідності між вузлами двох комп’ютерних мереж, що дозволить визначати комп’ютерні мережі з однаковими структурними представленнями. Наявність однакових фізичних топологій комп’ютерних мереж пришвидшить процес їх оптимізації. Апробація результатів дисертації. Основні положення даної роботи доповідались та обговорювались на: VІІІ Міжнародній Науково-Практичній Конференції «Сталий Розвиток – ХХІ Століття: Управління, Технології, Моделі (Наукові Читання Імені Ігоря Недіна)», 16-17 Листопада 2023 р., м. Київ, Україна. Дисертація складається з вступу, шести розділів, висновків та додатку. Повний обсяг дисертації складає 88 сторінок, в тому числі 80 сторінок основного тексту, 18 таблиць, 31 рисунок, 3 сторінки списку використаних джерел у кількості 37 найменувань.
dc.description.abstractotherActuality of theme. The graph isomorphism problem contains a number of problems that take a long time to solve, and has a solution that can be easily verified, but not necessarily quickly found. Hungarian mathematician Laszlo Babai developed a mathematical algorithm for determining graph isomorphism in a much smaller number of steps than the previous best algorithm. The algorithm is based on the analysis of the same relationships between graph vertices. At the moment, there is no system with a software implementation of the algorithm developed by László Babaj. In the course of the analysis of this method of determining isomorphism of graphs, two methods of implementation arose: — implementation algorithm based on hypothesis testing; — implementation algorithm using matrices. Today, there are many computer networks, and in order to speed up the process of their optimization, there is a need to define networks that have the same physical topology. In this connection, the idea of creating a system for searching for isomorphic structural representations of computer networks, which would allow comparing the effectiveness of algorithms for determining isomorphism, arose. The aim of the work is to create a system for searching for isomorphic structural representations of computer networks, which would allow comparing the effectiveness of methods for determining isomorphism. Objectives of the study: — analyze existing isomorphism search algorithms and choose methods for software implementation; — choose technologies for system development; — to create a library of graph isomorphism definition classes, which should contain the entire necessary set of classes and methods for software implementation of effective graph isomorphism search algorithms; — to create a database of physical topologies of computer networks, which will establish the relationship between physical topologies, nodes and connections of computer networks; — to develop a web interface for working with the system, which will allow comparing the effectiveness of isomorphism determination methods. The object of research is mathematical methods of determining isomorphism. The subject of the research is mathematical methods of determining the isomorphism of structural representations of computer networks. The practical value of the results obtained in the work consists in providing the possibility of establishing correspondence between the nodes of two computer networks, which will allow determining computer networks with the same structural representations. Having identical physical topologies of computer networks will speed up the process of their optimization. Approbation of the results of the dissertation. The main provisions of this work were reported and discussed at: VIII International Scientific and Practical Conference "Sustainable Development - 21st Century: Management, Technologies, Models (Scientific Readings of the Names of Igor Nedin)", November 16-17, 2023, Kyiv, Ukraine. The dissertation consists of an introduction, six chapters, conclusions and an appendix. The full volume of the dissertation is 82 pages, including 74 pages of the main text, 18 tables, 28 figures, 3 pages of the list of used sources in the amount of 34 names.
dc.format.extent88 с.
dc.identifier.citationВласов, Р. І. Перевірка структурних представлень комп'ютерних мереж на основі пошуку ізоморфізму : магістерська дис. : 122 Комп’ютерні науки / Власов Ростислав Ігорович. – Київ, 2023. – 88 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/64692
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.titleПеревірка структурних представлень комп'ютерних мереж на основі пошуку ізоморфізму
dc.typeMaster Thesis

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Vlasov_magistr.pdf
Розмір:
3.26 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (ЦТЕ)
Магістерські роботи