Как стать автором
Обновить

Комментарии 130

Да. Пожалуй одна из самых известных головоломок будет занимать умы математиков еще долго.
Да.. Неплохо было бы и алгоритм выложить.. Это моя мечта..
Представляете, на глазах у удивленных людей, на спор за 20 с небольшим ходов собирать рубик из любого состояния... =)
Угу, а еще перед этим на глазух у изумленных людей, на бумажке просчитать 1-2 млн связанных состояний.
а кто-нибудь наблюдал за сколько в среднем ходов делают люди, которые легко собирают любую комбинацию рубика?
а то есть знакомые которые почти моментально, но наблюдать лень
собираю в среднем за три минуты - не моментально конечно, но все-таки =)
вот только без практики забывается
НЛО прилетело и опубликовало эту надпись здесь
ну парниша молодец конечно. а Вы соберете кубик? =)
НЛО прилетело и опубликовало эту надпись здесь
Понравилась фраза "...математиков-теоретиков, которые посвятили свою карьеру решению этой задачи..."
ага, "будет что внукам рассказать"
... внукам других математиков, у которых на кубик Рубика ушла не вся жизнь, а только её часть.
эта задача имеет большое прикладное значение.
да уж, нашли товарищи чем заняться :)
Заинтриговали. Можно ссылку или суть в двух словах?
Я представляю, каково им было бы узнать, что эту задачу сможет решить компьютер за небольшое количество часов..
Может не часов, а лет?
Максимальное количество ходов
в смысле - минимальное? :)
бррр... :\
минимальное имеет смысл только при заданном исходном состоянии.
Здесь речь идет о максимальном среди минимальных по всем исходным состояниям
:-)
ага, понял уже... со 2й попытки.
вредно что-то умное пытаться понять после 9 часов на работе :)
супремум :)
Максимин.
новояз
Нет. Математический сленг.Термины "Максимин" и "Минимакс" используются (по крайней мере у нас) на всех математических предметах.
Теже шинусы и чосинусы, это все индивидуально по преподам, кафедрам, обобщать все возникающие у них в голове ассоциации под мат.сленг не стал бы.
Минимакс и максимин - термины теории игр (совершенно не сленг, устоявшиеся). Супремум и инфимум - теории множеств.
как можете заметить во всех источниках эти "термины" заключаются в кавычки, что и означает их принадлежность именно к сленгу, с целью урезания полного выражения. Таким образом они не являются терминами теории игр.
Вы имеете в виду "синх" и "кош"?:)
Вот не понимаю. Какое у этой задачи ПРАКТИЧЕСКОЕ значение? Т.е скольким людям на земле станет жить лучше от того за 23 или за 21 ход можно собрать кубик-рубик. Идиотизм в чистом виде.
А какое практическое применение полетов на Марс? Скольким людям станет лучше жить от новых фоток его поверхности? Или какое практическое применение от попыток доказать теорему Ферма?

Есть фундаментальные науки, состоящая в частности из подобных задач, не имеющих практического применения. Но на их основе строиться очень многое в уже в прикладных сферах.
На счёт полезности полётов на Марс, я готов по спорить. Так как в Марсе вижу потенциальную планету обитания человека. Возможно это не очень скоро настанет, но настанет точно.
А не проще ли не засырать свою планету?
Проще, пока китайцы экспансию не начинают.
Ух-ты..новая обитель - Марс). Вы, наверное, не особо интересовались красной планетой) Либо сильно увлеклись просмотром к/ф "Вспомнить все".
нет, я прошёл Mass Effect.
Возомжно, пример не самый удачный. Но до практического применения и пользы от Марса так далеко, что на текущий момент это только убытки (и материальные и человеко-часы работы не самых плохих мозгов на планете), причем гораздо более значительные в сравнении с 7,8 ядро-лет вычислений, использованных для решения обсуждаемой задачи .
А не проще ли не засырать свою планету?

Причём тут засорение своей планеты? Я ж говорю не о переселении на Марс, а об потенциальной планете для обитания.

Ух-ты..новая обитель - Марс). Вы, наверное, не особо интересовались красной планетой) Либо сильно увлеклись просмотром к/ф "Вспомнить все".

Интересуюсь красной планетой в достаточной мере. Разумеется что это не наступит завтра, но наступит.

