Реєстраційний номер
0412U002676, Кандидатська дисертація
На здобуття
к.ф.-м.н.
Дата захисту
18-05-2012
Статус
Захищена
Назва роботи
Розробка методів і алгоритмів розв'язання аномальних та узагальнених задач паралельного упорядкування
Здобувач
Федоренко Наталія Костянтинівна,
Керівник Турчина Валентина Андріївна
Опонент Козін Ігор Вікторович
Опонент Ус Світлана Альбертівна
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Дніпропетровський національний університет імені Олеся Гончара
Опис
Об'єкт - оптимізаційні задачі на графах та методи їх розв'язання. Мета - розробка методів та алгоритмів розв'язання аномальних та узагальнених задач паралельного упорядкування. Методи - методи дискретної оптимізації, комбінаторного аналізу, статистичного аналізу. У роботі сформульовано та доведено необхідні умови виникнення чотирьох основних типів аномалій для задачі побудови паралельного упорядкування заданої ширини та мінімальної довжини для орграфів із неодиничними вагами вершин за умови заданого списку пріоритетів і для двоїстої до неї задачі. Виділено класи орграфів, для яких наявність транзитивних дуг не впливає на оптимальність алгоритму, заснованого на розстановці лексикографічних поміток, а також класи орграфів, для яких наявність транзитивних дуг завжди впливатиме на оптимальність. Визначено необхідні умови, за яких в оптимальному розв'язку задачі паралельного упорядкування спостерігатиметься порушення рівневого принципу. Запропоновано оцінки ширини упорядкування при розв'язанні задачі побудови паралельного упорядкування заданої довжини і мінімальної ширини. Розроблено алгоритми розв'язання класичних та узагальнених задач паралельного упорядкування, а саме, алгоритми побудови оптимального паралельного упорядкування мінімальної ширини при заданій довжині, алгоритм побудови всіх паралельних упорядкувань заданої довжини, алгоритми побудови паралельних упорядкувань заданої ширини, а також паралельних упорядкувань із шириною, що задана обмежуючою послідовністю, і алгоритми побудови паралельних упорядкувань для орграфів із двома типами вершин. Сфера - розпаралелення обчислень, управління ресурсами, навчальний процес.
Дата реєстрації
2012-05-31
Додано/оновлено в НРАТ
2020-04-04 / 2026-06-30
