|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Нейросетевой подход к проблеме изоморфизма графовдипломная работа (Бакалавр)
- Научный руководитель: Половников В.С.
- Автор: Измайлова А.А.
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2018
- Аннотация: Проблема проверки изоморфизма произвольных графов сложна и актуальна. Относительно недавно Ласло Бабаи опубликовал квази-полиномиальный алгоритм проверки изоморфизма. Для некоторых классов графов удаётся доказать даже полиномиальность сложности решения задачи изоморфизма. В частности, существует линейный алгоритм проверки изоморфизма деревьев, рассмотренный Александрой ранее в её курсовой работе. В выпускной работе Измайловой А.А. была поставлена задача схемной реализации алгоритма проверки изоморфизма деревьев в нейросетевом базисе. То есть построить нейронную схему без памяти для решения задачи изоморфизма деревьев. Возможно, полученная нейросетевая архитектура может быть доучена для решения задачи изоморфизма в более широком классе графов. Александрой была написана программа на javascript, действующая со всеми ограничениями нейронных схем, по которой впоследствии была построена и протестирована требуемая схема. Для сортировки наборов в лексикографическом порядке реализован алгоритм битонической сортировки (схемная сортировка за время порядка log^2 n). Для этого потребовалось реализовать компаратор в нейросетевом базисе. Нелинейная глубина полученной схемы составила O(n), что соответствует обычному (не нейросетевому) алгоритму.
- Добавил в систему: Половников Владимир Сергеевич