Top

Насколько сложен Эрудит

Математиков заинтересовало, насколько  сложна игра Эрудит, в англоязычных странах называемая Скрэббл.

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

Конечно, ученые пошли не простым путем, определяя, сложна игра или нет, они решили определить насколько сложен алгоритм наилучшей стратегии.

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

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

© lenta.ru

Другие статьи рубрики "Исследования"

Комментарии



Есть что сказать?

Вы должны войти войти чтобы оставить комментарий.


Bottom