Робастнi алгоритми для комбiнаторних задач маршрути- зацiї та трейдингу
Тип публікації :
Дисертація
Дата випуску :
29 квітня 2026 р.
Автор(и) :
Скибицький, Нiкiта Максимович
Науковий(і) керівник(и)/редактор(и) :
Семенов, Володимир Вiкторович
Мова основного тексту :
Ukrainian
eKNUTSHIR URL :
Цитування :
[APA 7] Скибицький, Н. М. (2026). Робастнi алгоритми для комбiнаторних задач маршрути- зацiї та трейдингу [Дис. доктора філософії, Київський національний університет імені Тараса Шевченка]. eKNUTSHIR. https://ir.library.knu.ua/handle/15071834/35752
[ДСТУ] Скибицький Н. М. Робастнi алгоритми для комбiнаторних задач маршрути- зацiї та трейдингу : дис. … доктора філософії : 113 Прикладна математика. Київ, 2026. 127 с. URL: https://ir.library.knu.ua/handle/15071834/35752
Скибицький Н.М. Робастнi алгоритми для комбiнаторних задач маршрутизацiї та трейдингу — Квалiфiкацiйна наукова праця на правах рукопису. Дисертацiя на здобуття наукового ступеня доктора фiлософiї за спецiальнiстю 113 — "Прикладна математика" (11 — "Математика та статистика"). — Київський нацiональний унiверситет iменi Тараса Шевченка, Київ, 2026.
У роботi отримано новi теоретичнi результати у п'яти галузях дискретної математики, що стали пiдґрунтям для побудови робастних методiв оптимiзацiї. Зокрема, дослiджено алгебраїчнi властивостi операцiї побiтового додавання в контекстi адитивної комбiнаторики. Для iнтервальних множин натуральних чисел A та B доведено, що розмiр їхньої побiтової суми |A ⊕ B| має лiнiйну верхню оцiнку вiдносно розмiрiв вихiдних множин, що суттєво покращує наївну квадратичну оцiнку. На основi цього теоретичного результату побудовано алгоритм, який дозволяє знаходити множину A⊕B за полi-логарифмiчний час.
У галузi рядкових алгоритмiв розроблено новий метод декомпозицiї Лiндона, який використовує шарувату архiтектуру структур даних та монотонний стек. Цей результат має важливе значення для задач лексикографiчного упорядкування, зокрема для ефективного обернення перетворення Барроуза—Вiллера, що застосовується в системах стиснення даних.
Встановлено зв'язок мiж задачами обчислення згорток послiдовностей та комбiнаторною оптимiзацiєю. У роботi встановлено зведення задачi про (min, +) згортку до окремого випадку задачi комiвояжера з квотою, що дозволило застосувати результати теорiї тонкої обчислювальної складностi для аналiзу ефективностi алгоритмiв маршрутизацiї.
Для структур даних типу дерево розв'язано задачi пошуку та пiдрахунку зигзагоподiбних послiдовностей. Запропоновано ефективнi алгоритми, що базуються на методi динамiчного програмування, використаннi найменшого спiльного предка (англ. lowest common ancestor) та технiцi злиття "вiд меншого до бiльшого". Цi методи переважають пiдходи, що ґрунтуються на декомпозицiї центроїдiв та декомпозицiї "важкий—легкий" (англ. heavy-light decomposition).
Дослiджено реберну зв'язнiсть регулярних графiв, зокрема циркулянтних. Запропоновано конструктивнi методи пошуку та пiдрахунку мiнiмально зв'язних циркулянтних графiв, що знаходить застосування у проєктуваннi надiйних мережевих топологiй, стiйких до вiдмов окремих ланок.
У прикладнiй частинi роботи побудовано ефективнi алгоритми розв'язування задач комбiнаторної оптимiзацiї в умовах невизначеностi. Запропоновано методи, що використовують структури даних, динамiчне програмування, метод гiлок та меж, кластеризацiю та генетичнi алгоритми. Проведено теоретичний аналiз констант апроксимацiї та ефективностi.
Проведено ряд обчислювальних експериментiв, що пiдтвердили перевагу розроблених методiв над класичними евристиками для задач, якi не допускають константної апроксимацiї за полiномiальний час. Показано, що хоча такi методи не є алгоритмами апроксимацiї з гарантованою оцiнкою, вони мають практичне значення для задач робастної оптимiзацiї.
У дисертацiї запропоновано новi перспективнi алгоритми та отриманi новi теоретичнi результати про обчислювальну складнiсть алгоритмiв. Теоретичне значення мають методи доведень теорем про збiжнiсть iнтегральних характеристик та теорем про екстремальнi оцiнки. Розробленi алгоритми та програмнi засоби можуть бути використанi для планування маршрутiв безпiлотних лiтальних апаратiв, оптимiзацiї логiстичних процесiв, аналiзу геномних послiдовностей у бiоiнформатицi та в системах алгоритмiчної торгiвлi на фiнансових ринках.
У роботi отримано новi теоретичнi результати у п'яти галузях дискретної математики, що стали пiдґрунтям для побудови робастних методiв оптимiзацiї. Зокрема, дослiджено алгебраїчнi властивостi операцiї побiтового додавання в контекстi адитивної комбiнаторики. Для iнтервальних множин натуральних чисел A та B доведено, що розмiр їхньої побiтової суми |A ⊕ B| має лiнiйну верхню оцiнку вiдносно розмiрiв вихiдних множин, що суттєво покращує наївну квадратичну оцiнку. На основi цього теоретичного результату побудовано алгоритм, який дозволяє знаходити множину A⊕B за полi-логарифмiчний час.
У галузi рядкових алгоритмiв розроблено новий метод декомпозицiї Лiндона, який використовує шарувату архiтектуру структур даних та монотонний стек. Цей результат має важливе значення для задач лексикографiчного упорядкування, зокрема для ефективного обернення перетворення Барроуза—Вiллера, що застосовується в системах стиснення даних.
Встановлено зв'язок мiж задачами обчислення згорток послiдовностей та комбiнаторною оптимiзацiєю. У роботi встановлено зведення задачi про (min, +) згортку до окремого випадку задачi комiвояжера з квотою, що дозволило застосувати результати теорiї тонкої обчислювальної складностi для аналiзу ефективностi алгоритмiв маршрутизацiї.
Для структур даних типу дерево розв'язано задачi пошуку та пiдрахунку зигзагоподiбних послiдовностей. Запропоновано ефективнi алгоритми, що базуються на методi динамiчного програмування, використаннi найменшого спiльного предка (англ. lowest common ancestor) та технiцi злиття "вiд меншого до бiльшого". Цi методи переважають пiдходи, що ґрунтуються на декомпозицiї центроїдiв та декомпозицiї "важкий—легкий" (англ. heavy-light decomposition).
Дослiджено реберну зв'язнiсть регулярних графiв, зокрема циркулянтних. Запропоновано конструктивнi методи пошуку та пiдрахунку мiнiмально зв'язних циркулянтних графiв, що знаходить застосування у проєктуваннi надiйних мережевих топологiй, стiйких до вiдмов окремих ланок.
У прикладнiй частинi роботи побудовано ефективнi алгоритми розв'язування задач комбiнаторної оптимiзацiї в умовах невизначеностi. Запропоновано методи, що використовують структури даних, динамiчне програмування, метод гiлок та меж, кластеризацiю та генетичнi алгоритми. Проведено теоретичний аналiз констант апроксимацiї та ефективностi.
Проведено ряд обчислювальних експериментiв, що пiдтвердили перевагу розроблених методiв над класичними евристиками для задач, якi не допускають константної апроксимацiї за полiномiальний час. Показано, що хоча такi методи не є алгоритмами апроксимацiї з гарантованою оцiнкою, вони мають практичне значення для задач робастної оптимiзацiї.
У дисертацiї запропоновано новi перспективнi алгоритми та отриманi новi теоретичнi результати про обчислювальну складнiсть алгоритмiв. Теоретичне значення мають методи доведень теорем про збiжнiсть iнтегральних характеристик та теорем про екстремальнi оцiнки. Розробленi алгоритми та програмнi засоби можуть бути використанi для планування маршрутiв безпiлотних лiтальних апаратiв, оптимiзацiї логiстичних процесiв, аналiзу геномних послiдовностей у бiоiнформатицi та в системах алгоритмiчної торгiвлi на фiнансових ринках.
Ключові слова :
задача комiвояжера динамiчне програмування безпiлотний лiтальний апарат чисельнi методи математичне моделювання комп’ютерне мо- делювання генетичний алгоритм невизначенiсть топологiчна структура. traveling salesman problem dynamic programming unmanned aerial vehicle numerical methods mathematical modeling computer modeling genetic algorithm uncertainty topological structure.
Галузі знань та спеціальності :
E6 Прикладна фізика та наноматеріали
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
1.1 MB
Контрольна сума :
(MD5):383a3ed6f27df7b5488c2dcd29ab61da
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International