Алгоритмы: построение и анализ

Упражнение 1:

Номер 1

Какое утверждение верно для игры Ним с начальной позицией {2,1,1}?(каждая цифра означает число камней в соответствующей куче)

Ответ:

(1) первый игрок может гарантировать себе выйгрыш

(2) второй игрок может гарантировать себе выйгрыш

(3) может случиться ничья

Номер 2

Какое утверждение верно для игры Ним с начальной позицией {2,2,1}?(каждая цифра означает число камней в соответствующей куче)

Ответ:

(1) первый игрок может гарантировать себе выйгрыш

(2) второй игрок может гарантировать себе выйгрыш

(3) может случиться ничья

Номер 3

Какое утверждение верно для игры Ним с начальной позицией {2,2,3}?(каждая цифра означает число камней в соответствующей куче)

Ответ:

(1) первый игрок может гарантировать себе выйгрыш

(2) второй игрок может гарантировать себе выйгрыш

(3) может случиться ничья

Упражнение 2:

Номер 1

Какая из следующих игр Ним является игрой с симетричной стратегией?

Ответ:

(1) {1,2,3,2,1}

(2) {4,2,1,4,1,2}

(3) {4,3,4,2}

Номер 2

Сколько вершин в графе иры Ним для начальной позиции {2,2}? (начальную {2,2} и конечную {0,0} тоже считать)

Ответ:

(1) 6

(2) 4

(3) 5

Номер 3

Нулевым позициям в графе игры Ним соответствуют

Ответ:

(1) позичии в которых первый игрок может гарантировать себе выйгрыш

(2) позичии в которых второй игрок может гарантировать себе выйгрыш

(3) позиции в которых в одной из куч 0 камней

Упражнение 3:

Номер 1

Игра называется конечной, если:

Ответ:

(1) из любой позиции можно сделать не более чем конечное число ходов

(2) первый игрок может гарантировать конечность игры

(3) в любой момент один из игроков может сдаться и тем самым закончить игру

Номер 2

Игра называется нейтральной, если:

Ответ:

(1) в ней возможна ничья

(2) из любой позиции множество ходов первого и второго игроков совпадают

(3) в ее графе нет циклов

Номер 3

Какая из этих игр является конечной?

Ответ:

(1) шахматы

(2) крестики-нолики

(3) шашки

Упражнение 4:

Номер 1

Для игры Ним {7,2,1} нимбером является:

Ответ:

(1) 110

(2) 100

(3) 111

(4) 1010

Номер 2

Для игры Ним {3,3,2,1} нимбером является:

Ответ:

(1) 10

(2) 110

(3) 101

Номер 3

Для игры Ним {3,3,2,7} нимбером является:

Ответ:

(1) 101

(2) 111

(3) 110

Упражнение 5:

Номер 1

Какое утвеждение верно?

Ответ:

(1) в игре Ним при правильной игре обоих игроков выигрывает второй игрок тогда и только тогда, когда ее нимбер оканчивается на ноль

(2) в игре Ним при правильной игре обоих игроков проигрывает второй игрок тогда и только тогда, когда ее нимбер равен нулю

(3) в игре Ним при правильной игре обоих игроков выигрывает второй игрок тогда и только тогда, когда ее нимбер равен нулю

Номер 2

Какие утверждения верны?

Ответ:

(1) если нимбер игры нулевой, то на следующий ход он обязательно станет ненулевым

(2) если нимбер игры не нулевой, то сделав один ход его всегда можно сделать нулевым

(3) если нимбер игры не нулевой, то на следующий ход он обязательно станет нулевым

(4) если нимбер нулевой, то при правильной игре выигрывает второй игрок

Номер 3

Как определяется нимбер произвольной игры  A?

Ответ:

(1)

(2)

(3)

Упражнение 6:

Номер 1

Чему равен нимбер игры  ? (игра "ромашка" с начальной позицией 4 липестка вряд)

