|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Определение группы преобразований кубика Рубика размера 2 и нахождение минимального алгоритма его сборки для любой конкретной позициидипломная работа (Бакалавр)
- Научный руководитель: Борисенко Владимир Витальевич
- Автор: Абдулханонов Довар Комилович
- Тип: Бакалавр
- Организация, в которой проходила защита: Филиал МГУ им. М.В.Ломоносова в г. Душанбе
- Год защиты: 2020
- Аннотация: Вычисляется группа вращений кубика Рубика размера 2x2x2 и минимальное представление каждого ее элемента в виде произведения порождающих этой группы, соответствующих вращениям граней кубика. Это для произвольной позиции кубика предоставляет алгоритм его сборки за минимальное число вращений. Определено максимальное число вращений, достаточное для сбоки кубика из любой позиции -- 11 вращений. Алгоритм вычисления группы основан на алгоритме роста области из семени, алгоритм представления элементов группы в виде минимального произведения основан на алгоритме Дейкстры нахождения минимального пути в графе. Все алгоритмы реализованы на языке C++, причем время работы программы составляет около 5 часов. При реализации алгоритмов особое внимание уделялось экономии памяти, в частности, максимально компактному представлению элементов группы, поскольку ее порядок составляет 88,179,840. В результате при работе программа использует около 7.1 Gib памяти, что позволяяет ее успешно выполнять на компьютере с 8 Gb памяти и операционной системой Linux.
- Добавил в систему: Борисенко Владимир Витальевич