Журнал «Компьютерра» № 31 от 28 августа 2007 года

Академические компьютерщики периодически обращаются к разноцветному кубику не только на досуге: благодаря высочайшей вычислительной сложности задача о его сборке является отличным средством для тестирования быстродействия новейших процессоров. Чего стоит хотя бы число комбинаций кубика, равное 43 квинтиллионам (4,3х1019)! Кроме того, алгоритмы перебора "от Рубика" неплохо работают и в прикладных областях – например, при составлении авиарасписаний или визуальном представлении структуры белка. Нынешним летом поверить "божий промысел" алгеброй удалось сотрудникам кафедры компьютерных наук из Северо-Восточного университета в Бостоне Дэниелу Канклу (Daniel Kunkle) и Джину Куперману (Gene Cooperman).

Стремясь максимально облегчить задачу, исследователи решили считать идентичными две любые комбинации, в которых пара цветов поменяна местами друг относительно друга. Сначала в рассмотрение угодили «канонические» состояния кубика, решаемые лишь 180-градусными поворотами его граней. Таковых оказалось около 15 тысяч, при этом решение каждой из них укладывается в 13 ходов – с «расщелкиванием» всех этих комбинаций за одни сутки справится любой современный десктоп. Затем предстояло решить более сложную задачу – выяснить, за сколько ходов любое более сложное цветовое сочетание можно перевести в одно из уже просчитанных. Методом исключения «близнецов», переводимых к «каноническому» виду одной и той же последовательностью поворотов, круг сузился до 1,4 трлн. комбинаций, доверенных для обсчета университетскому суперкомпьютеру. По истечении 63 часов машинного времени стало ясно, что для решения любой комбинации потребуется не более 29 ходов. После того как самые «упрямые» состояния удалось «уговорить» при помощи оригинального алгоритма, выяснилось, что "число Бога" снизилось до 26. Это число, на единицу меньшее предыдущего рекорда, установленного в прошлом году сотрудниками Технологического института Лунда (Швеция), и прозвучало на форуме International Symposium on Symbolic and Algebraic Computation в канадском Ватерлоо. По-видимому, и это не предел: Канкл и Куперман рассчитывают вскоре улучшить свой результат на один «ход», а многие исследователи придерживаются мнения, что "число Бога" вообще равняется двадцати.

Как известно, дилетантов, нечасто вертящих в руках детище Рубика, всегда поражает время решения этой головоломки, демонстрируемое профессионалами на чемпионатах. Так, текущий мировой рекорд скоростной сборки, установленный корейцем Ю Ен-Мином в минувшем январе, составляет лишь 11,76 секунды! Что ж, в свете нынешнего исследования в этом нет ничего непостижимого. Ведь, действуя оптимальным образом, собрать кубик при любом раскладе можно менее чем за 9 секунд. Правда, при этом нужна самая малость: чтобы на каждом шаге его грани крутились в правильном направлении. ДК

Робот по травке бежит и хохочет…

Исследователи из Университета Цинциннати Джулия Тейлор и Ларри Мазлак (Julia Taylor, Larry Mazlack) создали компьютерную программу, которая «понимает» шутки. Разработка была представлена на Американской конференции по искусственному интеллекту (American Association for Artificial Intelli-gence). Программа в первую очередь пригодится для управления поведением роботов-компаньонов, которые большую часть времени находятся в прямом контакте с человеком, и для создания различных чат-сервисов. Как говорит Мазлак: "Это ПО призвано сделать машину более «неформальной» в общении".

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

Кафка сделан былью

"Круглое катить, квадратное тащить". Подобными заповедями в наши дни руководствуются не только грузчики, но и робоконструкторы, жестко подразделяющие электронных братьев меньших на шагающие и колесные модели. Впрочем, так ли уж велика пропасть между ногой и колесом – а что, если создать гибрид того и другого? Задавшись этим вопросом, японские робоконструкторы из Технологического института провинции Тиба создали робота-"двоеборца" Halluc II, которому по плечу участие и в заездах, и в забегах.