Ответ:

(1) 1

(2) 2

(3) 3

(4) 0

Номер 2

Чему равен нимбер игры  ?(игра "ромашка" с начальной позицией 3 лепестка вряд)

Ответ:

(1) 0

(2) 1

(3) 2

(4) 3

Номер 3

Что является аналогом нимберов для цветных игр?

Ответ:

(1) числа Конвея

(2) цветные нимберы

(3) числа Хакенбуша

Упражнение 7:

Номер 1

Пусть два многочлена совпадают в n точках, при каком условии можно утверждать, что они равны друг другу?

Ответ:

(1) их степени не превосходят n

(2) их степени не превосходят n+1

(3) их степени не превосходят n-1

Номер 2

В скольких точках должны совпадать два многочлена степени n, чтобы можно было утверждать что они совпадают всюду?

Ответ:

(1) в n+1 точке

(2) в n точках

(3) в n-1 точке

Номер 3

Интерполяционный многочлен Лагранжа это

Ответ:

(1) многочлен принимающий заданные значения в заданных точках

(2) многочлен принимающий нулевые значения в заданных точках

(3) многочлен который принимающий нулевые значения во всех кроме одной заданной точки, а в этой точке равен единице

Упражнение 8:

Номер 1

Чему равно ?

Ответ:

(1) 0

(2) -1

(3) 1

(4) это выражание неопредлено

Номер 2

Чему равно ?

Ответ:

(1)

(2)

(3)

Номер 3

Что такое примитивный корень степени n из 1?

Ответ:

(1) это такой корень, что среди его целых степеней есть все остальные корни степени n

(2) это такой корень, что среди его степеней есть все остальные корни степени n

(3) это такой корень, что среди его целых степеней есть все остальные корни

Упражнение 9:

Номер 1

Чему равна сумма всех корней степени n из 1?

Ответ:

(1) n

(2) 0

(3) 1

Номер 2

Чему равны  в дискретном преобразовании Фурье многочлена

Ответ:

(1)

(2)

(3)

Номер 3

Как выражаются  в обратном дискретном преобразовании Фурье?

Ответ:

(1)

(2)

(3)

Упражнение 10:

Номер 1

Квадраты корней степени 8 из 1 это в точности ...

Ответ:

(1) все корни степни 4 из 1

(2) все корни степни 8 из 1

(3) первые 4 корня степени 8 из 1

Номер 2

Квадраты корней степени 10 из 1 это в точности ...

Ответ:

(1) все корни степни 5 из 1

(2) все корни степни 10 из 1

(3) первые 5 корней степени 10 из 1

Номер 3

Квадраты корней степени 9 из 1 это в точности ...

Ответ:

(1) все корни степни 9 из 1

(2) все корни степни 5 из 1

(3) все корни степни 3 из 1

Упражнение 11:

Номер 1

Чему равно время работы врямя работы алгоритма дискретного преобразования Фурье для многочлена степени  n?

Ответ:

(1) O(n^2)

(2) O(n*log n)

(3) O(n)

Номер 2

Чему равно время работы  алгоритма обратного дискретного преобразования Фурье для многочлена степени  n?

Ответ:

(1) O(n^2)

(2) O(n)

(3) O(n*log n)

Номер 3

Какая абривеатура означает обратное дискретное преобразование Фурье?

Ответ:

(1)

(2)

(3)

(4)

Упражнение 12:

Номер 1

Какие утверждения верны для конечного поля?

Ответ:

(1) для любого элемента есть обратный

(2) любой элемент в какой-то степени равен любому другому элементу поля

(3) любой элемент является корнем из единицы

Номер 2

Сколько примитивных корней степени 5 из 1?

Ответ:

(1) 4

(2) 5

(3) 1

Номер 3

Чему равна сумма всех примитивных корней степени 5 из 1?

Ответ:

(1) 0

(2) 1

(3) -1

Алгоритмы: построение и анализ - тест 11