244
правки
Изменения
Нет описания правки
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(3^n)$.
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(2^n n)$.
# Будем кодировать k, g и p двумя булевыми значениями, 00 для k, 11 для g и 01 или 10 для p. Разработайте в явном виде схему для композиции действия на перенос. У нее должно быть 4 булевых входа (два входных действия) и 2 булевых выхода - действие-композиция. Используйте любой удобный базис.
# Докажите, что для суммы $n$-битных чисел не существует схемы глубиной $O(1)$.
# Докажите, что для произведения $n$-битных чисел не существует схемы глубиной $O(1)$.
# Докажите, что не существует схемы глубиной $O(1)$, которая проверяет, будет ли переполнение, при суммировании двух $n$-битных чисел.
# Докажите, что для функции ""большинство из $2n+1$"" существует схема из функциональных элементов глубины $O(\log 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 = 2^m - 1$, задано $n$ булевых входов $x_1, x_2, \ldots, x_n$. Постройте схему размера $O(n)$ и глубины $O(m)$, которая по этим входам выдает $m$ выходов $y_0, y_1, \ldots, y_{m-1}$, которые задают двоичное число $k = \overline{y_{m-1}y_{m-2}\ldots y_1 y_0}$, такое что $k = 0$, если все входы равны $0$, иначе $k = \max\{j\,|\,x_j = 1\}$.
# Постройте схему, которая имеет $n$ входов $x_1, x_2, \ldots, x_n$ и $n$ выходов $y_1, \ldots, y_n$, где $y_k = x_1 \wedge x_2 \wedge \ldots \wedge x_{k-1}\wedge x_{k+1}\wedge \ldots \wedge x_n$ ($k$-й выход равен конъюнкции всех входов, кроме $k$-го). Схема должна использовать базис $\{\wedge, \vee, \neg\}$ и содержать не более $3n$ функциональных элементов.
# Предложите схему для сравнения целых чисел без знака глубины $O(\log n)$.
# Предложите схему для сравнения целых чисел со знаком в дополнительном коде глубины $O(\log n)$.
# В матричном умножителе вместо элементов ""и"" поставили элементы ""или"". Можно ли получить с помощью этого умножителя произведение чисел, используя $O(n)$ дополнительных элементов? Вы можете добавить эти элементы в произвольные места в схеме для умножителя.
# Будем интерпретировать битовые строки длины $n$ как целые числа с соответствующей двоичной записью. Заданы $n$-битные числа $v_0 < v_1 < \ldots < v_{m-1}$. Предложите алгоритм за $O(m)$, который по заданным числам и числу $j$ находит все такие пары индексов $i, k$, что $v_i \oplus 2^j = v_k$. Считайте, что операции с числами выполняются за $O(1)$.
# Докажите, что $(x \oplus 3x) \wedge ((x \oplus 3x) >> 1)=0$, где $>>$ означает битовый сдвиг вправо.
# Предложите алгоритм, который для заданного $d \ge 3$ вычисляет $x^y\bmod 2^d$ для заданных $x$ и $y$, где $x$ нечетен, используя $O(d)$ сложений и битовых операций и одно умножение на $y$.
# Для каких бинарных коммутативных операций $\circ$ выполнен распределительный закон для медианы $w\circ\langle xyz \rangle = \langle x\circ w, y \circ w, z \circ w\rangle$?
# Можно ли выразить медиану трех через медиану пяти?
# Будем называть длиной ДНФ количество вхождений перменных в нее. Например, $(x\wedge y)\vee (\neg x \wedge z)$ имеет длину 4. Постройте ДНФ минимальной длины для функции $x_1 \oplus x_2 \oplus \ldots \oplus x_n$.
