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

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

Новость: 18 августа 14:54: Слухи о закрытии передачи «Давай поженимся»Слухи о закрытии передачи «Давай поженимся»


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

10 августа 15:25
Были отозваны 275 тыс "жидких" чехлов для iPhone

2 августа 15:29
Microsoft отказался от приложения Paint

25 июля 14:39
В России нашли способ остановить распространение нового вируса "Петя"

28 июня 15:40
Вирус WannaCry проник в компьютеры автопроизводителя Honda

22 июня 12:33
Apple представила новые умные колонки HomePod

6 июня 12:38
Мир подвергся массовым кибератакам

15 мая 11:36
Galaxy S8 покорил Южную Корею

20 апреля 12:43
СМИ: популярные мессенджеры будут работать под законом

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

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

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