Караваєв К. Д. Методи і алгоритми розв’язання класичних та узагальнених задач упорядкування вершин орграфів

English version

Дисертація на здобуття ступеня доктора філософії

Державний реєстраційний номер

0824U002290

Облікова картка дисертації

0824U002290.pdf

Здобувач

Спеціальність

  • 113 - Прикладна математика

Спеціалізована вчена рада

ДФ 08.051.086 ID 6112 Караваєв К.Д.

Дніпровський національний університет імені Олеся Гончара

Анотація

Дисертаційна робота присвячена розробці та обґрунтуванню точних та наближених методів і алгоритмів розв’язання класичних та узагальнених задач паралельного упорядкування вершин ациклічних орієнтованих графів. Наукова новизна результатів, описаних у дисертаційній роботі, полягає у наступному: вперше теоретично обґрунтовано можливість зведення будь-якої класичної задачі оптимального упорядкування до задачі із щільним упорядкуванням та шириною заданої парності; дістав подальшого розвитку класичний алгоритм розв’язання для двох виконавців для побудови щільних упорядкувань; вперше запропоновано підхід для скорочення перебору у методі гілок та меж за рахунок виключення гілок, що відповідають ізоморфним підграфам: розглянуті точні та наближені варіанти його реалізації; отримана необхідна умова існування щільних упорядкувань та запропоновані ефективні алгоритми її перевірки для загальної та спеціальної структур графів; вперше побудовано послідовність оцінок знизу довжини упорядкування, в якій кожна наступна оцінка, теоретично, є точнішою за попередні; дістав подальшого розвитку спосіб визначення діапазону допустимих місць вершин шляхом врахування ширини упорядкування; теоретично обґрунтовано можливість зведення задачі зі змінним значенням ширини упорядкування до класичної задачі; отримані нові наукові дані про поліноміальні наближені алгоритми для розв’язання задачі зі змінною шириною для вхідних бінарних дерев; вперше розглянуто клас узагальнених задач оптимального упорядкування з неповним завантаженням; проведено обчислювальні експерименти для визначення ефективності запропонованих методів та алгоритмів. Отримані результати можуть підвищити ефективність побудови розкладів виконання завдань у різних практично важливих сферах та галузях, зокрема у промисловому виробництві, питаннях логістики, пріоритетності використання та розподілу ресурсів, паралелізації та розподілення обчислень, обробки та моніторингу даних в режимі реального часу тощо. Також вони можуть мати важливе значення для подальшого розвитку сучасних технологій, зокрема автоматичного розпаралелення, та слугувати підґрунтям для нових напрямків наукових пошуків за цією тематикою.

Читати повністю

Публікації

1. Караваєв К. Д. Про необхідні умови існування щільних упорядкувань в класичній задачі паралельного упорядкування. Збірник наукових праць «Системні технології», м. Дніпро, 2024. Вип. 151. С. 76–91. DOI: https://doi.org/10.34185/1562-9945-2-151-2024-07.

2. Караваєв К. Д., Турчина В. А. Узагальнення задач упорядкування з урахуванням неповного завантаження. Збірник наукових праць «Питання прикладної математики і математичного моделювання», м. Дніпро, 2022. Вип. 22. С. 67–79. DOI: https://doi.org/10.15421/322207.

3. Караваєв К. Д., Турчина В. А. Аналіз впливу автоморфізму графу на схеми направленого перебору. Збірник наукових праць «Питання прикладної математики і математичного моделювання», м. Дніпро, 2021. Вип. 21. С. 94–104. DOI: https://doi.org/10.15421/322110.

4. Turchyna V., Karavaiev K. Analysis of algorithms for constructing dense sequencing of digraphs vertices. Proceedings of The Third International Workshop on Computer Modeling and Intelligent Systems (CMIS-2020), Zaporizhzhia, 2020. P. 690–703. DOI: https://doi.org/10.32782/cmis/2608-53.

5. Турчина В. А., Караваєв К. Д. Дослідження оцінок довжини паралельного упорядкування вершин графу. Збірник наукових праць «Питання прикладної математики і математичного моделювання», м. Дніпро, 2018. Вип. 18. С. 186–195. DOI: https://doi.org/10.15421/321819.

6. Турчина В. А., Караваєв К. Д. Контрприклад до алгоритму перерахування паралельно-послідовних графів без ізоморфізму. Математичне та програмне забезпечення інтелектуальних систем (MSSIS-2023): Матеріали XXI міжнародної науково-практичної конференції, 22-24 листопада 2023 р., м. Дніпро, 2023. С. 291–292. URL: http://mpzis.dnu.dp.ua/wp-content/uploads/2023/11/mpzis-2023.pdf.

