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

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

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

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

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

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