Российская Информационная Сеть
English   Контакты
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ
ТОП-дайджест  Хроника  Эксклюзив  Фоторепортажи  Личное мнение  Погода  Комментарии  Поиск  RSS  Интернет-радио  
 Топ 20 сегодня Топ 20 сегодня 
"Прогресс" успешно стартовал с космодрома Байконур"Прогресс" успешно стартовал с космодрома Байконур
На пляже во Флориде был найден труп недоеденной акулыНа пляже во Флориде был найден труп недоеденной акулы
далее топ дня...
 Фотожурнал: фото-топ за месяц, галерея всех фото Фотожурнал 
 Новости партнеров
 Топ новости разделов сегодня Топ новости разделов 
Украина заблокировала заявление СБ ООН, посвященное Виталию ЧуркинуУкраина заблокировала заявление СБ ООН, посвященное Виталию Чуркину
Китай прекращает импорт угля из Северной КореиКитай прекращает импорт угля из Северной Кореи
На пляже во Флориде был найден труп недоеденной акулыНа пляже во Флориде был найден труп недоеденной акулы
"Прогресс" успешно стартовал с космодрома Байконур"Прогресс" успешно стартовал с космодрома Байконур
СМИ: популярные мессенджеры будут работать под закономСМИ: популярные мессенджеры будут работать под законом
К зданию МИД РФ несут цветы в память о ЧуркинеК зданию МИД РФ несут цветы в память о Чуркине
В Башкирии водители маршруток устроили перестрелкуВ Башкирии водители маршруток устроили перестрелку
В Башкирии водители маршруток устроили перестрелкуВ Башкирии водители маршруток устроили перестрелку
Дружба с экс-возлюбленными вызывает психические расстройстваДружба с экс-возлюбленными вызывает психические расстройства
Харрисон Форд едва не разбился на своем самолетеХаррисон Форд едва не разбился на своем самолете
далее...
 Личное мнение Личное мнение 

 Новости о знаменитостях Знаменитости 
Новость: 16 июля 18:13: Новости проекта "Дом-2": один из участников расплакался из-за изменыНовости проекта "Дом-2": один из участников расплакался из-за измены

Новость: 9 июля 23:36: VIA-Летта (Дядюра Виолетта) feat. Пьер Нарцис - Лето (видео)VIA-Летта (Дядюра Виолетта) feat. Пьер Нарцис - Лето (видео)


 Заплатим за ваше мнение!
Получайте до 1,5 долларов за каждую заполненную анкету!



 Новости Hi-Tech Новости Hi-Tech 
12 марта, 10:53

Ученые вычислили сложность Mario и Donkey Kong

Новости Hi-Tech: Ученые вычислили сложность Mario и Donkey Kong
Международная группа исследователей из Массачусетского технологического института и Брюссельского свободного университета определила сложность пяти серий классических игр от Nindendo - Mario, Donkey Kong, Zelda, Pockemon и Metroid.

Статья ученых пока не принята к публикации в рецензируемом журнале, однако, ее препринт доступен на сайте arXiv.org.

В рамках работы ученые формализовали игры при помощи машины Тьюринга - универсальной модели вычислительного устройства. Уровни в большинстве этих игр представляют собой некий лабиринт ограниченного размера с фиксированным набором ловушек. Вопрос, алгоритмическую сложность решения которого предполагалось определить, ученые формулировали следующим образом: для заданного состояния всех ловушек в лабиринте и местоположения врагов существует ли способ попасть из начала в конец лабиринта.

Всего ученые рассматривали Super Mario Bros. 1, 3, Lost Levels, Super Mario World, Donkey Kong Country 1-3, все игры Legend of Zelda (за исключением Zelda II), а также все игры серии Metroid и Pockemon. Оказалось, что вопрос определения "разрешимости" уровня имеет сложность NP. Это означает, что недетерминированная машина Тьюринга решает такую задачу за полиномиальное время.

При этом вопрос для Mario и Donkey Kong оказался NP-полным, то есть всякая задача в классе NP может быть сведена к данной за полиномиальное время обычной машиной Тьюринга. Также оказалось, что некоторые игры из серии Zelda имеют сложность PSPACE, то есть для решения задачи требуется полиномиальное количество памяти. По словам исследователей, полученные ими результаты позволяют оценить снизу сложность поиска оптимального пути между двумя точками в таких играх - очевидно, что поиск подобного пути заведомо не сложнее вопроса разрешимости того или иного лабиринта.

