Search academic texts

Information × Registration Number 0824U002290, PhD dissertation Status Доктор філософії Date 06-06-2024 popup.evolution . Title Methods and algorithms for solving classical and generalised problems of digraph vertices sequencing Author Kostiantyn D. Karavaiev, popup.head Valentyna A. Turchyna popup.opponent Maryna F. Semeniuta popup.opponent Oksana S. Pichugina popup.opponent Igor V. Kozin popup.review Natalia A. Guk Description Дисертаційна робота присвячена розробці та обґрунтуванню точних та наближених методів і алгоритмів розв’язання класичних та узагальнених задач паралельного упорядкування вершин ациклічних орієнтованих графів. Наукова новизна результатів, описаних у дисертаційній роботі, полягає у наступному: вперше теоретично обґрунтовано можливість зведення будь-якої класичної задачі оптимального упорядкування до задачі із щільним упорядкуванням та шириною заданої парності; дістав подальшого розвитку класичний алгоритм розв’язання для двох виконавців для побудови щільних упорядкувань; вперше запропоновано підхід для скорочення перебору у методі гілок та меж за рахунок виключення гілок, що відповідають ізоморфним підграфам: розглянуті точні та наближені варіанти його реалізації; отримана необхідна умова існування щільних упорядкувань та запропоновані ефективні алгоритми її перевірки для загальної та спеціальної структур графів; вперше побудовано послідовність оцінок знизу довжини упорядкування, в якій кожна наступна оцінка, теоретично, є точнішою за попередні; дістав подальшого розвитку спосіб визначення діапазону допустимих місць вершин шляхом врахування ширини упорядкування; теоретично обґрунтовано можливість зведення задачі зі змінним значенням ширини упорядкування до класичної задачі; отримані нові наукові дані про поліноміальні наближені алгоритми для розв’язання задачі зі змінною шириною для вхідних бінарних дерев; вперше розглянуто клас узагальнених задач оптимального упорядкування з неповним завантаженням; проведено обчислювальні експерименти для визначення ефективності запропонованих методів та алгоритмів. Отримані результати можуть підвищити ефективність побудови розкладів виконання завдань у різних практично важливих сферах та галузях, зокрема у промисловому виробництві, питаннях логістики, пріоритетності використання та розподілу ресурсів, паралелізації та розподілення обчислень, обробки та моніторингу даних в режимі реального часу тощо. Також вони можуть мати важливе значення для подальшого розвитку сучасних технологій, зокрема автоматичного розпаралелення, та слугувати підґрунтям для нових напрямків наукових пошуків за цією тематикою. Registration Date 2024-06-20 popup.nrat_date 2024-07-22 Close