Дисертація доктора філософії. Сапожник Дмитро Олегович. Методи та алгоритми для розвʼязання задачі максимального розрізу за допомогою квантово-гібридних алгоритмів

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

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

На здобуття

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

Дата захисту

29-06-2026

Статус

Захищена

Назва роботи

Методи та алгоритми для розвʼязання задачі максимального розрізу за допомогою квантово-гібридних алгоритмів

Здобувач

Сапожник Дмитро Олегович,

Керівник Морозов Андрій Васильович
Опонент Гнатюк Сергій Олександрович
Опонент Лахно Валерій Анатолійович
Рецензент Воротніков Володимир Володимирович
Рецензент Лобанчикова Надія Миколаївна

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

Державний університет "Житомирська політехніка"

Опис

Задача максимального розрізу графа (Max-Cut) належить до класу NP-складних задач комбінаторної оптимізації та займає важливе місце в теорії алгоритмів, теорії складності та прикладній математиці. Мета задачі полягає у знаходженні такого розбиття множини вершин неорієнтованого графа на дві підмножини, при якому кількість або сумарна вага ребер між цими підмножинами є максимальною. Незважаючи на простоту формулювання, задача характеризується експоненційним зростанням простору можливих рішень зі збільшенням кількості вершин, що обумовлює її високу обчислювальну складність. Задача Max-Cut застосовується в задачах оптимізації топології телекомунікаційних і енергетичних мереж, балансування навантаження в розподілених системах, кластеризації даних, аналізі мережевих структур, фінансовому моделюванні, а також у задачах проєктування інтегральних схем і транспортному плануванні. Класичні підходи до розв’язання Max-Cut демонструють суттєві обмеження при зростанні розмірності графа. Точні алгоритми, зокрема метод повного перебору та метод гілок і меж, забезпечують знаходження глобально оптимального розв’язку, однак їх експоненційна часова складність обмежує їх використання для задач середньої та великої розмірності. Апроксимаційні методи, зокрема алгоритм Ґоєманса-Вільямсона (Goemans-Williamson), забезпечують теоретичні гарантії якості розв’язку, проте пов’язані зі значними обчислювальними витратами, зумовленими використанням напіввизначеного програмування. Евристичні та метаевристичні алгоритми, такі як локальний пошук, генетичні алгоритми та імітація відпалу, мають кращу масштабованість, однак не гарантують досягнення глобального оптимуму та характеризуються варіативністю результатів.

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

2026-06-01

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

2026-06-01 / 2026-07-17