Застосування патернiв проектування в сучасному C++ для реалiзацiї операторiв на графах

Simple item page
dc.contributor.advisorБублик, Володимирuk_UA
dc.contributor.authorНагорний, Юрiй uk_UA
dc.date.accessioned2026-08-13T13:51:17Z
dc.date.available2026-08-13T13:51:17Z
dc.date.issued2026
dc.descriptionThis qualification paper is devoted to the problem of improving the computational efficiency of structural graph operators by integrating them into an eventdriven joint traversal architecture using modern C++20 standard tools. The architectural limitations of classic generic libraries (using BGL as an example) are established, and the mathematical criteria for the compatibility of operators with the joint traversal mechanism are formulated. An original algorithm for line graph construction is developed, and the iterative line graph recognition algorithm ILIGRA is adapted for execution in a single pass of the breadth-first search (BFS). A prototype of a graph library is designed utilizing static Visitor and Composite design patterns based on Concepts with zero-overhead abstractions. Computational experiments have proven that the application of joint traversal provides up to a 16% performance increase by minimizing CPU cache misses. Furthermore, the decomposition of algorithms into Visitor events reduces the execution time for massive structures by up to 27% due to aggressive function inlining by the compiler.en_US
dc.description.abstractКвалiфiкацiйну роботу присвячено проблемi пiдвищення обчислювальної ефективностi структурних графових операторiв шляхом їх iнтеграцiї у подiє-орiєнтовану архiтектуру спiльного обходу засобами сучасного стандарту C++20. Встановлено архiтектурнi обмеження класичних узагальнених бiблiотек (на прикладi BGL) та сформульовано математичнi критерiї сумiсностi операторiв iз механiзмом спiльного обходу. Розроблено оригiнальний алгоритм побудови реберного графа та адаптовано iтеративний алгоритм розпiзнавання реберних графiв ILIGRA до виконання за один прохiд пошуку в ширину (BFS). Спроєктовано прототип графової бiблiотеки iз застосуванням статичних патернiв Вiдвiдувач та Компонувальник на базi концептiв (Concepts) iз нульовими накладними витратами. Обчислювальнi експерименти довели, що застосування спiльного обходу забезпечує до 16% приросту продуктивностi завдяки мiнiмiзацiї промахiв кешу процесора, а декомпозицiя алгоритмiв на подiї Вiдвiдувача скорочує час виконання масивних структур до 27% за рахунок агресивного вбудовування функцiй (inlining) компiлятором.uk_UA
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/40866
dc.language.isoukuk_UA
dc.statusfirst publisheduk_UA
dc.subjectтеорiя графiвuk_UA
dc.subjectреберний графuk_UA
dc.subjectалгоритм ILIGRAuk_UA
dc.subjectпатерни проєктуванняuk_UA
dc.subjectC++20uk_UA
dc.subjectспiльний обхiдuk_UA
dc.subjectпатерн Вiдвiдувачuk_UA
dc.subjectбакалаврська роботаuk_UA
dc.subjectgraph theoryen_US
dc.subjectline graphen_US
dc.subjectILIGRA algorithmen_US
dc.subjectdesign patternsen_US
dc.subjectC++20en_US
dc.subjectjoint traversalen_US
dc.subjectVisitor patternen_US
dc.titleЗастосування патернiв проектування в сучасному C++ для реалiзацiї операторiв на графахuk_UA
dc.typeOtheruk_UA
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
Nahornyi_Bakalavrska_robota.pdf
Size:
425.75 KB
Format:
Adobe Portable Document Format
Download
Thumbnail Image
Name:
Nahornyi_Bakalavrska_robota_1.pdf
Size:
321.69 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
F1 Прикладна математика