"Русский переплет" зарегистрирован как СМИ.
Свидетельство о регистрации в Министерстве печати РФ: Эл. #77-4362 от
5 февраля 2001 года. При полном или частичном использовании
материалов ссылка на www.pereplet.ru обязательна.
|
14.03.2012 00:21 |
"Кассини" сфотографировал Рею
Астрономы, работающие с "Кассини", опубликовали снимки сатурнианского спутника Рея. Фото и их описания доступны на сайте Лаборатории реактивного движения. Все . . . |
13.03.2012 21:32 |
Яндекс запустил Навигатор
13 марта cпециально для автолюбителей Яндекс выпустил бесплатное мобильное приложение Навигатор. В нем есть всё, что нужно человеку за рулем: актуальные карты, . . . |
12.03.2012 22:28 |
Ученые вычислили сложность Mario и Donkey Kong Международная группа исследователей из Массачусетского технологического института и Брюссельского свободного университета определила сложность пяти серий классических игр от Nintendo - Mario, Donkey Kong, Zelda, Pokemon и Metroid. Статья ученых пока не принята к публикации в рецензируемом журнале, однако, ее препринт доступен на сайте arXiv.org.
В рамках работы ученые формализовали игры при помощи машины Тьюринга - универсальной модели вычислительного устройства. Уровни в большинстве этих игр представляют собой некий лабиринт ограниченного размера с фиксированным набором ловушек. Вопрос, алгоритмическую сложность решения которого предполагалось определить, ученые формулировали следующим образом: для заданного состояния всех ловушек в лабиринте и местоположения врагов существует ли способ попасть из начала в конец лабиринта.
Всего ученые рассматривали Super Mario Bros. 1, 3, Lost Levels, Super Mario World, Donkey Kong Country 1-3, все игры Legend of Zelda (за исключением Zelda II), а также все игры серии Metroid и Pokemon. Оказалось, что вопрос определения "разрешимости" уровня имеет сложность NP. Это означает, что недетерминированная машина Тьюринга решает такую задачу за полиномиальное время.
При этом вопрос для Mario и Donkey Kong оказался NP-полным, то есть всякая задача в классе NP может быть сведена к данной за полиномиальное время обычной машиной Тьюринга. Также оказалось, что некоторые игры из серии Zelda имеют сложность PSPACE, то есть для решения задачи требуется полиномиальное количество памяти. По словам исследователей, полученные ими результаты позволяют оценить снизу сложность поиска оптимального пути между двумя точками в таких играх - очевидно, что поиск подобного пути заведомо не проще вопроса разрешимости того или иного лабиринта.
Вместе с тем исследователи отмечают, что естественная модификация лабиринта позволила заметно упростить задачу. Исследователи обратили внимание на то, что в играх наподобие классического Mario все ловушки и враги вне фиксированной области (видимого экрана) всегда находятся в неподвижном дефолтном состоянии. В случае, когда еще размеры лабиринта заведомо ограничены, ученые показали, что задачу можно решить за полиномиальное время на обычной машине Тьюринга.
В феврале в arXiv.org появились работы, в которых ученые аналогичным образом вычислили сложность игры Scrabble ("Скрэббл"), известной в русском варианте как "Эрудит", а также нескольких классических игр, например, Pacman.
|
12.03.2012 22:25 |
В США скончался "разрушитель" озонового слоя Земли
В США в возрасте 84 лет скончался химик Фрэнк Шервуд Роуланд, нобелевский лауреат, открывший механизм воздействия человека на озоновый слой Земли. Об этом сообщает . . . |
12.03.2012 22:22 |
Пшенице вернули потерянный ген
Австралийские ученые установили ген устойчивости к высокому содержанию соли, утраченный пшеницей в процессе одомашнивания, и ввели его в современные сорта . . . |
12.03.2012 22:21 |
Физики впервые проверили принцип Ландауэра на практике
Физики впервые на практике продемонстрировали так называемый принцип Ландауэра. Статья ученых появилась в журнале Nature. Принцип Ландауэра был сформулирован . . . |
12.03.2012 22:18 |
Астрономы объяснили магнитные пятна на Луне
Ученые предложили объяснение магнитным аномалиям, обнаруженным американскими миссиями "Аполлон". Все они - следствие падения огромного метеорита в далеком . . . |
12.03.2012 22:15 |
Нейтринные осцилляции удивили физиков
Международная группа физиков, в которую входят и российские исследователи, измерила важный параметр нейтринных осцилляций - так называемый тета 1-3, который . . . |
12.03.2012 22:12 |
Климатологи ухудшили прогноз гренландскому леднику
Группа испанских и немецких климатологов под руководством Андрея Ганапольского провела моделирование устойчивости снежного покрова Гренландии к глобальному . . . |
12.03.2012 22:10 |
Палеонтологи нашли древнейший скелет
Палеонтологи установили, что древнейшим скелетом обладала губкоподобная Coronacollina acula, жившая 550-560 миллионов лет назад на дне мирового океана. С находкой . . . |
12.03.2012 18:07 |
Контактные линзы станут вычислительной платформой?
Исследователи из Университета штата Вашингтон создали пробную версию устройства, способную произвести революцию в сфере интерактивной визуальной информации . . . |
12.03.2012 17:34 |
Cisco и NetApp помогают клиентам ускорить переход на частное облако Microsoft
Решение FlexPod от NetApp и Cisco для построения частного облака Microsoft инсталлировано в Технологическом центре Microsoft в Москве Виртуализация центров обработки данных (ЦОД) . . . |
11.03.2012 20:26 |
В России открылась первая Академия Cisco для людей с ограниченными возможностями здоровья
В России начала работу Академия Cisco для людей с ограниченными возможностями здоровья (Academy of Borderless Possibilities). Этот некоммерческий проект реализуется по инициативе . . . |
11.03.2012 19:37 |
Microsoft займется разработкой сверхотзывчивых сенсорных экранов
Инженеры Microsoft займутся разработкой сенсорного экрана, который будет "отзываться" на прикосновения пользователя в сто раз быстрее, чем современные образцы, . . . |
11.03.2012 19:32 |
В лектории "Популярной механики" расскажут о трансе и сознании
В марте в лектории "Популярной механики" состоятся три лекции по астрофизике и биологии. Они пройдут в кинотеатре "35 ММ". Начало всех лекций в 19:30, а цена входного . . . |
11.03.2012 19:28 |
Астрономы сфотографировали галактическое скопление в Геркулесе
Астрономы из Европейской южной обсерватории (ESO), работающие с телескопом VLT, опубликовали снимки галактического скопления Abell 2151. Фото и их описания доступны на . . . |
11.03.2012 19:19 |
Итальянцы составили карту поверхности Мохоровичича
Группа итальянских ученых впервые составила глобальную карту в высоком разрешении границы между земной корой и мантией, известной как поверхность Мохоровичича . . . |
11.03.2012 19:17 |
Физики придумали самые точные атомные часы
Ученые из Университета Нового Южного Уэльса предложили схему атомных часов, которые превосходят по точности современные аналоги на несколько порядков. Подобная . . . |
11.03.2012 19:14 |
Обнаружен новый тип клеточной ДНК
Новый тип небольшой кольцевой нехромосомной ДНК со средним размером 200-400 пар оснований обнаружили биологи в клетках мышей и человека. Результаты их работы . . . |
11.03.2012 19:12 |
Физики нашли волны в полярных сияниях
Физики обнаружили у полярных сияний турбулентные явления (связанные с так называемыми ленгмюровскими волнами), которые раньше получались только искусственным . . . |