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