2 посмотреть профиль maximw
- Мобильные телефоны никогда не станут популярными, это очень дорого и вредно для здоровья...
- Человек ещё очень не скоро полетит в космос...
- Интернет - сеть которой будут пользоваться только учёные и военные...
Отличные цитаты. Они лишь подтверждают, то что предсказание практической пользы (или ее отсутствия) от развития той или иной идеи или достижения есть дело небалгодарное :)
и поэтому лучше идею развить, а там посмотрим, что получится:)
Простите за занудство, но не могли бы вы привести пример чего-то материального, в основу модели чего входит кубег?

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

Итак:
Решение задачи Кубика-рубина => Новые алгоритмы комбинаторики => Новые системы криптоанализа => Новые системы защиты информации => Государственная безопасность и коммерческая тайна.
Спасибо за пример, о данном направлении не задумывался.

PS: На ум сразу пришла статья, где описывалось, что с появлением молекулярных (нано?/био? — не помню) компьютеров мощности поднимутся на столько, что все(!) современные алгоритмы криптования станут просто бесполезны.
Скорее всего, речь шла о квантовых компьютерах :)
Извините, теорему Ферма уже доказали...
Огромное спасибо за ссылку! Поищу более подробную информацию по поводу этого доказательства. Одной лишь википедии сложно доверять в таком вопросе :)
Доказать, то доказали, и этих доказательств несколько.
Все ищут наиболее простое, цепляясь за слова самого Ферма
который говорил,что её можно доказать в пару строчек.
Едисвенное:он не привёл её доказательства, по слухам,
сославшись на нехватку бумаги под рукой.
Полет на Марс то как раз связан с практическими задачами. Насчет теоремы ферма не знаю. Возможно её доказательства могут открыть какие то скрытые закономерности.
В науке ПОЛНО задач гораздо более прикладных. А фундаментальная наука это тоже хорошо. Вот только важно чтобы у нее прицел был на прикладное применение. Пусть даже гипотетическое. А кубик-рубик идиотизм, во всяком случае пока мне не доказали обратное.
Практическое применение находят те технологии, которые разрабатываются для полётов на Марс.
Вообще вся космическая индустрия - это большой полигон, на котором делается множество открытий-изобретений-разработок, которыми мы затем наслаждаемся в реальной жизни. Множество полимерных материалов, например, обязаны своим изобретениям поискам идеальной одежды для космонавтов. то же и со множеством других изобретений
Призы за некоторые великие математические проблемы назначены не только потому, что сама проблема важна, но и в надежде, что все старые способы перепробованы и в поисках решения будет найден новый метод доказательство или построений.
Где-то слышал что у всех подобных игр практическое применение заключается в торможении работы учёных. В частности слышал про известную игру пятнашки, где на поле 4х4 находится 15 фишек с номерами и их нужно выстроить по прядку. Соответственно разрабатывается врагами для торможения технического прогресса страны противника. Вместо того чтоб придумывать новый вид оружия, учёный сидит и играется в пятнашки.
Так ведь это основы основ алгоритмов!
Ученый посидит-посидит, подумает. Используя теорию групп, поймет, что решить можно не все комбинации, до от злости нажмет красную кнопку.
Описанное Вами больше похоже на "офисный планктон", чем на реальных ученых, впрочем, и среди них есть "планктон" :)
ученый побьется головой об стену в своей задаче в течении двух- трех дней, потом поиграет 10 минут в пятнашки, переключит внимание, потом вернется к своей задачи со свежей головой - и увидит решение которое перед глазами
Не чувак ты неправ, если так рассуждать, то можно ваще на все забить и сидеть пиво у телека сосать!
Есть анекдот в тему - про негра, который нифига не делал, сидел под пальмой и ел бананы. ))
Дета тут в притчах вроде.
Угу, если забыть о том, сколько его собратьев не дожили даже до момента, когда они смогли бы съесть свой первый банан:(
НЛО прилетело и опубликовало эту надпись здесь
После сборки кубика за 21 ход, останется больше времени на изучение новых алгоритмов.
Может быть продолжить дальнейшее развития человечества подальше от обезьяны?
далеко не всё делается практики ради.
У Томаша Рокицки слишком много свободного времени.
Этот Томаш завтра свои вычисления применит где-нибудь в физике, алгоритмике или математике и завхатит весь мир со всякими майкрософтами и гуглами :)
Как правило у таких Томашей находится лаборант в очках, который и становится миллионером применяя идею в практической сфере. А сами теоретики кроме премий и грантов никакого богатства не наживают увы.
Помнится в детстве я собирал кубик-рубик путем переклеивания наклеек.))
Мне больше нравилось разбирать его на кусочки )
А я переклеиванием самих кусочков. Когда разбираешь - они всегда отламывались)
Я знал, знал, что не только я занимался этим :)
даже таким способом за 23 хода собрать невозможно )
Интересно, а за сколько ходов можно разложить пасъянс и другие игры они тоже считают?
Есть целый пласт игр, таких как Кубик Рубика и пятнашки (они называются механическими головоломками), задачка "Священники и черти" (логические головоломки), которые похоже решаются - через ориентированные графы. Для них всех существует понятие "божественный алгоритм" - алгоритм с минимальным числом ходов для решения задачи. Простой карточный пасьянс (как и покер, например) в число таких задачек не входит, он решается другими методами.
Косынку по 3 карты я как то за время меньшее минуты разложил, даже не помню за сколько, но 50 с чем-то. Скорее всего просто повезло.
А вот кубик Рубика я только одну сторону научился собирать :(

ЗЫ: Интересно, сколько народу сейчас ломанётся в Гугл искать алгоритм сборки?
Могу сказать что один то точно.

P.S. Я :)
о. на разкладку пасьянсов тратится я уверен куда больше машинного времени, чем на кубик-рубик. :)
На раскладку пасьянсов человеко-часов тратится больше (особенно на работе :) ), а так они решаются по простому подсчету вероятности. При определенной сноровке это даже в уме можно делать. Ну не со 100% точностью, конечно, но серьезно повышая свои шансы.
ФИДЕ вовремя проплатила Вассерману. Поэтому шахматы до сих пор не решены.

