Вебмастеру:
Добавьте разнообразия на страницы Вашего сайта при помощи
легко настраиваемого под Ваш дизайн новостного информера
 
лента новостей

 

идет обновление информации.

 

 
ТОП месяца

 

идет обновление информации.


 
поиск

 


 

:: расширенный поиск ::

 

 
меню 
 
интересное в сети

 

 

 

 

 

 

 
наука и техника
30/01/2012 18:32

Итальянец посчитал сложность выигрыша в классические компьютерные игры

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

В рамках работы Вильетта оценивал сложность вычисления последовательности действий, который приводят к победе в игре. В первой части статья итальянец приводит серию теорем, которые позволяют связать вычислительную сложность игры с наличием в ней некоторых конкретных элементов. К последним, например, относятся рычаги, которые надо нажать, чтобы открылась некоторая дверь, призы, которые необходимо собирать, и многое другое.

Как оказалось, большая часть игр принадлежит к так называемому классу NP - это задачи, решающиеся за полиномиальное время на недетерминированной машине Тьюринга (то есть машине, программа которой допускает развилки). Также нашлись игры, принадлежащие к классу P (полиномиальное время на детерминированной машине Тьюринга), L (задачи, решаемые с привлечение логарифмически зависящего от начальных данных количества памяти детерминированной машиной Тьюринга), NL (то же, что и L, только машина недетрминированная) и PSPACE .

Кроме этого, несколько задач оказались NP-полными и PSPACE-полными. По сути это самые сложные задачи в своих классах - к ним за полиномиальное время можно свести любую задачу из данного класса. Например, к NP-полным задачам относится задача коммивояжера - поиск замкнутого кратчайшего пути в графе, который проходит по каждой вершине хотя бы один раз.

Полный список результатов выглядит следующим образом: Boulder Dash (1984) - сложность NP Deflektor (1987) - сложность L Doom (1993) - сложность PSPACE Lemmings (1991) - сложность NP Lode Runner (1983) - сложность NP Mindbender (1989) - сложность NL Pac-Man (1980) - сложность NP Pipe Mania (1989) - NP-полная игра Prince of Persia (1989) - PSPACE-полная игра Puzzle Bobble 3 (1996) - NP-полная игра Skweek (1989) - NP-полная игра Starcraft (1998) - сложность NP Tron (1982) - сложность NP

Вильетта также заявил, что аналогичный анализ для современных игр смысла не имеет, так как в них могут встречаться неразрешимые головоломки.

 

Оригинал (на 30/01/2012): lenta.ru

 

В случае обнаружения неточностей или ошибок
просим Вас сообщить об этом по адресу

 

 

 

 

 

Северокорейские мобильники обязали соблюдать траур по Ким Чен Иру

Северокорейские мобильники обязали соблюдать траур по Ким Чен Иру

Гражданам Северной Корее запретили пользоваться мобильной связью в ходе стодневного траура по скончавшемуся 17 декабря лидеру КНДР Ким Чен Иру. Попытка воспользоваться сотовым телефоном будет...

 

Генетики нашли родину американских индейцев на Алтае

Генетики нашли родину американских индейцев на Алтае

Генетики установили, что американские индейцы пришли на американский континент с территории современного Алтая. В рамках работы ученые анализировали ДНК современных обитателей Алтая. Они сравнивали...

 

Сервис Filesonic отключил функцию обмена файлами

Сервис Filesonic отключил функцию обмена файлами

Файловый хостинг Filesonic отключил функцию коллективного использования файлов. Теперь сервис может использоваться только для личного хранения контента. Причины таких изменений неизвестны, но,...

 

СМИ назначили выход iPad 3 на март

СМИ назначили выход iPad 3 на март

Планшеты iPad 3, по неофициальным данным, поступят в продажу в марте. Они получат четырехъядерный процессор и смогут работать в сетях LTE. Также ожидается, что Apple увеличит разрешение экрана....

 

Израильские археологи нашли любовный подарок

Израильские археологи нашли любовный подарок

Израильские археологи нашли в Еврейском квартале Иерусалима керамическую трубку с любовной надписью на арабском. По мнению археологов, трубка с надписью "Сердце - это язык для влюбленных" могла...

 

Японцы определили возраст хондритов

Японцы определили возраст хондритов

Японские астрономы определили возраст углистых хондритов по новой методологии. Оказалось, что метеориты моложе, чем предсказывают существующие теории. Углистые хондриты - редкий вид астероидов,...

 

 

 

 

:: все новости из этой категории на 30/01/2012 ::

 

 

последняя новость  
 

идет обновление информации.

архив
 
 
2006 |  2007 |  2008 |  2009
2010 |  2011 |  2012 |  2013
2014 |  201520162017
2018 |  2019 |  2020 |  2021 | 

Январь, 2012
Пн Вт Ср Чт Пт Сб Вск
      1
2345678
9101112131415
16171819202122
23242526272829
3031     

 

опрос  
 

 

Для Вас фаст-фуд - это:

 

Удобный способ быстро перекусить

 

Дешевая еда на каждый день

 

Отрава для человеческого желудка

 

Понятия не имею, что это такое

 

 

 

:: результаты опроса ::