Изменения
Нет описания правки
# Дешифратором называется схема, которая имеет $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}$. Постройте схему линейного размера для дешифратора.
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
# На одном китайском заводе в матричном умножителе случайно использовали элементы "или" вместо "и". Можно ли из получившихся значений получить произведение исходных чисел (доступа к входам нет, есть только доступ к $n\times 2n$ выходам матричного псевдоумножителя).
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
# Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами''). Зафиксируем некоторые значения переменным. Тогда ''замкнутыми'' называются ребра, на которых записана 1, ребра, на которых записан 0, называются ''разомкнутыми''. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".
# Постройте контактную схему для функции "xor".
# Постройте контактную схему для функции медиана трех.
# Докажите, что любую булеву функцию можно представить контактной схемой.
# Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
# Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
# Постройте контактную схему, в которой для каждого из $2^n$ наборов конъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта конъюнкция, используя $O(2^n)$ ребер.
# Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