А вот по шашкам проплатить не успели… :(

Кстати, а что еще мы «не знаем» об Анатолии Вассермане? Смотрим (ну, или вспоминаем) здесь: http://boyany.nnm.ru/vsya_pravda_ob_anat… ;)

Пасьянсов существует множество видов. Для части их доказана сходимость(то есть, что при любом изначальном раскладе существует стратегия, ведущая к выигрышу). В частности, одним из таких пасьянсов является Freesell. Для других пасьянсов доказана несходимость - то есть, что существуют такие расклады, которые заведомо невозможно выиграть. К таким относится klondike, более известный у нас как "Косынка". Доказательством сходимости-несходимости некоторых пасьянсов занимались великие (и не очень) математики не одну сотню лет назад. Пасьянс - развлечение очень древнее, и, поскольку имеет некоторое отношение к математике, исследовалось очень давно и пристально.
Вспомнился фильм с Виллом Смитом "В погоде за счастьем". Там, помнится, он кубик Рубика собирает минуты за 2.
Для чемпионов по скоростной сборке кубика Рубика это вообще не результат :)
Более того, вот ссылка на видео, где мальчуган собирает кубик рубика ногами за 50 секунд.
здесь сборка четырех разнокалиберных кубиков за 5 минут
недавний мировой рекорд - 9,18 (в Википедии информация, кстати, до сих пор не обновлена)
За две я в детстве собирал без проблем. Это совсем не трудно.
Сейчас минуты за три-четыре соберу.
Одно дело сидеть и производить расчеты кол-ва комбинаций, а другое - собирать кубик одной рукой:)
на математики-теоретики нашли самый важный в своей области предмет для исследований. Это как американские ученый всякие ненужности исслдуют типо влияние лунного света на рост телеграфных столбов.

