Хитроумный кубик Рубика. Научные игрушки. Кубик Рубика в наше время. Решение головоломки - последние вращения

В 1975 году скульптор Эрне Рубик запатентовал свое изобретение под названием "Магический куб". Уже более 40 лет все права на головоломку принадлежат компании близкого друга изобретателя - Тома Кренера - под названием Seven Towns Ltd. Английская фирма контролирует производство и продажу кубика по всему миру. В Венгрии, Германии, Португалии и сохранила свое первоначальное название, в других странах игрушку называют кубиком Рубика.

Разновидности головоломки

Классический кубик Рубика имеет размеры 3 на 3 квадрата. Со временем придумали огромное количество форм и размеров для игрушки. Никого уже не удивить головоломкой в виде пирамиды или размером кубика 17х17. Однако человечество никогда не останавливается на достигнутом.

Очевидно, что не существует схемы сборки для начинающих этого кубика. Процесс сборки и решения головоломки может занять годы. В последнее время интерес к кубику растет не только в Азии и Европе, но и там, где игрушка была не очень популярна, например, в США. Один из поклонников кубика Рубика снял на видео сборку головоломки 17 на 17. Общая длина ролика 7,5 часов, съемки проводились в течение недели.

Растущий спрос рождает предложение. Иногда продаваемые модели невероятны и не всегда понятно, как же они будут выглядеть в собранном виде. В каждой стране есть свои любимые разновидности игрушки.

Что такое спидкубинг?

Поклонники игры устраивают настоящие соревнования по скорости сборки кубика. В продаже имеются специальные "скоростные" головоломки. Механизм вращения таких кубиков Рубика очень качественный, а повороты граней и рядов можно совершать движением одного пальца.

World Cube Association (WCA) - это некоммерческая организация, поддерживающая движение спидкубинга. WCA регулярно устраивает соревнования по всему миру. Практически во всех странах есть представители организации. Стать участником мероприятия по спидкубингу может любой, нужно лишь зарегистрироваться на сайте и уложиться в норматив по сборке. Самая популярная дисциплина на таких соревнованиях - это скоростная сборка кубика Рубика 3х3. Норматив для участия составляет 3 минуты, но даже если человек не сможет решить задачу за отведенное время, его все равно допустят до мероприятия. Записаться можно на любую дисциплину, но приходить нужно со своей головоломкой.

Рекорд сборки кубика Рубика 3х3 принадлежит роботу Sub1, созданному инженером Альбертом Биром. Машина способна решить головоломку за доли секунды, тогда как человеку потребуется на это 4,7 секунды (достижение Матса Валка 2016 года). Как видно, участникам движения спидкубинга есть на кого равняться.

Какие существуют алгоритмы сборки кубика Рубика 3х3?

Существует множество способов решить известную головоломку. Разработаны варианты схем сборки кубика Рубика 3х3 как для начинающих, так и для продвинутых людей с усложненными схемами: 4х4, 6х6 и даже 17х17.

Вариант головоломки 3х3 считается любимой классикой у большинства поклонников. Поэтому инструкций как собрать кубик Рубика 3х3 гораздо больше, чем каких - либо еще.

Как должна выглядеть головоломка?

Собрать игрушку по схеме можно лишь из заранее подготовленной позиции. Если узоры на гранях кубика расположены неправильно, то решить его через алгоритм сборки кубика рубика 3х3 для начинающих не получиться. Существует набор таких позиций для разных вариантов решения.

На рисунке изображен или просто "крест" - отправная точка самого простого способа собрать кубик Рубика 3х3. Рекомендуется разобрать и сложить игрушку правильно.

Обозначения схем и способы вращения кубика

Прежде, чем приступить к разборке формул кубика Рубика 3х3, стоит выучить обозначения используемые в спидкубинге. Все движения головоломки обозначаются заглавными буквами. Отсутствие апострофа над символом означает то, что вращение осуществляется по часовой стрелке, если знак есть, то вращать следует в обратном направлении.

Общепринятыми считаются первые буквы английских (или русских) слов обозначающих движения:

• front - F или Ф - вращение фронтальной стороны;
• back - B или Т - вращение задней стороны;
• left - L или Л - вращение левого ряда;
• right - R или П - вращение правого ряда;
• up - U или В - вращение верхнего ряда;
• down -D или Н - вращение нижнего ряда.

Также могут использоваться указатели для изменения положения кубика в пространства - движения перехвата. Здесь тоже все просто, из школьного курса геометрии всем известны оси координат X, Y и Z. Движение X означает, что кубик необходимо повернуть гранью F на место грани U, при сдвиге Y - F становиться на место L, а при вращении Z - F перемещается на R.

Следующая группа обозначений используется редко, ее применяют при составлении схем узоров:

• M - поворот среднего ряда, между правым (R/П) и левым (L/Л);
• S - поворот среднего ряда, между фронтальным (F/Ф) и тыльным (B/Т);
• E - поворот среднего ряда, между верхним (U/В) и нижним (D/Н).

Зачем собирают узоры на гранях кубика?

На встречах по спидкубингу соревнуются не только в решении головоломки, но и в умении составлять различные узоры на кубике Рубика 3х3. Делают это для того, чтобы быстро и просто собирать кубик в нужную позицию.

Существует огромное количество схем по сборке самых разных узоров: "точки", "шахматы", "точки с шахматами", "зигзаг", "мезон", "кубик в кубе в кубе" и многие другие. Только для классической головоломки их существует более 46. Мастера спидкубинга считают зазорным разбирать игрушку. Также составление узоров на кубике Рубика 3х3 - это прекрасный способ тренировки и улучшения навыков.

На рисунке изображены варианты различных узоров головоломки. Далее приведены еще несколько формул для сборки самых интересных рисунков из позиции крест:

• шахматы - M 2 E 2 S 2 ;
• зигзаг - (ПЛФТ) 3;
• четыре z - (ПЛФТ) 3 В 2 Н 2 ;
• крест Пламмера - ТФ 2 Н"П 2 ФНТ"ФН"ВФ"Н"Л 2 ФН 2 В";
• кубик в кубе в кубе - В"Л 2 Ф 2 Н"Л"НВ 2 ПВ"П"В 2 П 2 ПФ"Л"ВП".

Алгоритм сборки кубика Рубика 3х3 для начинающих

Хотя способов решения головоломки множество, простые и понятные схемы для новичков найти не так просто. С каждым пройденным этапом сборки, формулы кубика Рубика 3х3 становятся сложнее. Нужно не только правильно изменить узор, но и сохранить то, что сделано до этого. Ниже будет приведен один из вариантов, как легко собрать кубик Рубика 3х3.

Условно весь процесс можно разбить на следующие этапы:

1. Сборка креста в верхней грани кубика.
2. Правильное составление всей верхней грани.
3. Работа над средним слоев.
4. Правильная сборка ребер последнего ряда.
5. Сборка креста нижней грани.
6. Правильное ориентирование углов последней грани кубика.

Решение головоломки - подготовительная работа

Первый этап самый легкий. Новички могут попробовать свои силы и потренироваться в составлении узоров кубика по имеющимся инструкциям, но этот процесс займет много времени.

Нужно выбрать верхнюю грань и цвет, который будет собираться первым. Алгоритм сборки кубика Рубика 3х3 для начинающих разработан с позиции "крест". Сделать его несложно, необходимо выбрать центральный цвет, найти 4 реберных элемента того же оттенка и поднять их на выбранную грань. Цветная стрелочка на картинке указывает на искомую часть. Варианты расположения нужного элемента могут быть разными, в зависимости от этого описаны 2 последовательности действий А и Б. Трудность заключается в том, чтобы продолжить крест по боковым сторонам кубика. Более внимательно рассмотреть конечный вид этапа можно на изображении, размещенном выше.

Решение головоломки - работа над средним рядом

На этом этапе схемы сборки кубика Рубика 3х3 для начинающих необходимо найти и собрать угловые элементы верхней грани. В конечном результате должна быть полностью решена грань с крестом и верхний ряд головоломки.

На изображении приведены три случая возможного узора граней. Выбирая один из способов А, Б или В необходимо собрать все 4 угла кубика. Запоминая алгоритмы вращения и отрабатывая их, приобретаются навыки и мастерство сборки головоломки. Рассматривать формулы и представлять процесс - бессмысленно, гораздо проще взять кубик и попробовать все способы на практике.

Третий этап кажется простым, но это только видимость. Для его решения описаны две ситуации узоров и соответственно составлены две формулы вращения. Применяя их, стоит помнить о сохранении ранее достигнутых результатов. Мастера постоянно держат в памяти 3-4 последних вращений, чтобы в случае неудачи вернуть кубик к первоначальному состоянию.

Для решения головоломки ее нужно вращать по оси координат в поиске необходимых элементов и работы с ними. Такие движения редко отображаются в формулах, только в особых случаях. Рекомендуется начать сборку реберных граней с элементов нижних рядов, после таких вращений все нужные кубики спустятся из среднего в нижний ряд.

Решение головоломки - составление второго креста

