Пошук академічних текстів

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