Registration Number
0416U002213, Candidate dissertation
Status
к.ф.-м.н.
Date
28-04-2016
popup.evolution
.
Title
Graphs exploration with the help of the collective of agents.
Author
Stepkin Andrey Viktorovich,
popup.head Hrunskyy Igor Sergeevich
popup.opponent Кривий Сергій Лук"янович
popup.opponent Годлевський Олександр Богуславович
popup.rada
Taras Shevchenko Kiev University
Description
Диссертационная работа посвящена проблеме анализа свойств конечных простых неориентированных графов - проблеме распознавания графа при помощи коллектива агентов, а именно исследованию самого процесса распознавания графа с целью повышения эффективности его распознавания. При этом одним из центральных моментов исследования является изучение сложности коммуникации между агентами. Предложен новый метод распознавания графа, при помощи построения на его вершинах неявной нумерации, путем разметки элементов графа с помощью красок. На основе этого метода разработан базовый алгоритм, в котором каждый агент-исследователь использует две различные краски (всего три краски). В этом алгоритме впервые, наряду с временной T n , емкостной S n сложностями и числом переходов по ребрам, совершаемых агентами-исследователями, исследуется коммуникационная сложность K n - сложность, определяемая количеством и объемом сообщений, которыми нужно обменяться агентам-исследователям с агентом-экспериментатором для распознавания графа. Базовый алгоритм распознавания имеет кубические, от числа вершин графа, временную и коммуникационную сложности, квадратичную емкостную сложность и кубическую верхнюю оценку числа переходов по ребрам, совершаемых агентами-исследователями.
Registration Date
2016-05-19
popup.nrat_date
2020-04-03 / 2026-06-29