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

 Новости о знаменитостях Знаменитости 
Новость: 22 июля 09:00: Родион Газманов устроил "Самый яркий день"Родион Газманов устроил "Самый яркий день"

Новость: 19 августа 17:35: Муз-ТВ спровоцировало флэшмоб среди популярных поп-исполнителей и актёровМуз-ТВ спровоцировало флэшмоб среди популярных поп-исполнителей и актёров


 Заплатим за ваше мнение!
Получайте до 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 Хроника новостей 
В Великобритании создадут радар на случай "российской агрессии" в воздухе

27 января 10:04
Twitter не нашел доказательств российского вмешательства в Brexit

25 января 20:04
Минкомсвязь смягчила законопроект о регулировании интернет-трафика

23 января 10:04
Скоро sim-карта может заменить паспорт.

15 ноября 10:09
Чем хорош iPhone для современных девушек.

8 ноября 12:23
В России запретили анонимайзеры для обхода блокировок РКН

1 ноября 09:13
Еще один российский ритейлер заманивает покупателей трейдином смартфонов

31 октября 10:46
Страховщики предлагают страховать от атаки хакеров

27 октября 11:21
Десятый iPhone выпустят в 2 раза меньше от плана

25 октября 10:41
"Плохой кролик" атаковал банки России

25 октября 09:50
Министерство связи России обещает отмену международного роуминга

18 октября 12:59
Telegram в Москве присудили штраф почти на миллион рублей

17 октября 10:10
Мессенджер Telegram наконец стал легально поддерживать русский язык

11 октября 10:31
Лайфхаки со смартфоном, которые ты должен знать

9 октября 10:34
Наушники Google переводят с 40 языков в режиме реального времени

6 октября 12:14
IQ ИИ Google выше, чем у Siri и Bing

4 октября 09:42
Мессенджер Telegram могут заблокировать за неисполнение закона Яровой

27 сентября 08:41
Насколько безопасна идентификация по лицу в iPhone X?

18 сентября 11:04
Роскомнадзор тестирует новый способ блокировки запрещённых сайтов

15 сентября 12:21
Презентация iPhone X запомнилась конфузом

14 сентября 11:15
Обнаружен новый способ использования вашего компьютера злоумышленниками

14 сентября 10:11
Как iPhone 8 повлияет на ОС Android

11 сентября 16:20
Холодильник Panasonic сам привезёт продукты к дивану

10 сентября 10:52
Моторола предложила для смартфонов стекло, способное само ремонтировать трещины

5 сентября 12:49
Nokia 8 - новый флагман, претендующий на лидерство

5 сентября 08:51
Успешно приземлился российский спускаемый аппарат с космонавтами на борту

3 сентября 14:52
Айфон бьет рекорды популярности

18 августа 15:23
Несколько фактов о новом iPhone 7s

16 августа 15:18
Новый вид спама через сотовую связь

16 августа 15:03
В Viber появилась новая удобная функция

11 августа 14:36
 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 >> 471
 Главная новость дня Главная новость дня 
В России вступили в силу новые правила прохождения техосмотра
 
 Эксклюзив Эксклюзив 
Пора ли продавать акции Apple? Пора ли продавать акции Apple?
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
Канье Уэст принял на себя роль визуального художника
Актера Шайа ЛаБаф арестовали за драку с полицейским
Актер Шайя ЛаБаф лечится от алкогольной зависимости
Мария Адоевцева обвенчалась со своим мужчиной (фото)
Николас Кейдж сломал ногу во время съемок
 Новости партнеров
 Новости дня Новости дня 
 
  Copyright © RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