На четвертом этапе игрушку переворачивают "вверх тормашками". Решение последней грани - самая сложная часть алгоритма сборки кубика Рубика 3х3 для начинающих. Формулы вращений длинные и сложные, их выполнение потребует особой внимательности. Цель действий - расположить реберные элементы на своих места для дальнейшего составления креста. Ориентация реберных частей может быть неправильной. Формула движений кубика всего одна и применять ее следует пока не будет достигнута цель этапа.

Вращения пятого этапа направлены на разворот элементов правильной стороной. Его особенность заключается в том, что применяется одна и та же формула вращения для всех трех узоров на рисунке, разница лишь в ориентации самого кубика.

Формулы для движений 5 этапа выглядят следующим образом:

• (ПС Н) 4 В (ПС Н) 4 В" - вариант «А»;
• (ПС Н) 4 В" (ПС Н) 4 В - вариант «Б»;
• (ПС Н) 4 В 2 (ПС Н) 4 В 2 - вариант «В».

С Н - это поворот среднего ряда по часовой стрелке, а показатель степени над скобочкой - количество повторений действий в скобках.

Решение головоломки - последние вращения

На шестом этапе, как и на четвертом, нужные кубики расставляются по своим местам, безотносительно их ориентации. Головоломку следует повернуть так, чтобы элемент, который уже на нужном месте, располагался в левом дальнем углу наверху кубика. Варианты, предложенные для решения формулы, зеркально отражают друг друга. Повторять вращения необходимо до достижения желаемого результата.

Седьмой этап самый торжественный и самый трудный. При вращениях кубика нарушения в уже собранных рядах неизбежны. Потребуется полностью сосредоточить внимание на движениях, иначе результат сборки может быть безвозвратно загублен. Как и в пятом этапе, последовательность движений всего одна, но повторяется по 4 раза. Сначала совершаются вращения для ориентации элемента, затем обратные - для восстановления нарушенных рядов.

Не следует забывать о записи движений при помощи знаков английского алфавита. Формулы движений граней и рядов кубика данного этапа выглядят следующим образом:

• (RF"R"F) 2 U (RF"R"F) 2 - вариант «а»;
• (RF"R"F) 2 U" (RF"R"F) 2 - вариант «б»;
• (RF"R"F) 2 U 2 (RF"R"F) 2 - вариант «в».

В - поворот верхней грани на 90 градусов, В" - поворот той же грани против часовой стрелки, а В 2 - двойной поворот.

Сложность этапа в правильной оценке расположения элементов и выборе необходимого варианта вращений. Новичкам бывает трудно сразу правильно определить узор и сопоставить его с правильной формулой.

Кубик Рубика и дети

Хитрая головоломка интересна не только взрослым, но и детям. Мировыми рекордсменами по сборке кубика Рубика становились подростки. В 2015 году Колин Бернс, которому на тот момент было только 15 лет, собрал игрушку за 5,2 секунды.

Простая, но увлекательная игрушка продолжает интересовать подрастающее поколение вот уже 5 десятилетие. Детское увлечение нередко перерастает в профессию. Существуют математические способы оценки решения задач кубика Рубика. Данный раздел математики используют при составлении и написании алгоритмов решения для автоматизированных вычислительных машин. Роботы, которые действительно ищут пути сборки кубика, а не выполняют заранее вбитый алгоритм движений, решают головоломку за 3 секунды, например, CubeStormer 3.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Национальный аэрокосмический университет им. Н.Е. Жуковского

«Харьковский авиационный институт»

КУРСОВАЯ РАБОТА

по дисциплине: «Основы системного анализа»

на тему: СИСТЕМНЫЙ АНАЛИЗ ГРУПП ПРЕОБРАЗОВАНИЙ СОСТОЯНИЙ КУБИКА РУБИКА

г. Харьков - 2014 год

Введение

1.1 Актуальность работы

1.2 Дерево проблем

1.3 Дерево целей

3.4.1 Алгоритм Тистлетуэйта

3.4.2 Алгоритм Коцембы

Заключение

Список литературы

Приложение

Введение

Кубик Рубика - одна из популярнейших в мире головоломок. Её создал в 1975 году Эрнё Рубик (Erne Rubik, Rubik Ernх) -- венгерский изобретатель, скульптор и профессор архитектуры.

В 1971 году Эрнё был назначен преподавателем Академии прикладных искусств. Среди прочих дисциплин он преподавал трехмерное моделирование. По одной из версий, при помощи данного учебного пособия Рубик пытался объяснить студентам основы математической теории групп. Задача изобретателя была такова: заставить отдельные разноцветные кубики свободно вращаться на своих местах, не нарушая конструктивного единства всего приспособления.

Самому изобретателю потребовался месяц, чтобы собрать кубик, после создания первой модели.

В течение последующих 40 лет ведущие математики и программисты пытались найти кратчайший алгоритм сборка кубика Рубика. На данный момент кратчайший алгоритм не найден.

В первой главе данной работы приведен обзор литературы, сделаны выводы по результатам обзора информационных источников. Также представлены дерево проблем и дерево целей, определена цель исследования. Определен объект исследования, приведено доказательство того, что объект исследования является объектом с точки зрения системного анализа. Определен предмет исследования.

Во второй главе содержится анализ предмета исследования. Приведены структурный, функциональный, информационный и классификационный виды анализа исследуемого объекта.

В третьей главе обоснован выбор модельного представления объекта исследования. Приведены входные и выходные величины, а также основные уравнения, описывающие объект исследования.

В заключении представлены выводы, предложения и рекомендации, показана практическая значимость работы.

дефрагментация кубик рубик математический

1. Системный анализ групп преобразования состояний кубика Рубика

1.1 Актуальность работы

Кубик Рубика - это пластмассовый куб, разбитый на 27 конгруэнтных кубиков. Внутренний кубик удален, а 26 наружных кубиков соединены так, что любая грань из 9 кубиков, прилегающих к одной грани куба, может быть повернута в любом направлении на 900. После поворота на 900 вся система сохраняет прежнюю свободу вращений: снова любую грань в любом направлении можно повернуть в ее плоскости на 900.

Первоначально каждая из граней большого куба окрашена в свой цвет (красный, оранжевый, желтый, зеленый, синий, белый). После ряда случайно выбранных вращений окраска граней куба становится пестрой: на грани присутствуют клетки разных цветов. Решение головоломки состоит в том, чтобы с помощью вращений добиться изначальной расстановки кубиков, т.е. такой расстановки, при которой каждая грань куба снова будет одного цвета.

«Джон Конвей, один из крупнейших специалистов по теории групп в мире, либо один из его коллег в Кембридже определил кратчайший путь из любого данного состояния назад к начальному состоянию как «Алгоритм Бога» .

Число комбинаций кубиков, которые можно получить вращением граней (подсчитано, что их N = 43 252 003 274 489 856 000, т.е. более 43 квинтиллионов) делает ее недоступной для перебора даже на ЭВМ. Можно заметить, что не любая комбинация может быть получена вращением граней куба: если разрешить разборку куба на составляющие его 26 кубиков, то можно составить 12N = 529024039393878272000 различных комбинаций.

1.2 Дерево проблем

Основную проблему данной работы, можно разбить на подпроблемы и представить в виде дерева проблем (см. рис. 1.1)

1. Сложность последовательной обработки всех возможных различных состояний кубика Рубика

1.1. Сложность построения графа состояний кубика Рубика

1.1.1. Ограниченные возможности графических редакторов и средств для визуализации графа состояний кубика Рубика

1.2. Ограниченность ресурсов вычислительной техники

1.2.1. Ограниченностьвместимости цифровых носителей

Рисунок 1.1 -- Дерево проблем

1.3 Дерево целей

Основную цель данной работы, можно разбить на подцели и представить в виде дерева целей (см. рис. 1.2).

1. Исследовать возможность создания алгоритмов и сформулировать рекомендации, позволяющие оптимизировать количество преобразований между начальным и целевым состояниями кубика Рубика

1.1. Оптимизация на группе преобразований состояний кубика Рубика

1.1.1. Применение методов теории групп

1.2. Поиск алгоритма для нахождения оптимального решения

1.2.1. Изучение и анализ алгоритмов преобразования состояний кубика Рубика

Рисунок 1.2 -- Дерево целей

Цель работы - исследовать возможность создания алгоритмов и сформулировать рекомендации, позволяющие оптимизировать количество преобразований между начальным и целевым состояниями кубика Рубика.

Объект исследования - Состояния кубика Рубика.

Предмет исследования - Группы преобразований состояний кубика Рубика

Методы исследования:

· Обработка существующей информации;

· Анализ существующих алгоритмов.

Основные задачи исследования:

· Проведение морфологического, функционального, информационного и классификационного анализа объекта исследования;

· Изучение алгоритмов преобразования состояний кубика Рубика;

· Определение основных факторов, влияющих на оптимизацию групп преобразований кубика Рубика.

2. Описание системы трехмерного визуализатора процесса дефрагментации (кубика рубика) с точки зрения системного анализа

2.1 Структурное описание системы

