Реєстраційний номер
0416U002213, Кандидатська дисертація
На здобуття
к.ф.-м.н.
Дата захисту
28-04-2016
Статус
Захищена
Назва роботи
Розпізнавання графів за допомогою колективу агентів.
Здобувач
Стьопкін Андрій Вікторович,
Керівник Грунський Ігор Сергійович
Опонент Кривий Сергій Лук"янович
Опонент Годлевський Олександр Богуславович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Київський національний університет імені Тараса Шевченка
Опис
Диссертационная работа посвящена проблеме анализа свойств конечных простых неориентированных графов - проблеме распознавания графа при помощи коллектива агентов, а именно исследованию самого процесса распознавания графа с целью повышения эффективности его распознавания. При этом одним из центральных моментов исследования является изучение сложности коммуникации между агентами. Предложен новый метод распознавания графа, при помощи построения на его вершинах неявной нумерации, путем разметки элементов графа с помощью красок. На основе этого метода разработан базовый алгоритм, в котором каждый агент-исследователь использует две различные краски (всего три краски). В этом алгоритме впервые, наряду с временной T n , емкостной S n сложностями и числом переходов по ребрам, совершаемых агентами-исследователями, исследуется коммуникационная сложность K n - сложность, определяемая количеством и объемом сообщений, которыми нужно обменяться агентам-исследователям с агентом-экспериментатором для распознавания графа. Базовый алгоритм распознавания имеет кубические, от числа вершин графа, временную и коммуникационную сложности, квадратичную емкостную сложность и кубическую верхнюю оценку числа переходов по ребрам, совершаемых агентами-исследователями.
Дата реєстрації
2016-05-19
Додано/оновлено в НРАТ
2020-04-03 / 2026-06-29