"Русский переплет" зарегистрирован как СМИ.
Свидетельство о регистрации в Министерстве печати РФ: Эл. #77-4362 от
5 февраля 2001 года. При полном или частичном использовании
материалов ссылка на www.pereplet.ru обязательна.
|
|
14.03.2012
19:35 |
Яндекс открывает офисы в Европе
Яндекс открывает офис продаж, который будет продвигать рекламные продукты Яндекса в Европе. Новый офис зарегистрирован в Люцерне (Швейцария). Возглавит его Бернар . . . |
|
14.03.2012
19:25 |
HP готовит чип из 256 микропроцессоров, связанных лазерными лучами
К 2017 году компания Hewlett-Packard планирует выпустить микрочип, который будет создан по революционной технологии. Уникальность устройства заключается в том, что . . . |
|
14.03.2012
19:07 |
Россия поможет одиозному южнокорейскому биологу клонировать мамонта
Соглашение о сотрудничестве с целью возрождения мамонтов подписали сегодня, 13 марта 2012 года в Сеуле Василий Васильев, проректор Северо-Восточного федерального . . . |
|
14.03.2012
19:03 |
Самым острым зубам нашли применение
Ученые определили, как обладатели самых острых зубов из известных на настоящий момент - ископаемые конодонты - эти зубы использовали. Статья ученых вышла в журнале . . . |
|
14.03.2012
19:00 |
Австрийцы создали самый быстрый 3D-нанопринтер
Ученые из Венского технического университета создали самый быстрый на сегодняшний день 3D-принтер, работающий с нанометровой точностью. Об этом сообщается в . . . |
|
14.03.2012
18:55 |
Ботаники заглянули в память растений
Ботаники из института Небраски установили механизмы, благодаря которым растения запоминают пережитое высушивание и становятся более устойчивыми к нему . . . |
|
14.03.2012
18:51 |
Физики узнали причину главного недостатка графена
Группе физиков под руководством Кирилла Болотина из Университета Вандербильда удалось установить причину низкой электронной мобильности в графене. Кроме этого . . . |
|
14.03.2012
17:39 |
Школьник разработал новые методики лечения рака и победил в конкурсе Intel science talent search
На этой неделе все внимание общественности в столице США было привлечено к инновациям: от новейших решений для медицины до разработок в области альтернативных . . . |
|
14.03.2012
17:33 |
Intel создает систему школьных научных лабораторий
Корпорация Intel, фонд Intel Foundation совместно с АНО <Терциус> и Министерством образования Нижегородской области приступили к реализации проекта по созданию системы . . . |
|
14.03.2012
01:11 |
Intel совместно с Kraft Foods, Lego Group и UMA определяет будущее розничной торговли в Европе
∙По заказу Intel Оксфордский университет приступает к анализу и проработке будущей модели современных магазинов. ∙Intel представит на выставке Retail Business Technology Expo . . . |
|
14.03.2012
00:45 |
Sony представила смартфон с бесконтактным управлением
Sony анонсировала смартфон Xperia sola. Взаимодействовать с аппаратом пользователи могут бесконтактным способом. Экран в Xperia sola реагирует на действия пользователя даже . . . |
|
14.03.2012
00:42 |
В чемпионате США по разгадыванию кроссвордов примет участие компьютер
В 35-м ежегодном чемпионате США по решению кроссвордов, который будет проходить в Нью-Йорке с 16 по 18 марта, пример участие компьютерная программа Dr.Fill, сообщается на . . . |
|
14.03.2012
00:36 |
"Яндекс" представил сервис навигации
"Яндекс" представил навигационный сервис для смартфонов. Об этом компания рассказала 13 марта на специальной пресс-конференции. Бесплатное приложение . . . |
|
14.03.2012
00:32 |
Хищники оказались безразличны к сладкому
Американские биологи определили последовательность гена Tas1r2 у двенадцати различных хищных млекопитающих и установили, что многие из них потеряли способность . . . |
|
14.03.2012
00:30 |
Палеонтологи обнаружили древнейшую саламандру
Палеонтологи из США и Китая обнаружили древнейшую саламандру из известных на настоящий момент. Статья ученых появилась в журнале Proceedings of the National Academy of Sciences. Новый . . . |
|
14.03.2012
00:27 |
Роскосмос пообещал к 2030 году закрепиться в тройке космических лидеров
Роскосмос внес в правительство Российской Федерации проект стратегии развития отрасли до 2030 года. Об этом сообщает "Коммерсантъ". Проект был внесен еще на прошлой . . . |
|
14.03.2012
00:23 |
Геймеры победили компьютер в игре с ДНК
Люди в 70 процентах случаев лучше компьютера справляются с выравниванием нескольких небольших последовательностей ДНК. С таким результатом завершился . . . |
|
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.
|