Рассмотрим структуру системы кубика Рубика (Рисунок 2.1) и её свойства с позиций системного анализа.

Рисунок 2.1 - Структура кубика Рубика

Свойства системы:

1) Эмерджентность

Центральный механизм - предназначен для соединения 26 конгруэнтных кубиков управления вращениями граней

Кубики - определяют положение цветовых индикаторов на каждой грани

Каждая из систем выполняет свою функцию, но их объединение способствует визуализации пошагового процесса дефрагментации без нарушения целостности всего устройства.

2) Целостность

При удалении из системы всех центральных кубиков реберные и угловые кубики перестают управляться центральным механизмом, и система перестает существовать

3) Аддитивность

Переход системы в нулевое состояние осуществляется последовательными поворотами граней куба.

4) Синергизм

Вращение одной грани вызывает одновременное изменение положения и ориентации в пространстве девяти кубиков, принадлежащих вращающейся грани.

5) Прогрессирующая систематизация

Процесс сборки кубика Рубика - это стремление к целостному цветовому покрытию каждой грани

6) Изоморфизм

Все центральные, реберные и угловые кубики сходны между собой по строению (внутри группы).

Тип элементного состава - смешанный тип. Однотипными элементами являются кубики и в то же время они отличаются от центрального механизма.

Тип элементов - вещественный.

Тип связей между элементами - информационный.

Тип структуры - иерархическая.

Условно кубик Рубика можно представить кибернетической моделью, где {x1, …, xn} - вектор входов объекта, а {y} - выход.

2.2 Функциональное описание системы

Функциональное описание системы - это описание как основной функции, выполняемой системой, так и функций подсистем и элементов данной системы с указанием параметров системы, подсистем и элементов. Функциональное описание также содержит структурноеописание системы, описание системоразрушающих и системообразующих факторов.

Структурное описание системы:

1. Кубик Рубика

1.1. Центральный механизм

1.1.1. Толстое плечо креста

1.1.2. Тонкая ось креста

1.1.2.1. Шайба

1.1.2.2. Пружина

1.1.2.3. Гайка

1.2. Кубики

1.2.1. Центральные

1.2.1.1. Цветные накладки

1.2.2. Реберные

1.2.2.1. Цветные накладки

1.2.3. Угловые

1.2.3.1. Цветные накладки

Функции системы и ее подсистем представлены в таблице 2.1

Таблица 2.1 - Функциональное описание системы

Параметры системы и ее подсистем представлены в таблице 2.2

Таблица 2.2 - Параметры подсистем и элементов

Итоговое и суммарное количество функций

· Функции первого уровня - 1

· Функции второго уровня - 2

· Функции третьего уровня - 5

· Функции четвертого уровня - 4

Общие характеристики системы представлены в таблице 2.3

Таблица 2.3 - Общие характеристики системы

2.3 Информационное описание системы

Информационное описание должно давать представление об организации и управлении системой. Это наиболее полное описание, так как описывает систему уже в процессе ее функционирования. Информационное описание определяет зависимость морфологических и функциональных свойств системы от качества и количества внутренней (о самом себе и о среде) и внешней (поступающей из внешней среды) информации.

Принцип работы объекта исследования

На рисунках 2.2, 2.4 и 2.5 изображены внутренний крест, реберный кубик и угловой кубик соответственно. На рисунке 2.3 изображено крепление центрального кубика на внутреннем кресте

Рисунок 2.6 изображает внутреннюю сторону грани, снятой с креста.

Рисунок 2.7 изображает кубик Рубика, с которого снята одна грань и один реберный кубик.

Для большей наглядности на рисунках 2.6 и 2.7 центральные кубики, реберные кубики, угловые кубики и внутренний крест окрашены в разные цвета. Эта окраска не имеет отношения к цветным накладкам на внешних гранях кубиков.

На рисунках 2.6 и 2.7 видно как выступы на реберных и угловых кубиках складываются в почти цилиндрический выступ с внутренней стороны грани большого куба, а на среднем слое образуется цилиндрическое кольцеобразное углубление. Поворот грани отвечает повороту цилиндрического выступа в цилиндрическом углублении.

Роль пружины 4 (Рисунок 2.2) - в том, чтобы иметь возможность слегка оттягивать при поворотах вращающуюся грань.

Рисунок 2.2

Перечень элементов системы:

1) толстое плечо креста - 1;

2) тонкая ось креста - 6;

3) шайба - 6;

4) пружина - 6;

5) гайка - 6;

6) центральные кубики - 6;

7) реберные кубики - 12;

8) угловые кубики - 8;

9) цветные накладки -54 (9шт х 6цветов).

Свойства деталей элементов представлены в таблице 2.4

Таблица 2.4 - Свойства деталей элементов системы

Среднегеометрическое число свойств на один элемент:

Структура объекта представлена на рисунке 2.3

Рисунок 2.3 - Граф системы

Связи системы между элементами системы:

1) Соединительные

3. Угловые кубики - центральный кубик

4. Реберные кубики - центральный кубик

5. Центральный кубик - шайба

6. Угловой кубик - цветные накладки

7. Реберный кубик - цветные накладки

8. Центральный кубик - цветная накладка

10. Пружина - гайка

11. Гайка - тонкая ось креста

12. Тонкая ось креста - толстое плечо креста

2) Преобразующие

1. Внешняя среда (пользователь) - угловые кубики

2. Внешняя среда (пользователь) - реберные кубики

9. Шайба - пружина

Количество связей на один элемент системы представлено в таблице 2.5

Таблица 2.5 - Количество связей на один элемент

Среднегеометрическое число связей на один элемент:

Определяем число квантов пространства, занимаемых элементами (Таблица 2.6).

Квант пространства элемента vi- объем прямоугольного параллелепипеда, ограничивающего заданный элемент.

Объем пространства существования элементов V - это объем куба с ребром, равным сумме максимальных габаритов размеров элементов.

Число квантов: =

Таблица 2.6 - Число квантов пространства, занимаемых элементами

Среднегеометрическое число квантов пространства:

2.4 Классификационное описание системы

Классификация - это разделение совокупности объектов на

классы по наиболее существенным признакам.

Результаты классификации системы представлены в таблице 2.7.

Таблица 2.7 - классификация системы по классификационным признакам

3. Модельное представление объекта исследования

3.1 Основные уравнения, описывающие объект исследования

Для обозначения последовательности поворотов граней кубика Рубика 3Ч3Ч3 используется «нотация Сингмастера» , разработанная Дэвидом Сингмастером и опубликованная им в 1981 г.

Буквы L, R, F, B, U, D обозначают поворот на 90° по часовой стрелке левой (left), правой (right), передней (front), задней (back), верхней (up) и нижней (down) граней соответственно. Повороты на 180° обозначаются добавлением справа к букве цифры 2 или добавлением в верхнем индексе цифры 2 справа от буквы. Поворот на 90° против часовой стрелки обозначается добавлением штриха (?) или добавлением в верхнем индексе -1 справа от буквы. Так, например, записи L2 и L2; L? и L-1 эквивалентны.

Существует два наиболее распространённых способа измерения длины решения (метрики). Первый способ -- одним шагом (ходом) решения считается поворот грани на 90° (quarterturnmetric, QTM). По второму способу -- за 1 ход также считается и полуоборот грани (faceturnmetric, FTM, иногда это обозначают HTM -- half-turnmetric). Так, F2 (поворот передней грани на 180°) должен считаться за два хода в метрике QTM или за 1 ход в метрике FTM.

Для указания в тексте длины последовательности для используемой метрики используется нотация, состоящая из цифр числа ходов и строчной первой буквы обозначения метрики. Так, 14f обозначает «14 ходов в метрике FTM», а 10q -- «10 ходов в метрике QTM». Чтобы указать, что количество ходов является минимальным в данной метрике, используется звёздочка: 10f* обозначает оптимальность решения в 10 ходов FTM.

3.2 Входные и выходные величины

Входными величинами являются всевозможные состояния кубика Рубика. Единственной выходной величиной является нулевое (собранное) состояние.

3.3 Исследование преобразований состояний кубика Рубика с помощью математической теории групп

Состояния - различные варианты сборки кубика Рубика, возникающие при произвольной расстановке 8 угловых кубиков по вершинам куба и 12 реберных - по ребрам. Центральные кубики во всех состояниях расположены одинаково - так же, как в нулевом состоянии, когда каждая грань куба окрашена в один цвет. Если состояние S2 можно получить из состояния S1 с помощью некоторой операции, то и от S2 можно перейти к S1, изменив направление каждого из поворотов на противоположное и выполняя их в обратном порядке. В этом случае состояния S1 и S2 являются связанными.

Чтобы полностью описать состояние кубика Рубика, нужно для каждого маленького кубика указать место, которое он занимает, и его ориентацию на этом месте. Каждый угловой кубик можно поместить в одно и то же место тремя, а реберный - двумя способами.

Пусть кубик Рубика находится в нулевом состоянии. Перенумеруем его вершины и находящиеся в них угловые кубики числами от 1 до 8, а ребра и соответствующие реберные кубики - числами от 1 до 12. Кроме того на каждом ребре большого куба выберем определенное направление (вектор).

