"Русский переплет" зарегистрирован как СМИ.
Свидетельство о регистрации в Министерстве печати РФ: Эл. #77-4362 от
5 февраля 2001 года. При полном или частичном использовании
материалов ссылка на www.pereplet.ru обязательна.
|
|
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.
|
|
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 |
Климатологи ухудшили прогноз гренландскому леднику
Группа испанских и немецких климатологов под руководством Андрея Ганапольского провела моделирование устойчивости снежного покрова Гренландии к глобальному . . . |
