Пошук академічних текстів

Інформація × Реєстраційний номер 0824U002290, Дисертація доктора філософії На здобуття Доктор філософії Дата захисту 06-06-2024 Статус Захищена Назва роботи Методи і алгоритми розв’язання класичних та узагальнених задач упорядкування вершин орграфів Здобувач Караваєв Костянтин Дмитрович, Керівник Турчина Валентина Андріївна Опонент Семенюта Марина Фролівна Опонент Пічугіна Оксана Сергіївна Опонент Козін Ігор Вікторович Рецензент Гук Наталія Анатоліївна Опис Дисертаційна робота присвячена розробці та обґрунтуванню точних та наближених методів і алгоритмів розв’язання класичних та узагальнених задач паралельного упорядкування вершин ациклічних орієнтованих графів. Наукова новизна результатів, описаних у дисертаційній роботі, полягає у наступному: вперше теоретично обґрунтовано можливість зведення будь-якої класичної задачі оптимального упорядкування до задачі із щільним упорядкуванням та шириною заданої парності; дістав подальшого розвитку класичний алгоритм розв’язання для двох виконавців для побудови щільних упорядкувань; вперше запропоновано підхід для скорочення перебору у методі гілок та меж за рахунок виключення гілок, що відповідають ізоморфним підграфам: розглянуті точні та наближені варіанти його реалізації; отримана необхідна умова існування щільних упорядкувань та запропоновані ефективні алгоритми її перевірки для загальної та спеціальної структур графів; вперше побудовано послідовність оцінок знизу довжини упорядкування, в якій кожна наступна оцінка, теоретично, є точнішою за попередні; дістав подальшого розвитку спосіб визначення діапазону допустимих місць вершин шляхом врахування ширини упорядкування; теоретично обґрунтовано можливість зведення задачі зі змінним значенням ширини упорядкування до класичної задачі; отримані нові наукові дані про поліноміальні наближені алгоритми для розв’язання задачі зі змінною шириною для вхідних бінарних дерев; вперше розглянуто клас узагальнених задач оптимального упорядкування з неповним завантаженням; проведено обчислювальні експерименти для визначення ефективності запропонованих методів та алгоритмів. Отримані результати можуть підвищити ефективність побудови розкладів виконання завдань у різних практично важливих сферах та галузях, зокрема у промисловому виробництві, питаннях логістики, пріоритетності використання та розподілу ресурсів, паралелізації та розподілення обчислень, обробки та моніторингу даних в режимі реального часу тощо. Також вони можуть мати важливе значення для подальшого розвитку сучасних технологій, зокрема автоматичного розпаралелення, та слугувати підґрунтям для нових напрямків наукових пошуків за цією тематикою. Дата реєстрації 2024-06-20 Додано в НРАТ 2024-07-22 Закрити