Теперь местонахождение i-го углового (j-го среднего) кубика в состоянии S можно задать номером уS(i) (фS(j)) той вершины (ребра), где он находится (i = 1..8, j = 1..12).

Чтобы задать ориентацию угловых кубиков, выделим пару противоположных граней большого куба, например его горизонтальные грани. Для определенности предположим, что верхний кубик - синий, а нижний - зеленый. Каждый угловой кубик имеет либо одну грань синего цвета, либо одну грань зеленого цвета. Угол б (б = 00, 1200 или 2400), на который следовало бы повернуть этот кубик в его положении вокруг диагонали большого куба против часовой стрелки, чтобы эта грань (синяя или зеленая) стала горизонтальной, будем называть углом поворота данного углового кубика в состоянии S и об означать бS(i), где i - номер кубика.

Ориентацию j-го реберного кубика в состоянии S зададим углом вS(i) между вектором ребра, на котором кубик должен находиться, и вектором ребра, на котором он находится (фS(j)-го ребра). Угол вS(i) может равняться 00 или 1800; будем называть его углом поворота j-го реберного кубика в состоянии S.

Проследим, как изменяются характеристики состояний бS, вS, фS и уS при поворотах граней. Легко проверить что:

1) Углы поворотов угловых кубиков не изменяются при поворотах четырех вертикальных граней на 1800 и при произвольных поворотах горизонтальных граней.

2) Углы поворотов реберных кубиков не изменяются при поворотах двух противоположных граней на 1800 и при произвольных поворотах остальных граней.

3) При повороте любой вертикальной грани на ±900 к углам поворотов бs двух кубиков, стоящих в ее противоположных вершинах, добавляется по 1200, а к углам поворотов двух ее других угловых кубиков добавляется по 2400.

4) При повороте правой или левой грани на ±900 меняются углы поворотов всех четырех реберных кубиков этой грани.

Отсюда немедленно вытекает, что суммы углов поворотов всех угловых и всех реберных кубиков

A(S) = бS(1) + бS(2) + … + бS

B(S) = вS(1) + вS(2) + … + вS

остаются постоянными при всех поворотах граней. Такие характеристики состояний называются инвариантами. Значения любого инварианта для двух связанных состояний S1 и S2 совпадают. Поэтому равенства A(S1) = A(S2) и B(S1) = B(S2) являются необходимыми условиями связанности состояний. Присоединив к ним аналогичное равенство для еще одного инварианта, получаются достаточные условия.

Перестановкой конечного множества называется любое отображение этого множества на себя. Таким образом, функция уs заданная на множестве {1, …, 8}, является перестановкой этого множества, а фS - перестановка множества {1, … , 12}. С любой операцией F также связаны две перестановки фF и уFэтих же множеств: если нулевое состояние S0 переводится операцией F в состояние S, то, по определению, уS(i) = уF(i), фF(j) = фS(j). Другими словами, уF(i) и фF(j) - это номера тех мест, которые занимают в результате операции F угловой кубик, стоявший на i-м месте, и реберный кубик, стоявший на j-м месте.

Выполнив одну за другой перестановки у1 и у2 одного и того же множества, мы снова получим его отображение на себя - перестановку у. Она называется композицией перестановок у1 и у2: у = у1 _ у2.

Пусть у - произвольная перестановка множества {1, 2, … , n}. Нарисуем одну под другой две строчки по n точек. Если при перестановке у число i переходит в j, соединим i-ю точку верхней строки отрезком с j-й точкой нижней строки - мы получим граф перестановки у. Обозначим через N(у) число точек пересечения отрезков графа (точку, в которой пересекается больше двух отрезков, сосчитаем столько раз, сколько пар отрезков ее содержит). Перестановка у называется четной (нечетной), если число N(у) четно (нечетно). Знак перестановки у определим равенством е(у) = (-1) N(у). е(у) равно 1 или -1 в зависимости от того, четна или нечетна перестановка. Выясним, как зависит четность композиции у1 _ у2 от четностей у1 и у2. Граф композиции строится очень просто: совмещаем нижнюю строку графа перестановки у1 с верхней строкой графа у2 - получается промежуточный граф, а затем заменяем каждую ломаную в промежуточном графе на отрезок, соединяющий ее концы. Число точек пересечения ломаных в промежуточном графе равно N(у1) + N(у2). При распрямлении число точек пересечения ломаных может уменьшиться, но его четность сохранится.

Таким образом, N(у1 _ у2) и N(у1) + N(у2) - числа одной четности; следовательно, е(у1 _ у2) = (-1) N(у1 _ у2) = (-1) N(у1) + N(у2)= (-1) N(у1) Ч 1N(у2) = е(у1) _ е(у2). Другими словами, композиция двух перестановок четна, если их четности совпадают, и нечетна в противном случае.

Допустим, что перестановка у множества из n элементов оставляет неподвижными n - mэлементов, а остальные m элементов можно упорядочить так, что первый из них переходит во второй, второй - в третий, i-й - в (i+1)-й, а m-й элемент - опять в первый. Тогда перестановка называется циклом длины m или m-циклом.

Назовем знаком состояния S число е(S) = е(уS) _ е(фS). Оно равно 1 или -1 в зависимости от того, совпадают или нет четности перестановок уSи фS.

Рассмотрим поворот F любой грани на 900. Пусть в результате этого поворота кубик Рубика перешел из состояния S в состояние S". Тогда уS" = уS _ уF, фS" = фS _ фF. Перестановки уFи фF - это 4-циклы, поэтому они нечетны и е(уF) = е(фF) = -1. Следовательно, е(уS") = е(уS)Ч е(уF) = -е(уS), е(фS") = е(фS)Ч е(фF) = -е(фS)и е(S") = е(S). Знак состояния не меняется при поворотах граней. Это и есть третий инвариант.

Система инвариантов A(S), B(S) и е(S) - полная, то есть совпадение их значений для двух состояний обеспечивает связанность этих состояний.

3.4 Анализ некоторых алгоритмов решения головоломки

Первые разработанные алгоритмы требовали 200-300 ходов (поворотов граней) для того, чтобы вернуть кубик в нулевое состояние.

Постепенно длина алгоритмов (т.е. минимальное число ходов, гарантирующее решение) сокращалась. Это происходило за счет изменения последовательности сборки разных частей головоломки (улучшения стратегии) и применения более коротких операций для перестановки и правильной ориентации кубиков (улучшения тактики). Ставший самым популярным «послойный» алгоритм кубика Рубика осуществляет сборку не более чем за 108 ходов. Совершенствуя его, удается уменьшить это число до 86 ходов. Дальнейшие улучшения требуют резкого увеличения количества формул, которые необходимо держать в голове или на бумаге в процессе сборки.

Одновременно с любителями решать головоломку, держа ее в руках, неприступный кубик штурмовали и программисты. Сначала успеха добились те из них, кто взялся за малый кубик размером 2Ч2Ч2. Задачу они решали с конца: исходя из нулевого состояния кубика, программа начинает разрушать его, получая и запоминая результаты всевозможных поворотов граней. Если какая-либо расцветка кубика появляется повторно, то соответствующая операция игнорируется, так что в памяти компьютера остаются только самые короткие формулы. В результате был получен список всевозможных состояний малого кубика с указанием после каких поворотов граней они впервые появились. Этот список никогда не был ни опубликован, ни напечатан хотя бы в одном экземпляре. Причина не столько в его громадных размерах, сколько в том, что из-за таких размеров слишком трудно найти в списке нужную в данный момент операцию.

Поворачивая грани 12 раз, компьютер не нашел ни одного нового состояния Малого кубика. Следовательно, чтобы решить головоломку из 8 кубиков, всегда достаточно сделать не более 11 ходов.

Малый кубик есть не что иное, как 8 угловых кубиков классического кубика Рубика. Но в последнем - 26 кубиков, а это усложняет задачу перебора. Кубик Рубика может иметь N 4,3Ч1019 различных состояний.

Из программистов, занимавшихся разработкой алгоритма для классического кубика Рубика, первым добился успеха английский математик Морвин Тистлетуэйт, который в июле 1981г. разработал алгоритм, позволявший всегда упорядочить кубик Рубика не более чем за 52 хода. Хотя в принципе с помощью этого алгоритма можно собрать кубик Рубика и вручную, реально его может выполнить только компьютер. В дальнейшем этот алгоритм удалось несколько улучшить - сначала этого добился сам англичанин, а позже, в декабре 1990г. Ханс Клостерман из Голландии довел длину алгоритма до 42 ходов. Важно отметить, что эта граница обоснована строго, а не эмпирически, т.е. доказано, что из любого состояния кубика Рубика можно вернуться в нулевое не более чем за 42 хода, причем данный алгоритм не может гарантировать лучшего результата. Это означает, что другой алгоритм не может оказаться короче. Конечно, это доказательство существенно использует компьютер: для каждого из этапов сборки был осуществлен полный перебор вариантов, число ходов, понадобившееся в худшем случае, и принимается за длину данного этапа.

