База ответов ИНТУИТ

Инструменты, алгоритмы и структуры данных

<<- Назад к вопросам

Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Рассмотрим дерево конкретной игры, в узлах которого записываются оценки позиций. Дерево зададим скобочной записью:
(((5, 3) (6, -1, 8))((10, 6, 2) (-2, -4, -7)) )
Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. Каково значение цены игры для этого дерева?

(Отметьте один правильный вариант ответа.)

Варианты ответа
3
5
10
-1
2(Верный ответ)
-7
Похожие вопросы
Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Зададим дерево конкретной игры, в узлах которого записаны оценки позиций. Дерево зададим скобочной записью:
( ((5, 3) (6, -1, 8)) ((10, 6, 2) (-2, -4, -7)) )
Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. При вычислении цены игры применяется альфа-бета стратегия отсечения вариантов. Сколько вариантов (в данном случае листьев дерева) будет отсечено при применении этой стратегии?
Пусть Т - полное бинарное дерево (каждый узел не являющийся листом дерева имеет двух потомков) число листьев в котором равно 2^m. Для обхода дерева применяется инфиксная процедура обхода (обойти левое дерево, обойти корень, обойти правое дерево). Каким по счету будет посещен корень дерева, если счет узлов начинается с 1)?
Для некоторых алгоритмов получены оценки сложности. Из приведенных формул укажите две, задающие эквивалентные оценки?
Хеш-функция f(k) отображает множество ключей в целочисленный интервал: K -> [a, b]. Пусть ключами являются имена, которые должны отображаться в интервал [0, 9]. В качестве хеш-функции выберем функцию, которая вычисляет сумму позиций в алфавите кириллицы первой и последней буквы имени, прибавляет длину имени и вычисляет остаток от деления на 10 (взятие по модулю от длины интервала). Для имени Яша эта функция выдаст значение 7. Каково число коллизий возникнет при применении этой функции для следующих 10 имен: Анна, Инна, Нина, Ольга, Екатерина, Владимир, Владислав, Виктор, Михаил, Яков?
Рассмотрим рекурсивное определение понятия "идентификатор":
\text{идентификатор }\triangleq\text{ буква | идентификатор буква | идентификатор цифра}
Пусть алфавит языка содержит две буквы - x и y и одну цифру -1. Индуцируя построение идентификаторов в стиле неподвижной точки, на нулевом уровне можно построить два идентификатора в соответствии с нерекурсивной частью определения, а сколько идентификаторов можно построить, принадлежащих уровню 2:
Каково число возможных позиций курсора для пустого списка?
Рассмотрим язык программирования с двумя операторами - присваивания и цикла. Присваивание рассматривается в классическом варианте variable := expression и считается терминальным, не определяемым далее понятием. Грамматика языка такова:
\text{Оператор }\triangleq\text{ Присваивание | Цикл}\\ \text{Цикл }\triangleq \text{ until (Условие) Оператор}
Какие утверждения являются справедливыми относительно правил этой грамматики?
Рассмотрим контейнерный класс, в котором метод вставки элементов put имеет следующую сигнатуру: put (key:STRING; i: G), где key - ключ элемента, i - сам элемент. Какие постусловия должны включаться для этого метода?
Рекурсивное определение напоминает фокус. Рассмотрим рекурсивное определение известной в математике функции:
F(n) = n – 10,\text{ если }n > 100\\ F(n) = F(F(n + 11),\text{ если }n <= 100
Совершенно очевидно, какие значения принимает эта функция при n> 100. А каковы ее значения при n< 101? Оказывается, для таких n функция имеет одно и то же значение. Какое?
Для рекурсивно определенной функции можно дать другое определение, не использующее рекурсию, основанное на подходе "снизу -вверх". Для простоты будем полагать, что рассматривается функция одного целочисленного аргумента. Какие утверждения справедливы для такого подхода?