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

 

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

 

 
ТОП месяца

 

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


 
поиск

 


 

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

 

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

 

 

 

 

 

 

 
наука и техника
02/02/2012 13:44

Математики вычислили сложность игры "Скрэббл"

Математики вычислили сложность игры "Скрэббл" Ученые вычислили сложность игры Scrabble ("Скрэббл"), известной в русском варианте как "Эрудит". Статья исследователей пока не принята к публикации в рецензируемом журнале, однако ее препринт доступен на сайте arXiv.org.

Игра "Эрудит" состоит из поля-доски в 15 на 15 клеток и набора из 104 букв. Перед игрой каждый участник (которых может быть от 2 до 4) получает по 7 случайных букв из набора, а на середину игрового поля выкладывается начальное слово, составленное из оставшихся от раздачи букв. Затем игроки по очереди начинают выкладывать на доске собственные слова, например, слева направо и сверху вниз. Главное требование - каждое новое слово должно иметь общую букву или буквы с уже выложенными (все правила можно прочитать здесь ).

В рамках работы ученые интересовались следующим вопросом. Пусть на доске задана некоторая позиция - какова сложность алгоритма определения лучшей игровой стратегии? Традиционно ответы на подобные вопросы даются в виде утверждения о принадлежности задачи к некоторому классу сложности.

Эти классы определяются при помощи машины Тьюринга - универсальной модели вычислительного устройства. Мерой сложности алгоритма является либо количество действий, которые должна совершить машина в зависимости от длины строки входных данных, либо количество памяти, которое в зависимости от этой же строки надо задействовать.

В результате ученым удалось установить, что задача относится к классу PSPACE. Это означает, что для обработки входной строки длины n потребуется не более чем p(n) ячеек памяти, где p - некоторый многочлен. Более того, ученые установили, что задача PSPACE-полная, то есть любая другая задача из этого класса за полиномиальное время сводится к данной. В некотором смысле это PSPACE-полные - это самые сложные задачи класса PSPACE.

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

 

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

 

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

 

 

 

 

 

NASA сократит бюджет и откажется от Марса

NASA сократит бюджет и откажется от Марса

Бюджет NASA в 2013 году будет значительно сокращен, а кроме этого Американское космическое агентство отказывается от совместного с Европой проекта ExoMars. Финансирование научных программ снизится...

 

Биологи доказали "законность" строительства муравьиных дорог

Биологи доказали "законность" строительства муравьиных дорог

Международная группа биологов создала эффективную модель построения муравьиной сети для доставки в колонию пищи - в частности, они опровергли давнее убеждение о том, что во время строительства...

 

Apple потребовала запрета на Galaxy Nexus в США

Apple потребовала запрета на Galaxy Nexus в США

Apple обратилась в суд в Калифорнии с требованием запретить в США продажу смартфона Galaxy Nexus. Производителя аппарата, компанию Samsung, Apple обвинила в нарушении четырех патентов. Ранее...

 

Panasonic анонсировала водонепроницаемый смартфон

Panasonic анонсировала водонепроницаемый смартфон

Panasonic представила мобильный аппарат Eluga с защитой от попадания внутрь корпуса пыли и влаги. Он поступит в продажу в апреле 2011 года и станет первым смартфоном компании, предназначенным не...

 

Сайт "Большой белый круг" заработал

Сайт "Большой белый круг" заработал

Вечером в четверг заработал сайт "Большой белый круг", посвященный акции оппозиции 26 февраля 2012 года в Москве. Планируется, что в этот день несколько десятков тысяч человек встанут живой цепью...

 

В токийском универмаге появятся роботы-манекены

В токийском универмаге появятся роботы-манекены

Токийский универмаг выставит у себя в витрине человекоподобного робота - джеминоида. Робот женского пола будет демонстрировать на себе одежду из ассортимента магазина. Geminoid-F умеет...

 

 

 

 

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

 

 

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

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

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

Февраль, 2012
Пн Вт Ср Чт Пт Сб Вск
  12345
6789101112
13141516171819
20212223242526
272829    

 

опрос  
 

 

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

 

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

 

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

 

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

 

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

 

 

 

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