Нового достижения в 1992г. добился немецкий математик Герберт Коцемба. Он был среди тех, кто занимался малым кубиком, но затем примкнул к программистам, исследующим классический кубик Рубика. Он разработал алгоритм и написал программу, которая позволяет собрать головоломку не более чем за 21 ход. Эта оценка длины, в отличие от предыдущей, эмпирическая: все состояния кубика Рубика, которые предлагались программе Коцембы, были упорядочены не более чем за 21 ход.

В июле 2010 года программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 20 ходов. При этом любой поворот грани считался одним ходом. Таким образом, число Бога в метрике FTM оказалось равно 20 ходам. Объём вычислений составил около 35 лет процессорного времени, пожертвованного компанией Google. Технические данные о производительности и количестве компьютеров не разглашаются; продолжительность вычислений составляла несколько недель.

В августе 2014 г. Томас Рокики и Морли Дэвидсон объявили, что в метрике QTM число Бога равно 26q.

3.4.1 Алгоритм Тистлетуэйта

Тистлетуэйт использовал ряд подгрупп длины 4

· G0 = (L, R, F, B, U, D)

Эта группа совпадает с группой кубика Рубика. Её порядок равен

· G1 = (L2, R2, F, B, U, D)

Эта подгруппа включает в себя все состояния, которые могут быть решены без использования поворотов левой или правой граней на ±90°. Её порядок равен

· G2 = (L2, R2, F2, B2, U, D)

Эта подгруппа включает в себя все состояния, которые могут быть решены при условии, что повороты четырёх вертикальных граней на ±90° запрещены. Её порядок равен

· G3 = (L2, R2, F2, B2, U2, D2)

Эта подгруппа включает в себя все состояния, которые могут быть решены с использованием только поворотов на 180°. Её порядок равен

Эта подгруппа включает в себя единственное нулевое состояние.

На первом этапе произвольно заданное состояние из группы G приводится к состоянию, лежащему в подгруппе G1. Цель второго этапа состоит в том, чтобы привести кубик к состоянию, находящемуся в подгруппе G2, не используя поворотов левой и правой граней на ±90°. На третьем этапе кубик Рубика приводится к конфигурации, принадлежащей группе G3, при этом повороты вертикальных граней на ±90° запрещены. На заключительном, четвёртом этапе, кубик Рубика полностью собирается поворотами граней на 180°.

Упомянутые группы промежуточных состояний определяются путем вычисления определенных характеристик этих состояний. Эти характеристики, сохраняющиеся при любых разрешенных действиях, математики называют инвариантами. Каждая подгруппа соответствует своему набору инвариантов и их значений.

Тистлетуэйт, проделав весьма кропотливую работу по перебору алгоритмов, показал, что для первого этапа всегда достаточно 7 ходов, для второго - 13, для третьего - 15, а для четвертого - 17. Итого весь алгоритм требует не более чем 52 хода. Этот результат был намного лучше, чем могли в то время дать все остальные алгоритмы сборки кубика. У него был один-единственный "недостаток": он никак не помогал собрать кубик вручную.

3.4.2 Алгоритм Коцембы

Алгоритм Тистлетуэйта был в 1992 году улучшен учителем математики из Дармштадта Гербертом Коцембой.

Коцемба сократил количество этапов алгоритма до двух

· G0 = (U, D, L, R, F, B)

· G1 = (U, D, L2, R2, F2, B2)

Наглядное описание группы G1 можно получить, если произвести следующую разметку (рисунок 3.1):

· Все этикетки U и D пометить знаком «+».

· Все этикетки на рёберных элементах FR, FL, BL и BR пометить знаком «-»

· Все остальные этикетки оставить без меток.

Тогда все конфигурации группы будут иметь одну и ту же разметку (совпадающую с разметкой на собранном кубике).

Рисунок 3.1 - Промежуточное состояние кубика Рубика в алгоритме Коцембы. Группа G1

Алгоритм Коцембы еще в меньшей степени, чем алгоритм Тистлетуэйта, можно назвать "алгоритмом сборки" в привычном смысле этого слова. Реализовать этот алгоритм способен только достаточно быстрый компьютер с большой оперативной памятью. Однако сама идея довольно проста.

Вся сборка кубика разбивается на 2 этапа. На первом этапе допускаются любые повороты граней. Единственной целью первого этапа является приведение кубика в некоторое "промежуточное" состояние. Как только кубик после некоторого числа поворотов оказался в промежуточном состоянии, начинается второй этап. В этом этапе используются уже не все возможные повороты граней, а только такие, которые не выводят кубик из класса промежуточных состояний. Нулевое состояние (полностью собранный кубик) также принадлежит этому классу, поэтому рано или поздно оно будет найдено обыкновенным перебором вариантов.

Если суммарное число ходов, затраченных на первый и второй этап, больше 21, то программа возвращается к первому этапу и берет следующее промежуточное состояние. Экономия перебора, получаемая благодаря этой идее, колоссальна: на первом этапе рассматривается примерно вариантов, а на втором - вариантов. Итого программа должна просмотреть около вариантов, а это число на 9 порядков меньше, чем общее количество состояний куба.

У алгоритмов Коцембы и Тистлетуэйта есть много общего. Например, оба они используют такое понятие, как класс промежуточных состояний. При этом "промежуточные состояния Коцембы" практически совпадают со "вторым классом промежуточных состояний" Тистлетуэйта. Разница только в системе обозначений - на втором этапе Коцемба разрешает произвольные вращения U и D, и повороты на 180 остальных граней, а Тистлетуэйт на своем третьем этапе оставлял для произвольных вращений грани F и B. Иначе говоря, первый этап способа Коцембы соответствует двум первым этапам алгоритма Тистлетуэйта, а второй этап - двум последним. Различия между этими алгоритмами не столь заметны, но более принципиальны. А именно, Тистлетуэйт получил конкретные наборы операций и привел строгие математические доказательства, обосновывающие указанные им длины каждого этапа. А Герберт Коцемба, не утруждая себя никакими обоснованиями, просто бросил вызов всем любителям: можете присылать мне все те задачки, которые у вас не получаются, и моя программа справится с ними за 20 ходов!

Реально программа Коцембы немного сложнее, чем это описано выше. Она не делает полного перебора вариантов ни на одном из своих этапов. Вместо этого она тратит некоторое время на создание специальных фильтров: огромных массивов, содержащих списки состояний, из которых можно достичь конечного (для этого этапа) состояния за определенное число ходов (от 1 до 8). Начав сборку кубика, программа пытается выполнить первый этап за 10 ходов. Она делает первые два хода и смотрит массив-фильтр на 8 ходов. Если состояние не отсеется, то делается третий ход и просматривается фильтр на 7 ходов и т.д. В противном случае делается другой второй ход. Точно по такой же схеме выполняется и второй этап сборки - на него программа Коцембы отводит не более 14 ходов.

Сообщение Коцембы неоднократно перепроверялось и уточнялось другими специалистами. В результате оказалось, что для обоих этапов оценки, количества ходов, приведенные Коцембой, чересчур оптимистичны: существуют начальные позиции, из которых нельзя закончить первый этап быстрее чем за 12 ходов, кроме того, существуют состояния из "промежуточного" класса, от которых нельзя перейти к собранному кубику быстрее чем за 18 ходов. Приведенные числа 12 и 18 - это точные границы: последователям Коцембы удалось произвести полный перебор для 1-го и 2-го этапов. Таким образом, доказано, что алгоритм Бога имеет длину не более 30 ходов.

3.4.3 Метод CFOP (метод Джессики Фридрих)

CFOP - это название четырёх стадий сборки(рисунок 3.2): Cross, F2L, OLL, PLL:

1) Cross - сборка креста, четырёх рёберных кубиков на нижней грани;

2) F2L (First two layers) - первые два слоя - нижний и средний;

3) OLL (Orient the last layer) - ориентацияпоследнегослоя;

4) PLL (Permute the last layer) - перестановка последнего слоя.

Рисунок 3.2 - Четыре стадии метода CFOP

Единственный этап для которого нет четкой методики.

Основная хитрость сборки креста в том, что его надо собирать относительно. К примеру, если собирается крест на белой грани и бело-синий рёберный кубик уже на ней стоит белым цветом к белому центру, то не так важно, совмещена ли синяя сторона этого кубика с синей гранью. Достаточно поставить бело-зелёный кубик на противоположной стороне, а бело-красный и бело-оранжевый слева и справа. В процессе сборки можно крутить белую грань как угодно, а в конце одним движением сразу совместить все боковые центры с кубиками креста. Важно лишь помнить точный порядок цветов на кубике: если смотреть на белую грань, то по часовой стрелке идут синий, красный, зелёный, оранжевый (сзади -- жёлтый).

Нужно расставить на места восемь кубиков: четыре угловых нижнего слоя и четыре рёберных боковых в среднем слое. Начинающих пара из углового и рёберного кубика собирается сразу же (то есть надо собрать четыре таких пары). В зависимости от первоначальной расстановки кубиков пары нужно применить тот или иной алгоритм (последовательность поворотов). Всего таких алгоритмов больше 40.

