Изменения
Нет описания правки
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
# Мультиплексором называется схема, которая имеет $2^n+n$ входов и один выход. Обозначим входы как $x_0, x_1, \ldots, x_{2^n-1}, y_0, y_1, \ldots, y_{n-1}$. На выход подается то же, что подается на вход $x_i$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для мультиплексора.
# Дешифратором называется схема, которая имеет $n+1$ входов и $2^n$ выходов. Обозначим входы как $y_0, y_1, \ldots, y_{n-1}, x$, а выходы как $z_0, z_1, \ldots, z_{2^n-1}$. На все выходы подается 0, а на выход $z_i$ то же, что подается на вход $x$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для дешифратора.
# Игра "два шага вперед, один назад". Задана булева функция от $n$ аргументов $f(x_1, \ldots, x_n)$. Играют два игрока: 0 и 1. Игроки делают ходы по очереди. Для хода используется вспомогательное значение $m$, исходно равное 0, кроме того исходно все значения переменных не определены. Ход заключается в следующем. Игрок либо увеличивает $m$ на 2, либо уменьшает на 1. После этого действия значение $m$ должно удовлетворять неравенству $1 \le m \le n$. Затем, если значение $x_m$ не определено, то игрок присваивает переменной $x_m$ значение на свое усмотрение. Если же значение $x_m$ определено, то оно меняется на противоположное. Игра заканчивается, когда все значения определены. Если значение функции $f$ на получившемся наборе переменных равно 1, то выигрывает 1, иначе выигрывает 0. Проанализируйте описанную игру для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ лексикографически строго меньше строки $x_nx_{n-1}\ldots x_1$.
# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)=x_1\oplus x_2\oplus \ldots\oplus x_n$.
# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.
# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.дешифратора.
