|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Об алгоритмическом подходе к детектированию графов Муракурсовая работа (Специалист)
- Научный руководитель: Половников В.С.
- Автор: Ананьев К.Ю.
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Кафедра математической теории интеллектуальных систем
- Год защиты: 2015
- Курс: 4
- Аннотация: Регулярные графы с минимальным количеством вершин при заданном обхвате (графы-клетки) возникают во многих практически важных задачах, например, в теории помехоустойчивого кодирования. По значениям обхвата n и степени вершин r регулярного графа достаточно просто выводится нижняя оценка на общее количество вершин в таком графе (оценка Мура), но вопрос существования графа с заданными параметрами оказался сложным. Если существует (r,n)-клетка с количеством вершин, совпадающим с нижней оценкой, то такой граф называется графом Мура. В настоящее время построены некоторые классы графов Мура и доказаны теоремы о свойствах таких графов, например, теорема Хоффмана-Синглтона гласит, что все графы Мура обхвата 5 могут иметь степень вершин r лишь равное 2,3,7 и возможно 57. Общего подхода к генерации клеток, а следовательно графов Мура помимо переборных на данный момент не существует. Ананьев К.Ю. изучил нижние оценки Мура, придумал алгоритм разумного перебора для нахождения и построения графов Мура для четного обхвата, теоретически оценил количество операций и создал программу для ЭВМ, позволяющую генерировать графы Мура для малых значений (r,n).
- Добавил в систему: Половников Владимир Сергеевич