Основная сложность этапа в том, чтобы быстро находить парные кубики. Они могут находиться в 16 различных местах: 8 мест в последнем слое и 8 в столбиках. Столбики просматривать сложнее, а чем меньше столбиков собрано, тем больше шансов, что в несобранных находятся нужные кубики. Если вы при сборке креста не обращали внимания на кубики для F2L, при переходе к этому этапу вы можете потерять много времени просто на поиск.

На этом этапе кубики последнего слоя ориентируются так, чтобы последняя грань оказалась собранной. При этом неважно, что кубики не стоят на своих местах: для этого существует последний этап.

Существует 57 различных исходных ситуаций, для каждой из которых есть свой алгоритм сборки, от 6 до 14 ходов.

Заключительный этап сборки состоит в том, чтобы расставить кубики последнего слоя на нужные места. Подход примерно аналогичный предыдущему этапу, но комбинаций и алгоритмов здесь меньше, всего 21 (13, если считать зеркальные и обратные за одну). С другой стороны их несколько сложнее опознавать, так как здесь надо учитывать разные цвета, причём цвета на схеме могут не совпадать с фактическими цветами (с точностью до циклической перестановки):

3.4.4 Основные факторы, влияющие на оптимизацию групп преобразований состояний кубика Рубика

Деление пространства позиций

Количество состояний кубика Рубика было разбито на 2 217 093 120 групп, в каждую входило по 19,508,428,800 различных состояний. Одна такая подзадача легко помещается в память современного компьютера, и этот метод позволил достаточно быстро получить решение.

1. Симметрия

Если повертеть Кубик Рубика влево-вправо или вверх-вниз, то, по сути, ничего не изменится: число шагов в решении останется тем же самым. Вместо того, чтобы решать все эти состояния, можно получить решение для одного и распространить его на повернутые состояния. Есть 24 различных ориентации в пространстве и 2 зеркальных положения Кубика для каждого состояния, что позволяет уменьшить число решаемых состояний в 48 раз. Если использовать аналогичные рассуждения и воспользоваться поиском задачи “покрытия множества”, то число подзадач уменьшается от 2 217 093 120 до 55882296.

2. Хорошие и оптимальные решения

Оптимальное решение содержит достаточное количество шагов, но не более, чем необходимо. Так как уже известно одно состояние, для которого требуется 20 шагов, то можно не искать оптимальное решение для каждого состояния, а только решения в 20 или менее шагов. Это многократно ускоряет задачу.

3. Оборудование

Для решения 55 882 296 подзадач компания Google предоставила целый парк компьютеров и все вычисления заняли всего несколько недель. Google не раскрывает характеристики компьютеров, но было затрачено 1,1 миллиард секунд (35 лет) компьютерного времени на выполнение расчетов.

Заключение

В данной работе была рассмотрена группа преобразований состояний кубика Рубика.

Показана актуальность и практическая значимость работы.

Детально была рассмотрена структура системы. Проведена классификация системы, а также следующие описания:

· морфологическое, описывающее структуру системы, а также свойства каждого элементы системы;

· функциональное, в основе которого лежат составные части системы, их функции, входные и выходные данные;

· информационные, предоставляющее анализ свойств и связей каждого элемента системы.

Были изучены алгоритмы преобразования групп состояний кубика Рубика и определены основные факторы, влияющие на оптимизацию групп преобразований состояний кубика Рубика.

Список литературы

1. Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings The Cube: The Ultimate Guide to the World"s Bestselling Puzzle - Secrets, Stories, Solutions. - N. Y., 2009

2. М. Евграфов Механика волшебного кубика // Квант. -- 1982. -- № 3. -- С. 20-25

3. David Joyner Adventures in group theory: Rubik"s Cube, Merlin"s machine, and Other Mathematical Toys. -- Baltimore: Johns Hopkins University Press, 2002. -- С. 7.

4. В. Дубровский Алгоритм волшебного кубика // Квант. -- 1982. -- № 7. -- С. 22-25.

5. God"s Number is 20 [Электронныйресурс] // URL: cube20.org

6. К. Кноп Кубик Рубика: штурм твердыни [Электронный ресурс]// URL: http://geocities.com/CapeCanaveral/4344/192.html

Приложение А

Алгоритм CFOP (алгоритм Джессики Фридрих)

Язык вращений:

F - front - фронтальная сторона

B - back - задняя сторона

L - left - левая сторона

R - right - правая сторона

U - up - верхняя сторона

D - down - нижняя сторона

Fw - фронтальная вместе со средним слоем

Bw - задняя вместе со средним слоем

Lw - левая вместе со средним слоем

Rw - правая вместе со средним слоем

Uw - верхняя вместе со средним слоем

Dw - нижняя вместе со средним слоем

M - средний слой, находящийся между левым и правым слоями

S - средний слой, находящийся между фронтальным и задним слоями

E - средний слой, находящийся между верхним и нижним слоями

x - весь куб вращается от себя по плоскости, совпадающей с правым слоем. Это, по сути, то же самое, что повернуть правую грань кубика по часовой стрелке вместе со всем кубиком.

y - весь куб по часовой в горизонтальной плоскости (верхнюю грань кубика по часовой стрелке вместе со всем кубиком)

z - весь куб по часовой в фронтальной плоскости (фронтальную грань кубика по часовой стрелке вместе со всем кубиком)

Приложение Б

Применение Кубика Рубика для объяснений в теории групп

1. Множества и функции

Ш Множествоэто набор элементов,каждый из которых содержится в множестве более одного раза.(Конечное) множество может быть задано явно в виде списка внутри пары фигурных скобок, например{2,4,6,8}это множество четных натуральных чисел меньше 10. Оно состоит из четырех элементов.Есть бесконечные множества - множества, имеющие бесконечное число элементов - таких, как множество целых чисел, но, как правило, обсуждаются только конечные множества (и группы).

На головоломках, мы часто рассматриваем множество состояний головоломки.

Ш Функция F: АBотображающая множество А в множество В - это отношение, которое каждому элементу множества A сопоставляет некоторый элемент множества В.

Шаг на головоломки - это функция на множестве состояний. Шаг применяется к одному состоянию для перехода в другое.

Ш Функция F:А -> B называется инъективной, если она сопоставляет различным элементам множества А различные элементы множества B.

Функция F:А -> B называется сюръективной, если каждый элемент множества B она сопоставляет с элементом множества А.

Функция F:А -> B называется биективной, если она является как инъективной, так и сюрьективной.

Функция f называется обратной к F (как правило обозначается F-1), если F:А -> B имеет обратную F-1:В -> А, такую, что всякий раз, когда аF = b, то bF-1 = а

Вращения кубика Рубика всегда обратимы. Например, шаг R, поворот по часовой стрелке правой грани, может быть отменен путем поворота правой грани против часовой стрелки. Обозначается какR-1, хотя R" является более распространенной.

Ш Композицией двух функций F:А -> B и G:B -> С, называется функция, которая является результатом применения сначала F, а затем G. Таким образом, отображение элемента множества А в элемент множества С определяется по формуле = (аF)G. Эта функция обозначается F ? G.

Вращения могут быть объединены в последовательности вращений.

Любая последовательность шагов - это композиция. Например, если мы применяем последовательность вращений FRBк состоянию S, мы можем сделать ходы по одному, которые дают формулу ((SF)R)B, или в качестве одной функции F о R о В, что дает S (F о R о В).

Ш Функция тождества IA:A ->A. Определяется аI = а для любого элемента а из множества А. Легко увидеть, функция тождества биективна.

Тождество на кубе - это последовательность перемещений, которые в итоге не меняют состояние, например, F2 B2 L2 R2 F2 B2 L2 R2.

2. Группы и гомоморфизмы

Ш Группа замкнута относительно умножения, то есть, если перемножить любые два элемента группы, то результатом будет элемент этой же группы.

Можно объединить две последовательности ходов, чтобы получить третью.

Ш Существует единичный элемент, т.е. элемент е в группе такой, что для любого элемента g в группе у нас есть ge = eg = g.

Единичным элементом группы кубика Рубика является отсутствие вращения.

Ш Каждый элемент имеет обратный, то есть, если G есть элемент группы, то есть элемент H в группе такой, что GH = HG = е. Обратный элемент G обозначается G-1.

Обратным элементом группы кубика Рубика является инверсия вращения, т.е. вращение в обратную сторону на тот же угол поворота.

Ш Умножение ассоциативно, то есть, если, В и С являются элементами группы, то (АВ) С = А (ВС).

Ассоциативность группы кубика Рубика очевидна

Ш Группа конечна, если она имеет конечное число элементов. Число элементов в группе G называется порядком группы, и обозначается | G |.

Число состояний куба конечно, и, следовательно, число функций на этом множестве состояний также конечно. Группа кубика Рубика, следовательно, также конечна.

Существует еще одна группа - группа вращений куба в целом. Мы можем сделать верхней любую из шести граней, а затем есть четыре варианта, какая из смежных граней должны стать фронтальной. Следовательно, есть 24 возможные ориентации куба. Вращение всего куба это изменение между двумя такими ориентациями.

