Энциклопедия непознанного, интересного, нобъяснимого и загадочного
Главная старницаВидеоархив
Обратная связьSenav в twittereRSS 2.0
 
ПОПУЛЯРНЫЕ НОВОСТИ
» Уфолог: NASA и Россия скрывают контакты космонавтов МКС ...
» Катастрофические изменения в биосфере Земли обнаружили ...
» Всё вокруг говорит о том, что мы находимся в Матрице
» Как маскируются пришельцы, живущие среди людей
» НЛО Над Вашингтоном Вызвал Эвакуацию Белого Дома
» NASA: Cтена из раскаленной плазмы окружает нашу Солнечн ...
» Ученые считают, что Венеция в ближайшие годы уйдет под ...
» Самый опасный астероид Бенну движется в сторону Земли
» Нострадамус предсказал скорое объединение бывших советс ...
» Медики США впервые ввели пациента в состояние анабиоза
РУБРИКИ САЙТА
» Мифология
» Теория Заговора
» Свободная энергия
» Выдающиеся люди
» Планета Земля
» Тайны истории
» Изобретения
» Непознанное
» Космос
» НЛО
» Читальный зал
 

Гадание



ОНИ ЗА НАМИ СЛЕДЯТ Пожелания и отзывы
Мы рады Вас видеть на нашем проекте о непознанном и интересном SEnav.net!
В любое время Вы можете зарегистрироваться, и стать полноценным пользователем сайта.
Вы сможете оставлять комментарии к публикациям, голосовать в опросах, а самое главное ‒ присылать свои материалы! Надеемся, что Вы проведете время с пользой и удовольствием. Приятного отдыха и хорошего настроения!
 
Шекспир не Шекспир?
Опубликована 11 октября 2012,  в раздел » Видеоархив    
Шекспир не Шекспир?
Смотрели: 61243 человек  Оставили свои мысли: 1     
Прочитать статью целиком

Ученые вычислили сложность игры Scrabble
Опубликована 6 февраля 2012,  в раздел » Планета Земля   |  разместил: Lандыш
Ученые вычислили сложность игры Scrabble
Ученые вычислили сложность игры Scrabble ("Скрэббл"), известной в русском варианте как "Эрудит". Статья исследователей пока не принята к публикации в рецензируемом журнале, однако ее препринт доступен на сайте arXiv.org.

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

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

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

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

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





Источник — «Ученые вычислили сложность игры Scrabble»



Уважаемый посетитель, если захотите записать свою мысль на страницах SEnav.net - Вам необходимо будет зарегистрироваться, либо войти на сайт под своим именем.
 (голосов: 0)
Просмотров: 1294  |   | 

ЧИТАЙТЕ ТАКЖЕ:
  • Японские физики выяснили причины зависимости сверхпроводимости теллурида же ...
  • Нобелевский лауреат отменил черные дыры
  • Китайцы разобрались с расстановкой заправок для электромобилей
  • Внутри черных дыр существуют планеты?
  • Астрономы подтвердили, что ядро Млечного Пути сформировалось в результате с ...


  •    
     
      Информация  
     
       
     
    Посетители, находящиеся в группе Гости, не могут оставлять комментарии в данной новости.

     
       
         


    Написал: Кузьмич
    в теме: В Греции нашли возможную гробницу любовника Александра Македонского


    Написал: Кузьмич
    в теме: Зонд "Розетта" достиг орбиты Юпитер


    Написал: Кузьмич
    в теме: Зонд "Розетта" достиг орбиты Юпитер


    Написал: Fobbescerve
    в теме: Люди имеют внеземное происхождение


    Написал: Starking
    в теме: Люди имеют внеземное происхождение


    Написал: Кузьмич
    в теме: Дик Чейни предупредил об атаке пришельцами США импульсным оружием


    Написал: Кузьмич
    в теме: Бразилия займется производством комплексов «Игла-С»





    Если человечество погибнет, то от ...

    Инопланетяне всех перебьют
    Катастрофа - астероид, комета ...
    От эпидемий
    Мы сами себя уничтожим войнами
    Не знаю от чего, но точно помрем
    Все будет хорошо
    Декабрь 2019 (7)
    Ноябрь 2019 (10)
    Октябрь 2019 (12)
    Сентябрь 2019 (17)
    Август 2019 (20)
    Июль 2019 (15)


    Rambler's Top100
    Главная   •   Регистрация   •   Поиск по сайту   •   Карта сайта
    Копирование материалов со сылкой на источник поощряется положительной кармой!
      SEnav.net © 2007 – 2016
    Реклама на сайте