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

 

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

 

 
ТОП месяца

 

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


 
поиск

 


 

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

 

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

 

 

 

 

 

 

 
наука и техника
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

 

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

 

 

 

 

 

В Германии палеонтологи открыли новый вид динозавров

В Германии палеонтологи открыли новый вид динозавров

Ученые из разных стран открыли новый вид морских динозавров. Открытие было сделано благодаря находке 2005 года. Все это время палеонтологи проводили исследование в Естественно-историческом музее...

 

В Gmail появится защита от "клавиатурных шпионов"

В Gmail появится защита от "клавиатурных шпионов"

Google тестирует функцию Sesame, которая позволит обезопасить пользователей от "клавиатурных шпионов" в интернет-кафе. Чтобы зайти в почту с общественного компьютера, предлагается сфотографировать...

 

Исходный код webOS обнародуют в сентябре

Исходный код webOS обнародуют в сентябре

Исходники мобильной операционной системы webOS будут полностью открыты к сентябрю 2012 года. Нынешний владелец webOS, компания Hewlett-Packard, уже представила первый компонент новой ОС, прикладную...

 

На записях советских зондов с Венеры нашли объекты со "свойствами живых существ"

На записях советских зондов с Венеры нашли объекты со "свойствами живых существ"

Советские зонды засняли в 70-х и 80-х годах прошлого века на поверхности Венеры объекты, обладающие "свойствами живых существ". Об этом в своей работе заявил заведующий лабораторией Института...

 

Разработчики получат ARM-версию Windows 8 в феврале

Разработчики получат ARM-версию Windows 8 в феврале

По неофициальным данным, Microsoft выпустит ARM-версию Windows 8 для разработчиков в феврале. Предполагается, что планшеты с Windows 8 на этой архитектуре будут дешевле планшетов на x86. Ранее Стив...

 

Россия и Европа задумали отправить аппарат на Ганимед

Россия и Европа задумали отправить аппарат на Ганимед

Роскосмос совместно с Европейским космическим агентством (ESA) планирует послать межпланетную станцию к Ганимеду. Также стало известно, что российские ученые не отказались от планов получить грунт...

 

 

 

 

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

 

 

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

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

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

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

 

опрос  
 

 

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

 

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

 

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

 

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

 

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

 

 

 

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