Ш Порядок элемента g в группе это наименьшее натуральное число N, для которого gN = е (если такое N существует), где показатель обозначение gN имеет естественный смысл повторного умножения. Если такого числа не существует, то g, как говорят, бесконечный порядок. Порядок g обычно обозначается O (G).

В конечной группе все элементы имеют конечный порядок

Группа куба конечна. Если делать какие-либо последовательные вращения, а также постоянно повторять их, то в конечном итоге получится начальное состояние.

Ш Гомоморфизм - это отображение F: G -> H ставящее в соответствие всякому элементу g из группы G однозначно определенный элемент h из группы H, если всякий элемент g из группы G служит при этом отображении образом некоторого элемента h из группы H, и если для любых элементов g1, g2 группы G выполняется равенство (g1 · g2) F = (g1) F · (g2) F. Если гомоморфизм взаимно однозначен, то он называется изоморфизмом.

Существует гомоморфизм из обычного кубика Рубика 3 Ч 3 Ч 3 на Малый кубик 2 Ч 2 Ч 2. Любой шаг последовательности на кубике Рубика также может быть выполнен на Малом кубике. Таким образом, любая перестановка на обычном кубике привязывается к некоторой перестановке на маленьком кубике. Это отображение не является изоморфизмом, так как маленький кубик имеет группу, которая является упрощенной версией группы большего кубика.

Размещено на Allbest.ru

Подобные документы

Особенности факторизации четырехмерных симплектических групп. Исследование и анализ композиции геометрических преобразований. Характеристика изометрии, закономерных пространств. Методы решения структурных теорем – центры, коммутанты, теоремы о простоте.

дипломная работа , добавлен 14.02.2010


Изучение строения групп по заданным свойствам системы их подгрупп как направлениt в теории конечных групп. Обзор конечных групп с плотной системой F-субнормальных подгрупп в случаях, когда F - произвольная S-замкнутая формация p-нильпотентных групп.

курсовая работа , добавлен 07.03.2010


Группа, как совокупность преобразований, замкнутая относительно их композиции. Изучение нильпотентных групп, их простейших свойств и признаков. Особенности доказывания теорем Силова, Лагранжа, Виланда. Подгруппа Фраттини конечной группы нильпотентна.

курсовая работа , добавлен 10.04.2011


Возникновение и развитие теории групп. Проблема интегрирования дифференциальных уравнений. Алгебраические конструкции в теории автоматов. Появление понятия перестановок. Группы и классификация голограмм. Применение теории групп в квантовой механике.

реферат , добавлен 08.02.2013


Решение системы линейных уравнений методами Крамера, Гаусса (посредством преобразований, не изменяющих множество решений системы), матричным (нахождением обратной матрицы). Вероятность оценки события. Определение предельных вероятностей состояний системы.

контрольная работа , добавлен 26.02.2012


Строение конечных групп по заданным свойствам их обобщенно субнормальных подгрупп. Использование методов абстрактной теории групп и теории формаций конечных групп. Субнормальные и обобщенно субнормальные подгруппы и их свойства. Обобщение теоремы Хоукса.

дипломная работа , добавлен 20.12.2009


Систему дифференциальных уравнений Колмогорова. Решение системы алгебраических уравнений для финальных вероятностей состояний. Графики зависимостей. Тип системы массового обслуживания по характеру входящего потока и распределению времени обслуживания.

контрольная работа , добавлен 01.03.2016


От анализа Фурье к вейвлет-анализу. Некоторые примеры функций вейвлет-анализа в MATLAB. Построение систем полуортогональных сплайновых вейвлет. Применение вейвлет-преобразований для решения интегральных уравнений. Вейвлеты пакета wavelet toolbox.

дипломная работа , добавлен 12.04.2014


Сущность теории групп. Роль этого понятия в математике. Мультипликативная форма записи операций, примеры групп. Формулировка сущности подгруппы. Гомоморфизмы групп. Полная и специальная линейная группы матриц. Классические группы малых размерностей.

курсовая работа , добавлен 06.03.2014


Описание ненильпотентных групп с перестановочными обобщенно максимальными подгруппами. Изучение групп с Х-перестановочными I-максимальными подгруппами. Особенности групп, в которых 2-максимальные подгруппы перестановочны с 3-максимальными подгруппами.

Как известно, количество возможных состояний кубика Рубика равно
43 252 003 274 489 856 000 (43 квинтиллиона 252 квадриллиона 3 триллиона 274 миллиарда 485 миллионов 856 тысяч). Откуда же берётся такая цифра? А вот откуда:
(количество расстановок реберных кубиков) х
х(количество расстановок угловых кубиков) х
х (количество комбинаций поворотов реберных кубиков) х
х (количество комбинаций поворотов угловых кубиков).

Есть ещё центральные кубики, но они всегда находятся на своих местах, а их ориентацией (для кубика с монотонной раскраской каждой грани) можно пренебречь.

Реберных кубиков в кубике Рубика 12. Значит, первый кубик можно расставить по 12 местам, второй кубик – на 11 мет, 3 кубик - на 10 мест четвертый - на 9 и так далее до последнего. То есть, количество ВСЕХ расстановок реберных кубиков равно
12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 479001600.
Записывается это как 12! (12-факториал).

Факториал числа n (лат. factorialis - действующий, производящий, умножающий; обозначается n!, произносится эн факториал) - произведение всех натуральных чисел от 1 до n включительно.

Аналогичным образом посчитаем количество ВСЕХ расстановок угловых кубиков. Их 8, а значит,
8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320.

Теперь посчитаем количество ВСЕХ комбинаций поворотов реберных кубиков. Каждый из 12 реберных кубиков может иметь только 2 ориентации - 0 и 180 градусов, поэтому, 2 в 12 степени = 4096.

Точно так же посчитаем количество всех ориентаций угловых кубиков: 3 в 8 степени = 6561.

Казалось бы, можно перемножить полученные 4 числа, и всё готово. Но не всё так просто. Пока что цифра получится горааааздо больше. Отсечём лишнее.

Если кубики выведены из правильного положения только допустимыми вращениями (а не физической разборкой и новой сборкой всего устройства или перекраской граней), то не может возникнуть положение, при котором:

1. все средние кубики стоят на своих местах и только один из них повернут неправильно;
2. все средние кубики и стоят, и повернуты правильно, а все угловые кубики, кроме двух, стоят (в любых положениях) на своих местах;
3. все средние кубики и стоят, и повернуты правильно, а все угловые кубики стоят на своих местах и только один из них повернут неправильно.

Кому интересно, откуда выведены такие свойства, рекомендую к прочтению статью «Математика волшебного кубика» В. Дубровского в журнале «Квант» №8 за 1982 год, и статью «Венгерский шарнирный кубик» в №12 за 1980 год в том же журнале, авторы - В. Залгаллер и С. Залгаллер. . Если Вы ни разу не математик, читать не советую, ибо вынесете себе мозг. А по сему, просто поверьте на слово.

В соответствии с первым свойством не может быть развёрнут только один реберный кубик, значит, его ориентацию мы тоже не будем учитывать. Поэтому 2 в 12 степени поделим на 2, что равно 2 в 11 степени. Получим 2048.

Исходя из третьего свойства, по которому не может быть повернут неправильно только один угловой кубик (а значит, можно не учитывать его ориентацию), подкорректируем подсчёт всех ориентаций угловых кубиков до минимально необходимого. То есть, поделим на 3, или запишем 3 в 7 степени, что равнозначно. Получится 2187.

Ну и последняя корректировка основана на втором свойстве. Она отсекает невозможные перестановки. То есть, если мы уже расставили на свои места (в любой ориентации) 6 из 8 угловых кубиков, то последние 2 обязательно встанут каждый на своё место. Помните, как мы считали расстановку углов? (От 8 возможных мест для первого кубика до одного места для последнего кубика.) Так вот, множители для последних кубиков можно теперь не учитывать. Поделим 8! на 2, получим 20160.

Итак, теперь Вы понимаете, что и откуда взялось в этой формуле, а значит можно смело перемножать полученные числа:
12! * 8!/2 * 2 11 * 3 7 = 12! * 8! * 2 10 * 3 7 .
Можно ещё разложить 12! и 8! на простые числа, тогда получим
2 27 * 3 14 * 5 3 * 7 2 * 11 = 43252003274489856000.
Или просто перемножить заранее вычисленные 4 числа:
479001600 * 20160 * 2048 * 2187 = 43252003274489856000.

Давайте теперь посчитаем, сколько будет возможных состояний у кубика Рубика, если учесть повороты центральных кубиков (серединок). Как известно, их 6 штук (в кубике размерностью 3х3х3) и каждый из них может быть повернут на 0, 90, 180 и 270(или минус 90) градусов, то есть иметь 4 возможных положения. Следовательно, количество возможных комбинаций центров равно 4 в 6 степени. Но в кубике невозможно состояние, когда при полностью собранном кубе только один центральный кубик повёрнут на 90 градусов (в любую сторону), поэтому, у последнего центрального кубика из шести учтём только два положения – 0 и 180 градусов. Получим
(4 6)/2=(2 2) 6 /2=2 12 /2=2 11 = 2048 возможных комбинаций.

