Кандидатська дисертація. Шило Петро Володимирович. Алгоритми розв'язання окремих класів задач дискретної оптимізації великої розмірності

Реєстраційний номер

0417U004117, Кандидатська дисертація

На здобуття

к.ф.-м.н.

Дата захисту

27-10-2017

Статус

Захищена

Назва роботи

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

Здобувач

Шило Петро Володимирович,

Керівник Сергієнко Іван Васильович
Опонент Михайлюк Віктор Олексійович
Опонент Чупов Сергій Вікторович

Установа, організація, у вченій раді якої відбудеться/відбувся захист

Інститут кібернетики ім. В.М.Глушкова НАН України

Опис

Розроблено нові алгоритми розв'язання задач дискретної оптимізації великої розмірності, а саме: задач про покриття множини та про покриття множини мінімальної потужності, квадратичної задачі про призначення, задачі побудови завадозахищеного коду максимального обсягу для Z-каналу, яка зводиться до задачі знаходження максимальної незалежної множини вершин графу. Серед запропонованих є алгоритми: глобального рівноважного пошуку, випадкового локального пошуку, табу та точний алгоритм гілок і меж. На основі експериментальних досліджень проведено порівняльний аналіз кращих відомих та розроблених автором алгоритмів, який підтвердив переваги останніх за швидкодією та якістю отриманих розв'язків. З використанням портфелів та команд алгоритмів глобального рівноважного пошуку розроблено та досліджено паралельні алгоритми розв'язання задач про максимальний зважений розріз графу та булевого квадратичного програмування без обмежень, які дають змогу суттєво прискорити цей процес та розв'язувати за рахунок цього задачі великої розмірності.

Дата реєстрації

2017-11-02

Додано/оновлено в НРАТ

2020-04-03 / 2026-06-29