7. Караваєв К. Д., Турчина В. А. Про необхідні та достатні умови наявності автоморфізму у паралельно-послідовних графах. Комбінаторні конфігурації та їхні застосування: Матеріали XXV Міжнародного науково-практичного семінару імені А. Я. Петренюка, (Запоріжжя – Кропивницький, 14-16 червня 2023 року) / за ред. Г.П. Донця, м. Запоріжжя - Кропивницький, 2023. C. 122–129. URL: https://zp.edu.ua/uploads/dept_s&r/2023/conf/1.4/Petrenyuk_ISPS-25-proc.pdf.

8. Караваєв К. Д. Використання інваріантів графів для скорочення напрямленого перебору у задачах упорядкування. Математичне та програмне забезпечення інтелектуальних систем (MSSIS-2022): Матеріали XX ювілейної міжнародної науково-практичної конференції, 23-25 листопада 2022 р., м. Дніпро, 2022. С. 96–97. URL: http://mpzis.dnu.dp.ua/wp-content/uploads/2022/12/MPZIS-2022-1.pdf.

9. Караваєв К. Д., Турчина В. А. Про зв’язок задач ізоморфізму графів та упорядкування їх вершин. Комбінаторні конфігурації та їхні застосування: Матеріали XXIV Міжнародного науково-практичного семінару імені А. Я. Петренюка, (Запоріжжя – Кропивницький, 13-14 травня 2022 року) / за ред. Г.П. Донця, м. Запоріжжя - Кропивницький, 2022. C. 30–33. URL: https://zp.edu.ua/uploads/dept_s&r/2023/conf/1.4/Petrenyuk_ISPS-25-proc.pdf.

10. Караваєв К. Д., Турчина В. А. Деякі узагальнення задачі паралельного упорядкування. Комбінаторні конфігурації та їхні застосування: Матеріали XXIII Міжнародного науково-практичного семінару імені А. Я. Петренюка, присвяченого 70-річчю Льотної академії Національного авіаційного університету, (Запоріжжя – Кропивницький, 13-15 травня 2021 року) / за ред. Г.П. Донця, м. Запоріжжя - Кропивницький, 2021. C. 93–97. URL: https://www.glau.kr.ua/images/docs/sbornik/materiali_23_mnp_seminaru.pdf.

10. Караваєв К. Д., Турчина В. А. Деякі узагальнення задачі паралельного упорядкування. Комбінаторні конфігурації та їхні застосування: Матеріали XXIII Міжнародного науково-практичного семінару імені А. Я. Петренюка, присвяченого 70-річчю Льотної академії Національного авіаційного університету, (Запоріжжя – Кропивницький, 13-15 травня 2021 року) / за ред. Г.П. Донця, м. Запоріжжя - Кропивницький, 2021. C. 93–97. URL: https://www.glau.kr.ua/images/docs/sbornik/materiali_23_mnp_seminaru.pdf.

11. Karavaiev K., Turchyna V., Hurko O. The problem of consistencing the architecture of computational systems and algorithms. Сучасні науково-технічні дослідження у контексті мовного простору (іноземними мовами) 13 травня 2021 року: матеріали X Регіональної науково-практичної конференції молодих учених та студентів, м. Дніпро, 2021. С. 142–145. URL: https://www.dnu.dp.ua/docs/ndc/2021/19_Сучасні%20науково-технічні%20дослідження%20у%20контексті%20мовного%20простору.pdf.

12. Турчина В. А., Караваєв К. Д. Дослідження оцінки точності алгоритму, заснованого на лексикографічному порядку. Математичне та програмне забезпечення інтелектуальних систем (MSSIS-2019): Матеріали XVІІ міжнародної науково-практичної конференції, 20-22 листопада 2019 р., м. Дніпро, 2019. С. 258–259. URL: http://mpzis.dnu.dp.ua/wp-content/uploads/2019/12/MPZIS_2019.pdf.

13. Турчина В. А., Караваєв К. Д. Застосування рівневого принципу до аналізу задач паралельного упорядкування та їх узагальнення. Міжнародний науковий симпозіум «Інтелектуальні рішення». Обчислювальний інтелект (результати, проблеми, перспективи): праці міжнар. наук.-практ. конф., 15-20 квітня 2019 р., м. Ужгород, 2019. С. 56–57. URL: https://er.chdtu.edu.ua/bitstream/ChSTU/3192/1/OI-2019.pdf.

Читати повністю

Схожі дисертації

0824U002255

Гусак Віталій Олександрович

Шляхи підвищення ефективності чисельно-аналітичних методів розв’язку граничних задач для неканонічних областей

0824U002172

Харьков Олег Сергійович

Модифiкованi екстраградiєнтнi алгоритми для варiацiйних нерiвностей та їх застосування

0824U002162

Масаликін Станіслав Сергійович

Статистичне моделювання енергетичних потоків в системах концентрації енергії Сонця

0824U002163

Борисенко Андрій Геннадійович

Математичне та комп’ютерне моделювання теплообміну в нанорідинному теплоносії сонячних термодинамічних станцій

0824U002179

Юрков Роман Сергійович

Моделювання енергетичних потоків в теплових акумуляторах з фазовим переходом “тверде тіло – рідина”