Умножив теперь это число на известное нам количество комбинаций углов и ребер, получим:
2048 * 43252003274489856000 = 88580102706155225088000.

Итак, количество комбинаций кубика Рубика размерностью 3х3х3 с учетом ориентации центральных кубиков равно
2 11 * 2 27 * 3 14 * 5 3 * 7 2 * 11 = 2 38 * 3 14 * 5 3 * 7 2 * 11=
=88 580 102 706 155 225 088 000 (88 секстиллионов 580 квинтиллионов 102 квадриллиона 706 триллионов 155 миллиардов 255 миллионов 88 тысяч).

В последнее время появилось много кубиков с рисунками (или рисунком) на гранях. Если Вы приобрели себе один из них, то у Вас обязательно возникнет ситуация, когда центральные кубики будут неправильно сориентированы. Для того, чтобы собрать такой кубик, Вам необходимо знать, (на своих местах, естественно).

Как играть на кубике Рубика, играть не с ним, а на нем, как, например, на фортепиано? В этом вопросе, кажется, нет никакого смысла, но абстрактная область математики, которая называется теория групп, все-таки может дать на него ответ, если дадите мне минутку.

В математике группа – это определенный набор элементов. Это может быть и ряд целых чисел, сторона кубика Рубика или вообще, что угодно до тех пор, как это отвечает четырем определенным правилам или аксиомам.

Аксиома 1. Все операции в группе должны быть закрытыми ли ограниченными только для элементов группы. Так в нашем квадрате после каждой проделанной операции, например, повороте в одну или другую сторону, у нас все равно остаются все те же элементы группы.

Аксиома 2. Вне зависимости от того, где выполняя единую групповую операцию, мы поставим скобки, мы все равно получим один и тот же результат. Другими словами, если мы повернем квадрат направо два раза, а потом еще один – это то же самое, как если бы повернули его сначала один, а потом два раза. Если говорить о числах, это как один плюс два равняется два плюс один.

Аксиома 3. Для каждой операции в группе всегда есть элемент называющий нейтральный. Когда мы применяем его к другому элементу группы, этот элемент не меняется. Так и для поворота квадрата, и для сложения чисел нейтральный элемент – это ноль. Не очень-то захватывающе.

Аксиома 4. В каждом элементе группы есть элемент, называемый обратным. То же самое и у самой группы. При сложении двух таких элементов они дают нейтральный элемент – ноль. Поэтому можно считать, что они нейтрализуют друг друга.

Итак, все это, конечно, здорово, но какой в этом смысл? Когда мы понимаем все эти основные правила, появляются интересные свойства. Например, давайте расширим наш квадрат обратно в полный кубик Рубика. Это все так же остается группой, которая соответствует всем четырем аксиомам, хотя теперь у нас есть гораздо больше элементов и операций. Мы можем поворачивать каждый ряд и колонну каждой стороны. Каждая такая позиция называется перестановкой. И чем больше элементов в группе, тем больше существует перестановок. В кубике Рубика их более 43 квинтиллионов, так что пытаться решить его наугад – не лучшее решение.

Однако, используя теорию групп, мы можем проанализировать куб и определить последовательность перестановок, которые приведут к решению. И на самом деле именно это и делает большинство собирающих, иногда даже используя знаки теории, чтобы обозначить повороты.

Это работает не только для решения головоломок, теория групп глубоко связана также и с музыкой. Один из способов визуализировать аккорд – выписать все 12 нот и нарисовать между ними квадрат. Мы можем начать с любой, но давайте воспользуемся «до», раз уж она оказалась сверху. Получившийся в результате аккорд называется седьмым убывающим аккордом.

Теперь эта группа с этими четырьмя нотами в качестве элементов. Мы можем переставить нижнюю ноту наверх. В музыке это называется обращение и эквивалентно ассоциативности. Каждое обращение меняет звучание аккорда, но он все также остается «до» седьмым убывающим. Другими словами, это удовлетворяет аксиоме один. Композиты используют обращения, чтобы избежать нестройного звучания мелодии.

В музыке обращение выглядит так, но мы можем переложить это на наш квадрат и получить вот, что. Если вы покроете весь кубик Рубика нотами так, что каждая сторона собранного куба будет гармоническим аккордом, вы сможете выразить решение последовательностью аккордов, постепенно идущей от диссонанса гармонии и играть на кубике Рубика, если, конечно, это ваше.

Дата: 2013-12-24 Редактор: Загуменный Владислав

Матема?тика ку?бика Ру?бика — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Изучает алгоритмы сборки кубика, оценки алгоритмов его сборки и др. Основана на теории графов, теории групп, теории вычислимости, комбинаторике.

Существует множество алгоритмов, предназначенных для перевода кубика Рубика из произвольной конфигурации в конечную конфигурацию (собранную, все грани одноцветны). В 2010 г. строго доказано, что для перевода кубика Рубика из произвольной конфигурации в собранную конфигурацию (часто этот процесс называют «сборкой» или «решением») достаточно не более чем 20 поворотов граней. Это число является диаметром графа Кэли группы кубика Рубика. Алгоритм, который решает головоломку за минимально возможное количество ходов, называют алгоритмом Бога.

Алгоритма Бога кубика Рубика

История поиска алгоритма Бога кубика Рубика началась не позже 1980 года, когда открылся список рассылки для любителей кубика Рубика. С тех пор математики, программисты и просто любители стремились найти алгоритм Бога — алгоритм, который бы позволил на практике решать кубик Рубика за минимальное число ходов. С этой проблемой была связана проблема определения числа Бога — числа ходов, всегда достаточного для сборки головоломки.

В июле 2010 года программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что каждая конфигурация кубика Рубика может быть решена не более чем в 20 ходов. При этом любой поворот грани считался одним ходом. Таким образом, число Бога в метрике FTM оказалось равно 20 ходам. Объём вычислений составил около 35 лет процессорного времени, пожертвованного компанией Google. Технические данные о производительности и количестве компьютеров не разглашаются; продолжительность вычислений составляла несколько недель.

Нижние оценки числа Бога

Достаточно легко показать, что существуют разрешимые конфигурации, которые не могут быть решены менее чем в 17 ходов в метрике FTM или 19 ходов в метрике QTM.

Эту оценку можно улучшить, принимая во внимание дополнительные тождества, например, коммутативность поворотов двух противоположных граней (L R = R L, L2 R = R L2 и т. д.) Подобный подход позволяет получить нижнюю оценку для числа Бога, равную 18f или 21q.

«Суперфлип» — первая обнаруженная конфигурация, находящаяся на расстоянии 20f* от начальной Эта оценка в течение многих лет оставалась наилучшей известной. Кроме того, она вытекает из неконструктивного доказательства, так как оно не указывает конкретный пример конфигурации, требующей для сборки 18f или 21q.

Одной из конфигураций, для которой не удавалось найти короткое решение, был так называемый «суперфлип» (англ.), или «12-флип». «Суперфлип» представляет собой конфигурацию, в которой все угловые и рёберные кубики находятся на своих местах, но каждый рёберный кубик ориентирован противоположно.

Вершина, отвечающая суперфлипу в графе кубика Рубика, является локальным максимумом: любой ход из этой конфигурации уменьшает расстояние до начальной конфигурации. Это дало основание предположить, что суперфлип находится на максимальном расстоянии от начальной конфигурации, то есть является глобальным максимумом.

В 1992 году Дик Т. Винтер нашёл решение суперфлипа в 20f. В 1995 году Майкл Рид доказал оптимальность этого решения, в результате чего нижняя оценка числа Бога стала равной 20 FTM. В том же году Майкл Рид обнаружил решение «суперфлипа» в 24q. Оптимальность этого решения была доказана Джерри Брайаном.

В 1998 году Майкл Рид нашёл конфигурацию, оптимальное решение которой составляло 26q*. По состоянию на июль 2013 года, это число является наилучшей известной нижней оценкой числа Бога в метрике QTM.

Верхние оценки числа Бога

Чтобы получить оценку сверху для числа Бога, достаточно указать любой алгоритм сборки головоломки, состоящий из конечного числа ходов.

Первые оценки сверху для числа Бога были основаны на «человеческих» алгоритмах, состоящих из нескольких этапов. Сложение оценок сверху для каждого из этапов позволяло получить итоговую оценку порядка нескольких десятков или сотен ходов.

Вероятно, впервые конкретная оценка сверху была указана Дэвидом Сингмастером в 1979 году. Его алгоритм сборки позволял решить кубик Рубика не более чем за 277 ходов. Позднее Сингмастер сообщил, что Элвин Берлекэмп, Джон Конвей и Ричард Гай. разработали алгоритм сборки, требующий не более 160 ходов. Вскоре после этого группа «Conway’s Cambridge Cubists», которая занималась составлением списка комбинаций для одной грани, нашла 94-ходовый алгоритм.