А ну Томаш Рокицки конечно молодец!))
Была бы возможность поднять касту поднял бы) >.
Была бы возможность поднять карму Томашу Рокицки, поднял бы ;)
лежит такая игрушка в машине у жены, когда едду в качестве пассажира в пробке есть чем полезным время убить
НЛО прилетело и опубликовало эту надпись здесь
Это... А где собственно алгоритм сборки за 23 хода? :)
Зажали видимо...)
Он не строил алгоритм, а оценивал диаметр гигантского графа состояний. Алгоритм — отдельная, совсем другая задача.
да-да, это же ТЕОРЕТИЧЕСКАЯ работа, а не практикум...
Я думаю алгоритм банальный. Выпускается книжка на 1000 страниц с фразой: "посмотрите на свой кубик Рубика, если у вас такая-то комбинация, поверните такую-то грань по/против часовой стрелки." И так 1000 страниц ;) И обещается что любую комбинацию можно разложить за максимум в 23 хода
Число возможных различных состояний кубика Рубика равно (8!
Извините, отфильтровалась формула. Хотел написать, что в книжке будет 43 252 003 274 489 856 000 страниц (такого колличество комбинаций кубика Рубика)
А зачем тратить целую страницу на одну комбинацию? Мелким шрифтом, с исключением некоторых простейших симметрий, думаю можно и в 1000 страниц уложится.
Обожаю кубик Рубика.
НЛО прилетело и опубликовало эту надпись здесь
Я думаю в журнале Квант дано развернутое объяснение фразы: " но оно вполне соответствует выкладкам математиков-теоретиков, которые посвятили свою карьеру решению этой задачи. Они предполагают, что минимальное количество ходов находится где-то в начале третьего десятка."
Т.е. все предпологали, что ходов 22-23, но точное доказательство получили только сейчас.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
23 хода, как я помню. В Кванте. И об этом вполне уверенно говорилось...
На самом деле тоже пугают подобные «исследования», оставляющие этот самый привкус дежавю...
НЛО прилетело и опубликовало эту надпись здесь
было кино с джимом керри, триллер что ли, 23 назывался :)
НЛО прилетело и опубликовало эту надпись здесь
О как) Кубик! Уже с большой буковки начали называть)))
Титановый, со стороной около километра.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
хорошо хоть над алгоритмом вкручивания лампочик за 22 "вращение" головы не ломают. Там вообще море комбинаций!
Блять ну почему эти сраные новости вызывают такой ажиотаж, все обсуждают и т.п. аж противно.
Боятся упустить потенциального гения. Талантливых людей надо уметь "выцепить" как можно быстрее. Ну, вы же сами видите, какая проблема обстоит с поиском специалистов.
А эти вычисления можно производить как распределенные? т.е. чтобы не искать суперкомпьюет а просто собрать сеть из нескольких тысяч компьютеров и считать себе спокойно, я бы свое процессорное время этому отдал не задумываясь
Отдай лучше в F@H, больше пользы будет, а этот фанатик еще машинного времени за свои деньги купит.
Кстати, если кого интересует алгоритм сборки кубика Рубика, могу поискать у себя бумажку с ним (в детстве мне отец нарисовал). Алгоритм заключается в постепенном сборе кубика и использованием определенных паттернов. Естественно медленный, естественно неоптимальный, зато позволяет собрать кубик и может использоваться для понтов.
В Википедии есть много очень хороших ссылок (особенно ссылки на Квант).
Я использую не самый оптимальный алгоритм (зато после половины сборки используется всего одна формула) и уверенно собираю кубик меньше, чем за 3 минуты. Чувствую, что уже пора переходить на более оптимальные алгоритмы и развивать мизинцы ;)
Ага, согласен, там всё есть. Просто я хотел показать постом, что всё не так страшно. Ведь если глядеть профессионалов, которые собирают на эвристике и интуиции, то становится очень боязно. :)
Как я понял, его «доказательство» заклюается в оптимизированном брутфорсе?
Законченные логические выкладки ведь эффективнее...
А как на счет теоретической модели и доказательства для такого монстра?
Создатель кубика-рубика, наверно, и представить себе не мог, что над его игрушкой будут ломать голову математики и компьютеры =)
Кубик Рубика отлично тренирует мозг.. По старой памяти помню, как у меня болела голова после часа "игры" с ним.
P.s. Недавно ехал в метро. Люди вели себя как обычно - кто спал, кто читал, а один парень ехал и собирал кубик Рубика. Скажу честно, я позавидовал...
Вообще процессор Intel Core 2 Quad Q6600 имеет частоту 2.4 ГГц, а не 1,6 ГГц, как указано в новости.
Я конечно понимаю, доказательство максимального числа ходов сборки кубика хорошо. Но как то уж получается решил он это брутфорсом. ИМХО не спортивно. Дайте мне такой кластер и я докажу, что квейк первый за 25 минут можно пройти ;)
на компе проверять неспортивно) надо математически доказывать)
Все время его имя читаю как Томаш Росицки (Чешский футболист) =)
А вообще на то она и фундаментальная наука математика что основа многим технологиям.
Я придумал, как значительно упростить вычислительное решение задачи о кубике Рубика.
kartz.ru/2012/01/02/rainbow-rubik/
Опубликовать его здесь сейчас не могу.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории