Search academic texts

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