151 день за решеткой. Катерина Борисевич
Коронавирус: свежие цифры
  1. «Путин сделал предложение, от которого нельзя отказаться». Эксперты — об отношении Кремля к «заговору»
  2. Рабочая неделя будет теплой, зато на выходных выпадет снег
  3. Врач-инфекционист рассказал, чем отличается третья волна коронавируса и когда ждать пик заболеваемости
  4. «Он не тот человек, который привык жаловаться». Девушка Эдуарда Бабарико — о его 10 месяцах в СИЗО
  5. Почему все говорят про футбольную Суперлигу? Рассказываем о скандальном проекте
  6. Магазины «Домашний» приказали долго жить
  7. В Браславе в костеле обвенчалась пара — жениху и невесте по 91 году
  8. Тест не для слабонервных. Какой герой «Игры престолов» так умер?
  9. В Бресте суд решил ликвидировать «Польскую школу»
  10. Нацбанк ожидает ускорения инфляции во втором квартале
  11. Песков: Путин и Байден обсуждали информацию о готовившемся покушении на Лукашенко
  12. «Уже не рецессия, но еще и не рост». Эксперты — о настроении бизнеса и его влиянии на экономику
  13. США возобновляют санкции против «Белнефтехима» и еще 8 белорусских госпредприятий
  14. Сколько получает, где хранит и как тратит. Как работает Фонд соцзащиты, из которого платят пенсии
  15. Их фура — их дом на колесах: как работает семья дальнобойщиков из Пинска, где жена — королева красоты
  16. Перестал выходить на связь бывший следователь СК Евгений Юшкевич. Он в СИЗО КГБ
  17. Санкции США, интересы Кремля, ожидания Нацбанка, «семейный дальнобой» и скандал с Суперлигой — все за вчера
  18. Громкие «преступления», которые якобы готовились в Беларуси из-за политики: до и после выборов 2020 года
  19. «Они не знают, наступит ли завтра». Белорусский фотограф показал жизнь бездомных котов без прикрас
  20. Поставил лайк — получи срок. Как в России и Казахстане сажают за экстремизм (у нас могут повторить)
  21. «Все оказались в выигрыше». Эксперты — о «предотвращении переворота» в Беларуси и роли России в этом
  22. «Осознание, что это действия не совсем законные, появилось позже». Замов Бабарико допрашивают в суде
  23. Как сейчас выглядит ТРЦ Minsk City Mall, который строится в районе вокзала
  24. С 20 апреля снова дорожает автомобильное топливо
  25. Что происходит с ИП, которым хотят поднять налоги и взносы: теряют рынок, падает товарооборот
  26. Биолог рассказал, как сделать рассаду крепкой. Нужно выполнить всего пять простых пунктов
  27. Узнали, что открывается на местах, где были магазины Bigzz
  28. «Банк умыл руки». Помните историю с изъятием ценностей из ячеек Белгазпромбанка? Спросили, вернули ли их
  29. От выстрелов под Лиозно до погреба в Гомельской области. Как «покушались» на Лукашенко
  30. «На фуфайке фамилия выбита другим цветом». Родные осужденных по политическим статьям о том, как те отбывают наказание


Фото пользователя Hellbus с сайта wikipedia.org
Фото пользователя Hellbus с сайта wikipedia.org
Математики из Массачусетского технологического университета оценили количество ходов, необходимых для решения кубика Рубика (то есть приведения граней куба к одному цвету) произвольного размера. Препринт их статьи (
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). Последний эффект связан с тем, что за одно движение в подобных головоломках можно ставить на нужное место сразу несколько квадратов.
Задача о решении кубика Рубика относится к классу алгоритмических задач реорганизации. Типичным примером такой задачи, встречающимся на практике, является перестановка нужным образом коробок на складе.
-35%
-26%
-15%
-50%
-50%
-18%
-5%
-15%
-30%
-21%