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

 

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

 

 
ТОП месяца

 

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


 
поиск

 


 

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

 

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

 

 

 

 

 

 

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

 

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

 

 

 

 

 

Samsung открестилась от намерения купить производителя BlackBerry

Samsung открестилась от намерения купить производителя BlackBerry

Представители Samsung опровергли слухи о покупке компании Research in Motion. Они заявили, что никогда не испытывали интереса к RIM. О возможной сделке между двумя компаниями сообщил техноблог BGR....

 

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

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

Физики сделали первый в мире атомный рентгеновский лазер. В качестве активной среды в нем выступал газ неон, а для накачки использовался лазер LCLS. В последнем для получения излучения используются...

 

iPhone и Android сравнялись по продажам в США

iPhone и Android сравнялись по продажам в США

За октябрь-декабрь 2011 года американцы купили примерно поровну смартфонов Android и iPhone. При этом за квартал показатели Android сильно снизились, а iPhone - выросли. Рост интереса к аппаратам...

 

"Яндекс.Фотки" научили распознавать лица

"Яндекс.Фотки" научили распознавать лица

На фотохостинге "Яндекс.Фотки" заработала технология распознавания лиц, позволяющая автоматически указывать людей на фотографиях. Для этого сначала необходимо несколько раз отметить на фотографии...

 

Sony основала новую линейку смартфонов

Sony основала новую линейку смартфонов

Sony представила смартфон Xperia S, который положил начало новой линейке Xperia NXT. Аппарат с 4,3-дюймовым экраном и двухъядерным процессором поступит в продажу в первом квартале года. Sony будет...

 

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

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

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

 

 

 

 

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

 

 

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

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

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

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

 

опрос  
 

 

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

 

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

 

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

 

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

 

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

 

 

 

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