Изменения
Нет описания правки
# Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
# Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
# Напомним, что композиция отношений $R$ и $S$ это отношение $T=RS$, где $xTy$, если найдется $z$, такой что $xRz$ и $zRyzSy$. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивной их композиция?
# Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричной их композиция?
# Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$ тогда и только тогда, когда $xRy$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
# Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
# Постройте пример рефлексивного, симметричного, но не транзитивного отношения
# Транзитивный остов. Задано антисимметричное транзитивное отношение $R$ на $X$. Предложите полиномиальный алгоритм построения отношения $S$, такого что $S^+=R$, причем в $S$ содержится минимальное число пар элементов.
# В предыдущем задании требование транзитивности опустить нельзя. Задано антисимметричное отношение $R$ на $X$. Докажите, что если существует полиномиальный алгоритм построения отношения $S$, такого что $S \subset R$ и $S^+=R^+$, причем в $S$ содержится минимальное число пар элементов, то можно проверить, есть ли в графе гамильтонов цикл (цикл, проходящий по каждой вершине графа ровно один раз) за полиномиальное время.
# СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.
# Стрелка Пирcа (NOR) - булева функция $a \downarrow b = \neg (a \vee b)$. Выразите в явном виде ""и"", ""или"" и ""не"" через стрелку Пирса
# Штрих Шеффера (NAND) - булева функция $a \uparrow b = \neg (a \wedge b)$. Выразите в явном виде ""и"", ""или"" и ""не"" через штрих Шеффера
# Функция $f$ называется самодвойственной, если $f(\neg x_1, \ldots, \neg x_n) = \neg f(x_1, \ldots, x_n)$. Сколько существует самодвойственных функций от $n$ аргументов?
# Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что ""и"", ""или"", ""не"" - пороговые функции.
# Приведите пример непороговой функции
# Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{x\oplus y, x = y\}$?
# Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{x\to y, {\mathbf 0}\}$?
# Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{\langle xyz\rangle, \neg x\}$?
# Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$?
# Можно ли выразить ""и"" через ""или""?
# Можно ли выразить $\oplus$ через $=$?
# Медиана $2n+1$ булевского значения равна 1 если и только если среди ее аргументов больше единиц, чем нулей. Выразите медиану 5 через медиану 3
# Выразите медиану $2n+1$ через медиану 3
# Рассмотрим булеву функцию $f$. Обозначим как $N(f)$ число наборов аргументов, на которых $f$ равна 1. Например, $N(\vee) = 3$. Обозначим как $\Sigma(f)$ сумму всех наборов аргументов, на которых $f$ равна 1 как векторов. Например, $\Sigma(\vee) = (2, 2)$. Докажите, что если для пороговой функции $f$ и функции $g$ выполнено $N(f) = N(g)$ и $\Sigma(f) = \Sigma(g)$, то $f = g$
# КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
# Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.
# Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.
# Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.
# Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.
# Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?
# Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
# Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.
# Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
# Говорят, что формула находится в 2-КНФ (или форме Крома). если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Докажите, что если булеву функцию $f$ можно задать в форме Крома (в виде 2-КНФ), то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$
# Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$, то булеву функцию $f$ можно задать в форме Крома.
# Докажите, что если булеву функцию $f$ можно задать в форме Хорна, то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$
# Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$, то булеву функцию $f$ можно задать в форме Хорна
# Докажите, что $x_0\oplus x_1\oplus\ldots\oplus x_{2m} = \langle \neg x_0,s_1,s_2,\ldots,s_{2m}\rangle$, где $s_j=\langle x_0,x_j,x_{j+1},\ldots,x_{j+m-1},\neg x_{j+m},\neg x_{j+m+1},\ldots,\neg x_{j+2m-1}\rangle$, для удобства $x_{2m+k}$ обозначет то же, что и $x_k$ для $k \ge 1$.
# Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
# Докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
# Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
# Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$, используя не более 8 элементов. Элемент для "не" также считается.
# Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(n2^n)$ элементов.
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
# Докажите формулу разложения Шеннона по переменной $x$: $f(x, y_2, y_3, \ldots, y_n)=x\wedge f(1, y_2, y_3, \ldots, y_n)\vee \neg x\wedge f(0, y_2, y_3, \ldots, y_n)$
# Для булевых векторов $\alpha$ и $\beta$ обозначим как $\alpha\vee\beta$ побитовое $\vee$ этих векторов, аналогично введём $\alpha \wedge \beta$. Обозначим как $\succeq$ отношение доминирования на булевых векторах, $\alpha\succeq\beta$, если для всех $i$ выполнено $a_i\ge b_i$. Докажите, что $\alpha \wedge \beta$ удовлетворяет свойству, что $(\alpha \succeq\gamma)\wedge(\beta \succeq \gamma) \Leftrightarrow (\alpha\wedge\beta)\succeq \gamma$. Докажите, что $\alpha \vee \beta$ удовлетворяет свойству, что $\left((\gamma \succeq \alpha) \wedge (\gamma \succeq \beta)\right) \Leftrightarrow \gamma\succeq(\alpha\vee\beta)$.
# Докажите равенства $\alpha \wedge(\beta\vee\gamma)=(\alpha \wedge\beta)\vee(\alpha\wedge\gamma)$ и $\alpha \vee(\beta\wedge\gamma)=(\alpha \vee\beta)\wedge(\alpha\vee\gamma)$.
# Будем говорить, что булевый вектор $\alpha = (a_1, a_2, \ldots, a_n)$ префиксно мажорирует вектор $\beta = (b_1, b_2, \ldots, b_n)$, если для любого $k$ выполнено $a_1+\ldots+a_k \ge b_1+\ldots+b_k$ и писать $\alpha \ge_p \beta$. Докажите, что отношение $\ge_p$ является частичным порядком.
# Докажите. что $\alpha$ префиксно мажорирует $\beta$ тогда и только тогда, когда $\overline{\beta}$ префиксно мажорирует $\overline{\alpha}$ ($\overline{\alpha}$ означает побитовую инверсию).
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlywedge \beta$, такой что $((\alpha \ge_p \gamma) \wedge (\beta \ge_p \gamma)) \Leftrightarrow (\alpha\curlywedge\beta)\ge_p\gamma$. Предложите алгоритм построения такого вектора.
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlyvee \beta$, такой что $((\gamma \ge_p \alpha) \wedge (\gamma \ge_p \beta)) \Leftrightarrow \gamma\ge_p(\alpha\curlyvee\beta)$. Предложите алгоритм построения такого вектора.
# Докажите равенства $\alpha \curlywedge(\beta\curlyvee\gamma)=(\alpha \curlywedge\beta)\curlyvee(\alpha\curlywedge\gamma)$ и $\alpha \curlyvee(\beta\curlywedge\gamma)=(\alpha \curlyvee\beta)\curlywedge(\alpha\curlyvee\gamma)$.
# Будем называть функцию $f$ регулярной, если из $x \le_p y$ следует, что $f(x) \le f(y)$. Как связаны регулярные и монотонные функции?
# Докажите, что если функция $f$ является пороговой и $a_1 \ge a_2 \ge \ldots \ge a_n \ge 0$, то $f$ является регулярной.
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(3^n)$.
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(2^n 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}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для дешифратора.
# Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами''). Зафиксируем некоторые значения переменным. Тогда ''замкнутыми'' называются ребра, на которых записана 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)$ ребер.
# Будем интерпретировать битовые строки длины $n$ как целые числа с соответствующей двоичной записью. Заданы $n$-битные числа $v_0 < v_1 < \ldots < v_{m-1}$. Предложите алгоритм за $O(m)$, который по заданным числам и числу $j$ находит все такие пары индексов $i, k$, что $v_i \oplus 2^j = v_k$. Считайте, что операции с числами выполняются за $O(1)$.
# Приведите пример формулы, которая одновременно (а) равна тождественному нулю (б) находится в форме Хорна (в) находится в форме Крома (г) содержит хотя бы 3 переменные
# Докажите, что $(x \oplus 3x) \wedge ((x \oplus 3x) >> 1)=0$, где $>>$ означает битовый сдвиг вправо.
# Предложите алгоритм, который для заданного $d \ge 3$ вычисляет $x^y\bmod 2^d$ для заданных $x$ и $y$, где $x$ нечетен, используя $O(d)$ сложений и битовых операций и одно умножение на $y$.
# Предложите алгоритм, который по заданной своей таблицей истинности $n$-арной булевой функции строит за полином от $2^n$ монотонную булеву функцию, которая одновременно (а) мажорирует заданную на каждом входном наборе (б) имеет минимальное число входных наборов, на которых она равна 1.
# Формулы с кванторами. Рассмотрим формулу с кванторами $Qx_1Qx_2\ldots Qx_n f(x_1, \ldots, x_n)$, где $Q$ может быть квантором "существует" или "для любого". Докажите, что если если $f(x_1,\ldots,x_n)$ имеет ровно $k$ удовлетворяющих её назначений переменных, то существует ровно $k$ (из $2^n$ возможных) формул с кванторами в указанной форме, которые являются истинными.
# Дана формула в КНФ. Можно каждое вхождение переменной x заменить на её отрицание. Необходимо добиться, чтобы формула после этих преобразований оказалась в форме Хорна. Предложите алгоритм, который сводит эту задачу к задаче 2SAT.
# Свести 3SAT к проверке существования удовлетворяющего назначения для формулы, которая является конъюнкцией клозов, каждый из которых является либо клозом Хорна, либо клозом Крома
# Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
# Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
# Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
# Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды (коды, использующие алфавит не из двух символов, а из $k \ge 2$).
# Обобщите неравенство Крафта-Макмиллана на $k$-ичные коды
# Укажите, как построить дерево Хаффмана за $O(n)$, если символы уже отсортированы по частоте
# Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более $L$ бит
# Предложите способ хранения информации об оптимальном префиксном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
# Можно ли разработать алгоритм, который сжимает любой файл не короче заданной величины $N$ хотя бы на 1 бит?
# Приведите пример однозначно декодируемого кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным
# Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
# Пусть заданы пары $(u_i, v_i)$. Предложите полиномиальный алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.
# Докажите, что если в коде Хаффмана для некоторой строки $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц, то для многочлена от двух переменных $f(x, y) = \sum_{i=1}^n x^{u_i}y^{v_i}$ выполнено $f(x, y) - 1 = (x + y - 1) g(x, y)$ для некоторого многочлена $g(x, y)$.
# Изучите коды Шеннона-Фано https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D0%B0_%E2%80%94_%D0%A4%D0%B0%D0%BD%D0%BE. Приведите пример текста, для которого код Шеннона-Фано хуже кода Хаффмана.
# Обобщите коды Шеннона-Фано на $k$-ичные коды.
# Предложите алгоритм проверки того, что заданный двоичный код является однозначно декодируемым. Алгоритм должен работать за полином от суммы длин кодовых слов.
# Верно ли, что если длины кодовых слов некоторого кода удовлетворяют неравенству Крафта-МакМиллана, то это код является однозначно декодируемым?
# При арифметическом кодировании может повезти и у достаточно длинной строки код получится коротким, хотя длина строки большая, и оценка на длину кода тоже большая. Приведите пример такой строки.
# Для предыдущего задания приведите пример бесконечной последовательности строк возрастающей длины, для которых проявляется описанный эффект.
# При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
# Пусть вероятности символов упорядочены по убыванию ($p_1 \ge p_2 \ge \ldots \ge p_n$) и являются дробями, у которых знаменатель - степень двойки. Что можно сказать про арифметическое кодирование в этом случае?
# Проанализируйте время работы алгоритма арифметического кодирования (с учетом длинной арифметики).
# Троичное арифметическое кодирование. Пусть при арифметичском кодировании мы используем в качестве знаменателя не $2^q$, а $3^q$, а числитель записываем как троичное число, дополненное ведущими нулями до длины $q$. Затем запишем числитель в двоичной записи, а ведущие нули заменим на нули в двоичной записи. Приведите пример строки, когда описанный метод через степени тройки будет лучше классического арифметического кодирования.
# Приведите пример строки, когда такой метод будет хуже классического арифметического кодирования.
# Докажите, что для любого $c > 1$ существует строка, что арифметическое кодирование в $c$ раз лучше кода Хаффмана.
# Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в среднем тратит в $c$ раз меньше бит на символ строки, чем код Хаффмана.
# Докажите, что при оптимальном кодировании с помощью LZ не выгодно делать повтор блока, который можно увеличить вправо
# Разработайте алгоритм оптимального кодирования текста с помощью LZ, если на символ уходит $c$ бит, а на блок повтора $d$ бит
# Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
# Предложите алгоритм декодирования кода Барроуза-Уиллера.
# Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
# Предложите реализацию преобразования Move to Front за $O(n \log n)$.
# Предложите реализацию преобразования Move to Front за $O(n)$.