Вместе с тем исследователи отмечают, что естественная модификация лабиринта позволила заметно упростить задачу. Исследователи обратили внимание на то, что в играх наподобие классического Mario все ловушки и враги вне фиксированной области (видимого экрана) всегда находятся в неподвижном дефолтном состоянии. В случае, когда в добавок размеры лабиринта заведомо ограничены, ученые показали, что задачу можно решить за полиномиальное время на обычной машине Тьюринга.

В феврале в arXiv.org появились работы, в которых ученые аналогичным образом вычислили сложность игры Scrabble ("Скрэббл"), известной в русском варианте как "Эрудит", а также нескольких классических игр, например, Pacman.
[Читать все комментарии] [Напечатать новость]
LENTA.RU http://lenta.ru
  Комментарии к новости 
[Добавить комментарий]

Комментариев к этой новости пока нет. Добавьте первым свой комментарий!
[Добавить комментарий]
 Хроника новостей: Новости Hi-Tech Хроника новостей 
СМИ: популярные мессенджеры будут работать под законом

24 января 10:26
Программиста Станислава Лисова перевели в другую испанскую тюрьму

23 января 13:56
Компания Nintendo выпустила новую игровую консоль

13 января 11:55
В Китае разрабатывают технологию распознавания лиц

17 ноября 13:33
Apple представляет iPhone 7

8 сентября 10:05
Google запустил новый видеосервис Duo

16 августа 13:16
Новая технология защитит телефоны от robocall

4 августа 13:05
Apple заменит смайлик изображающий пистолет

2 августа 15:15
Спецслужбы вскрыли iPhone террориста

29 марта 16:08
Директор ФБР рассказал о конфликте с Apple

26 февраля 11:57
Американцы разработали удочку с Wi-Fi

12 февраля 10:48
Инженеры трудятся над виртуальной реальностью

9 февраля 12:54
Роскомнадзор закрыл самый крупный пиратский ресурс "Rutracker"

5 февраля 10:56
Российские инженеры создали робота-патрульного

20 января 11:41
Samsung официально представила Galaxy A9

25 декабря 11:36
В консольную World of Tanks временно добавили режим "Танчики"

24 декабря 17:10
Facebook выучится обновлять ленту новостей в оффлайне

11 декабря 11:54
Список самых надежных ноутбуков во всем мире

4 декабря 11:57
Японцы разработали моющийся смартфон (видео)

3 декабря 15:18
Apple тестирует iPhone 7 без кнопок

2 декабря 14:35
В работе Viber случился масштабный сбой

27 ноября 16:23
Wi-Fi может выдавать электроэнергию

26 ноября 14:58
Google Glass трудится над 3-мя новыми приспособлениями

19 ноября 11:19
В Fallout 4 воссоздали героев Tomb Raider и "Во все тяжкие"

11 ноября 11:59
Открытость Facebook беспокоит пользователей

10 ноября 12:17
Facebook отправит пользователей в виртуальный мир

5 ноября 11:19
Шутер Halo 5: Guardians поступил в продажу

27 октября 14:18
Assassin`s Creed: Syndicate поступил в продажу

23 октября 12:56
Twitter объявил о запуске новой функции

22 октября 12:18
В России стартовали продажи iPhone 6s

9 октября 09:35
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 >> 470
 Главная новость дня Главная новость дня 
Украина заблокировала заявление СБ ООН, посвященное Виталию Чуркину Украина заблокировала заявление СБ ООН, посвященное Виталию Чуркину
 
 Эксклюзив Эксклюзив 
Пора ли продавать акции Apple? Пора ли продавать акции Apple?
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
Мадонна заставила сына провести с ней каникулы
Лидер группы Motorhead скончался от рака
Лидер группы Motorhead скончался от рака
Скончался лидер группы Eagles Гленн Фрей
Шепелева обвинили во лжи
 Новости партнеров
 Новости дня Новости дня 
 
Новость: Украина заблокировала заявление СБ ООН, посвященное Виталию ЧуркинуУкраина заблокировала заявление СБ ООН, посвященное Виталию Чуркину
 
Новость: Появились новые подробности вокруг расследования убийства Ким Чен НамаПоявились новые подробности вокруг расследования убийства Ким Чен Нама
 
Новость: В Башкирии водители маршруток устроили перестрелкуВ Башкирии водители маршруток устроили перестрелку
 
Новость: Осужден бывший глава Гонконга Дональд ЦангОсужден бывший глава Гонконга Дональд Цанг
 
Новость: Трамп готовит иммигрантов к депортацииТрамп готовит иммигрантов к депортации
 
Новость: В Белгородской области врачи забыли в теле пациентки бинтВ Белгородской области врачи забыли в теле пациентки бинт
 
  Copyright © RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