Поистине, для тех, кто уверовал, делал добрые дела, выстаивал молитву и давал очистительный расход, ждет награда Господа.
Не познают они страха и печали.
(2:277)
Остерегайтесь (наказания Судного) Дня, в который вы будете возвращены к Богу.
Затем каждой душе полностью воздастся за то, что она приобрела, и они (души) не будут обижены.
(2:281)
Господи наш! Не уклоняй наши сердца после того, как Ты вывел нас на прямой путь,
и дай нам от Тебя милость: ведь Ты, поистине, - Податель!
(3:8)
Математики разобрались с гигантскими кубиками Рубика
[2011-07-01]
Газета "Наш Мир" Математики из Массачусетского технологического университета оценили
количество ходов, необходимых для решения кубика Рубика (то есть
приведения граней куба к одному цвету) произвольного размера. Препринт
их статьи (pdf) появился на сайте arXiv.org.
Исследования
кубика Рубика математиками начались в начале 80-х годов прошлого века
(сама головоломка была создана в 1974 году). Как оказалось, группа
симметрий кубика, действующая на множестве его квадратов, довольно
сложна и плохо поддается изучению. В 2010 году специалисты по теории игр
просчитали на суперкомпьютере все 43 252 003 274 489 856 000 возможных
первоначальных позиций для стандартного кубика Рубика (3 на 3 на 3) и
установили, что из любого начального положения кубик можно собрать всего
за 20 ходов.
В рамках нового исследования ученых интересовала
асимптотическая оценка количества движений, необходимых для решения
кубика Рубика (хотя, в данном случае, его правильнее было бы называть
прямоугольным параллелепипедом) с сторонами произвольной величины. В
качестве параметра оценки выступало число n - длина максимальной стороны
головоломки, а "асимптотическая" в названии означает, что оценка не
точная, но с ростом n оптимальное число ходов растет как оценка.
Исследователям удалось установить, что в общем случае количество ходов
есть O(n2) - то есть число необходимых для решения движений куба
увеличивается примерно как квадрат n, умноженный на некоторую константу.
При этом учеными предложен непосредственный алгоритм решения, который
реализует предложенную оценку.
В двух частных случаях ученым
удалось улучшить этот результат. Так, оказалось что для "кубического"
кубика Рубика, то есть головоломки с размерами n на n на n, и для
"веревки" Рубика - головоломки с размерами n на n на 1, оценка выглядит
как O(n2/log n). Последний эффект связан с тем, что за одно движение в
подобных головоломках можно ставить на нужное место сразу несколько
квадратов.
Задача о решении кубика Рубика относится к классу
алгоритмических задач реорганизации. Типичным примером такой задачи,
встречающимся на практике, является перестановка нужным образом коробок
на складе.
