Список заданий по ДМ 2023 осень

1. Постройте пример рефлексивного, симметричного, но не транзитивного отношения
2. Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
3. Постройте пример отношения, которое не симметрично и не антисимметрично
4. Постройте пример отношения, которое симметрично и антисимметрично
5. Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
6. Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
7. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
8. Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
9. Композиция отношений $R$ и $S$ это отношение $T=RS$, где $xTy$, если найдется $z$, такой что $xRz$ и $zSy$. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивной их композиция?
10. Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричной их композиция?
11. Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
12. Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
13. Докажите, что $(RS)^{-1} = S^{-1}R^{-1}$.
14. Композицией функций $f : A \to B$ и $g : B \to C$ называется $g \circ f$, что $(g \circ f)(x) = g(f(x))$. Докажите, если $f$ и $g$ инъективны/сюръективны/биективны, то то же свойство верно и для их композиции.
15. Отношение $R \subseteq A \times B$ называется функциональным, если $R^{-1} R \subseteq I$. Правда ли, что если $R \subseteq A \times B$ и $S \subseteq B \times C$ функциональны, то $RS \subseteq A \times C$ функционально?
16. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $a + d = b + c$ на ${\mathbb N} \times {\mathbb N}$ отношением эквивалентности?
17. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
18. Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?
19. Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?
20. Для решения этой серии вам необходимо самостоятельно изучить понятие СДНФ. В этой задаче вам необходимо построить СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.
21. Стрелка Пирcа (NOR) - булева функция $a \downarrow b = \neg (a \vee b)$. Выразите в явном виде ""и"", ""или"" и ""не"" через стрелку Пирса
22. Штрих Шеффера (NAND) - булева функция $a \uparrow b = \neg (a \wedge b)$. Выразите в явном виде ""и"", ""или"" и ""не"" через штрих Шеффера
23. Функция $f$ называется самодвойственной, если $f(\neg x_1, \ldots, \neg x_n) = \neg f(x_1, \ldots, x_n)$. Сколько существует самодвойственных функций от $n$ аргументов?
24. Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{x\oplus y, x = y\}$?
25. Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{x\to y, {\mathbf 0}\}$?
26. Медиана $\langle xyz\rangle$, также известная как функция большинства или функция голосования, равна 1, если из трех ее аргументов хотя бы два равны 1. Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{\langle xyz\rangle, \neg x\}$?
27. Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$?
28. Можно ли выразить ""и"" через ""или""?
29. Можно ли выразить $\oplus$ через $=$?
30. Медиана $2n+1$ булевского значения равна 1 если и только если среди аргументов больше 1. Выразите медиану 5 через медиану 3
31. Выразите медиану $2n+1$ через медиану 3
32. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что ""и"", ""или"", ""не"" - пороговые функции.
33. Приведите пример непороговой функции. Поясните, почему из предыдущего номера не следует, что любая функция является пороговой.
34. Рассмотрим булеву функцию $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$
35. КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
36. Расссмотрим функцию $f$, построим ее СДНФ. Заменим в этой формуле все $\vee$ на $\wedge$ и наоборот. Получится СКНФ некоторой функции $g$. Для каких функций $f$ выполнено $f=g$?
37. Для каждого класса Поста проверьте, существует ли функция, которая лежит в этом классе Поста, но не лежит ни в одном из четырех других.
38. Для каждого класса Поста проверьте, существует ли функция, которая не лежит в этом классе Поста, но лежит в четырех остальных.
39. Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.
40. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.
41. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.
42. Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.
43. Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?
44. Какие симметричные булевы функции являются пороговыми?
45. Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
46. Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.
47. Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
48. Говорят, что формула находится в 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$
49. Докажите, что если выполнено следствие: $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$ можно задать в форме Крома.
50. Докажите, что если булеву функцию $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$
51. Докажите, что если выполнено следствие: $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$ можно задать в форме Хорна
52. Докажите, что $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$.
53. Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
54. Изучите и докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
55. Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
56. Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$, используя не более 8 элементов. Элемент для ""не"" также считается.
57. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.
58. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(n2^n)$ элементов.
59. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
60. Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
61. Докажите формулу разложения Шеннона по переменной $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)$
62. Для булевых векторов $\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)$.
63. Докажите равенства $\alpha \wedge(\beta\vee\gamma)=(\alpha \wedge\beta)\vee(\alpha\wedge\gamma)$ и $\alpha \vee(\beta\wedge\gamma)=(\alpha \vee\beta)\wedge(\alpha\vee\gamma)$.
64. Будем говорить, что булевый вектор $\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$ является частичным порядком.
65. Докажите. что $\alpha$ префиксно мажорирует $\beta$ тогда и только тогда, когда $\overline{\beta}$ префиксно мажорирует $\overline{\alpha}$ ($\overline{\alpha}$ означает побитовую инверсию).
66. Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlywedge \beta$, такой что $((\alpha \ge_p \gamma) \wedge (\beta \ge_p \gamma)) \Leftrightarrow (\alpha\curlywedge\beta)\ge_p\gamma$. Предложите алгоритм построения такого вектора.
67. Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlyvee \beta$, такой что $((\gamma \ge_p \alpha) \wedge (\gamma \ge_p \beta)) \Leftrightarrow \gamma\ge_p(\alpha\curlyvee\beta)$. Предложите алгоритм построения такого вектора.
68. Докажите равенства $\alpha \curlywedge(\beta\curlyvee\gamma)=(\alpha \curlywedge\beta)\curlyvee(\alpha\curlywedge\gamma)$ и $\alpha \curlyvee(\beta\curlywedge\gamma)=(\alpha \curlyvee\beta)\curlywedge(\alpha\curlyvee\gamma)$.
69. Будем называть функцию $f$ регулярной, если из $x \le_p y$ следует, что $f(x) \le f(y)$. Как связаны регулярные и монотонные функции?
70. Докажите, что если функция $f$ является пороговой и $a_1 \ge a_2 \ge \ldots \ge a_n \ge 0$, то $f$ является регулярной.
71. Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(3^n)$.
72. Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(2^n n)$.
73. Будем кодировать k, g и p двумя булевыми значениями, 00 для k, 11 для g и 01 или 10 для p. Разработайте в явном виде схему для композиции действия на перенос. У нее должно быть 4 булевых входа (два входных действия) и 2 булевых выхода - действие-композиция. Используйте любой удобный базис.
74. Докажите, что для суммы $n$-битных чисел не существует схемы глубиной $O(1)$.
75. Докажите, что для произведения $n$-битных чисел не существует схемы глубиной $O(1)$.
76. Докажите, что не существует схемы глубиной $O(1)$, которая проверяет, будет ли переполнение, при суммировании двух $n$-битных чисел.
77. Докажите, что для функции ""большинство из $2n+1$"" существует схема из функциональных элементов глубины $O(\log n)$
78. Мультиплексором называется схема, которая имеет $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}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для мультиплексора.
79. Дешифратором называется схема, которая имеет $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}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для дешифратора.
80. Пусть $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\}$.
81. Постройте схему, которая имеет $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$ функциональных элементов.
82. Предложите схему для сравнения целых чисел без знака глубины $\log n$.
83. Предложите схему для сравнения целых чисел со знаком в дополнительном коде глубины $\log n$.
84. В матричном умножителе вместо элементов ""и"" поставили элементы ""или"". Можно ли получить с помощью этого умножителя произведение чисел, используя $O(n)$ дополнительных элементов? Вы можете добавить эти элементы в произвольные места в схеме для умножителя.
85. Будем интерпретировать битовые строки длины $n$ как целые числа с соответствующей двоичной записью. Заданы $n$-битные числа $v_0 < v_1 < \ldots < v_{m-1}$. Предложите алгоритм за $O(m)$, который по заданным числам и числу $j$ находит все такие пары индексов $i, k$, что $v_i \oplus 2^j = v_k$. Считайте, что операции с числами выполняются за $O(1)$.
86. Докажите, что $(x \oplus 3x) \wedge ((x \oplus 3x) >> 1)=0$, где $>>$ означает битовый сдвиг вправо.
87. Предложите алгоритм, который для заданного $d \ge 3$ вычисляет $x^y\bmod 2^d$ для заданных $x$ и $y$, где $x$ нечетен, используя $O(d)$ сложений и битовых операций и одно умножение на $y$.
88. Для каких бинарных коммутативных операций $\circ$ выполнен распределительный закон для медианы $w\circ\langle xyz \rangle = \langle x\circ w, y \circ w, z \circ w\rangle$?
89. Можно ли выразить медиану трех через медиану пяти?
90. Будем называть длиной ДНФ количество вхождений перменных в нее. Например, $(x\wedge y)\vee (\neg x \wedge z)$ имеет длину 4. Постройте ДНФ минимальной длины для функции $x_1 \oplus x_2 \oplus \ldots \oplus x_n$.
91. Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций ""и"", ""или"" и ""не"".
92. Постройте контактную схему для функции ""xor"".
93. Постройте контактную схему для функции медиана трех.
94. Докажите, что любую булеву функцию можно представить контактной схемой.
95. Постройте контактную схему ""xor от $n$ переменных"", содержащую $O(n)$ ребер.
96. Постройте контактную схему ""большинство из $2n+1$ переменных"", содержащую $O(n^2)$ ребер.
97. Постройте контактную схему, в которой для каждого из $2^n$ наборов дизъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта дизъюнкция, используя $O(2^n)$ ребер.
98. Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
99. Приведите пример формулы, которая одновременно (а) равна тождественному нулю (б) находится в форме Хорна (в) находится в форме Крома (г) содержит хотя бы 3 переменные
100. Предложите алгоритм, который по заданной своей таблицей истинности $n$-арной булевой функции строит за полином от $2^n$ монотонную булеву функцию, которая одновременно (а) мажорирует заданную на каждом входном наборе (б) имеет минимальное число входных наборов, на которых она равна 1.
101. Формулы с кванторами. Рассмотрим формулу с кванторами $Qx_1Qx_2\ldots Qx_n f(x_1, \ldots, x_n)$, где $Q$ может быть квантором ""существует"" или ""для любого"". Докажите, что если если $f(x_1,\ldots,x_n)$ имеет ровно $k$ удовлетворяющих её назначений переменных, то существует ровно $k$ (из $2^n$ возможных) формул с кванторами в указанной форме, которые являются истинными.
102. Дана формула в КНФ. Можно каждое вхождение переменной x заменить на её отрицание. Необходимо добиться, чтобы формула после этих преобразований оказалась в форме Хорна. Предложите алгоритм, который сводит эту задачу к задаче 2SAT.
103. Свести 3SAT к проверке существования удовлетворяющего назначения для формулы, которая является конъюнкцией клозов, каждый из которых является либо клозом Хорна, либо клозом Крома
104. Игра ""два шага вперед, один назад"". Задана булева функция от $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$.
105. Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)=x_1\oplus x_2\oplus \ldots\oplus x_n$.
106. Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.
107. Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.дешифратора.
108. Найдите в интернете частоты букв в английских текстах и постройте код Хаффмана для этих частот. Придумайте, как продемонстрировать результат и сравните получившийся код с кодом постоянной длины.
109. Найдите в интернете частоты букв в русских текстах и постройте код Хаффмана для этих частот. Придумайте, как продемонстрировать результат и сравните получившийся код с кодом постоянной длины.
110. Возьмите большой несжатый файл (например, изображение .bmp) и посчитайте частоты всех возможных 256 байтов в этом файле. Постройте код Хаффмана для этих частот
111. Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
112. Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
113. Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
114. Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды (коды, использующие алфавит не из двух символов, а из $k \ge 2$). Докажите корректность.
115. Укажите, как построить дерево Хаффмана за $O(n)$, если символы уже отсортированы по частоте
116. Предложите способ хранения информации об оптимальном префиксном бинарном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
117. Приведите пример однозначно декодируемого бинарного кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным (после разворота всех слов он тоже не становится префиксным)
118. Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
119. Дан набор частот $p_1, p_2, \ldots, p_n$, $p_i \ge 0$, $\sum\limits_i p_i = 1$. Докажите, что существует префиксный код, где длина $i$-го кодового слова равна $\lceil \log_2 (\frac 1{p_i}) \rceil$.
120. Обозначим $H(p_1, \ldots, p_n) = \sum\limits_{i=1}^n p_i \log_2 ( \frac 1{p_i} )$. Докажите, что длина кода из прошлой задачи (в этом контексте ее стоит понимать, как ""среднее количество бит, затраченное на случайный символ"") не превосходит $H(p_1, \ldots, p_n) + 1$.
121. Пусть заданы пары $(u_i, v_i)$. Предложите полиномиальный алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.
122. Докажите, что если в коде Хаффмана для некоторой строки $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)$.
123. Изучите коды Шеннона-Фано 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. Приведите пример текста, для которого код Шеннона-Фано хуже кода Хаффмана.
124. Предложите алгоритм проверки того, что заданный двоичный код является однозначно декодируемым. Алгоритм должен работать за полином от суммы длин кодовых слов.
125. Обобщите алгоритм Хаффмана для ""сжатых"" алфавитов, заданных в следующем виде: дано $n$ пар $(k_i, f_i)$, означающих, что в алфавите присутствует $k_i$ символов с частотой $f_i$. Придумайте, как за полиномиальное время найти длину кода Хаффмана для такого алфавита и оцените время работы алгоритма.
126. Верно ли, что если длины кодовых слов некоторого кода удовлетворяют неравенству Крафта-МакМиллана, то это код является однозначно декодируемым?
127. Приведите пример префиксного кода с длинами кодовых слов $1, 2, 3, \ldots, n-1, n-1$.
128. Приведите пример префиксного кода с длинами кодовых слов $1, 3, 3, 5, 5, 5, 5, \ldots$ (слов длины $2i+1$ будет $2^i$ для $i$ от 1 до $k$).
129. Петя утверждает, что он разработал однозначно декодируемый код $c$, в котором для каждой строки $x$ длина её кода $c(x)$ не больше длины $x$, а хотя бы для одной длина кода строго меньше. Прокомментируйте результат Пети.
130. Вася утверждает, что он разработал однозначно декодируемый код $c$, в котором для некоторого $n$ хотя бы для половины строк $x$ длины не больше $n$ длина кода $c(x)$ строго меньше длины $x$. Прокомментируйте результат Васи.
131. Пусть вероятности символов упорядочены по убыванию ($p_1 \ge p_2 \ge \ldots \ge p_n$) и являются дробями, у которых числитель 1, а знаменатель - степень двойки. Что можно сказать про арифметическое кодирование в этом случае?
132. Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в среднем тратит в $c$ раз меньше бит на символ строки, чем код Хаффмана.
133. При арифметическом кодировании может повезти и у достаточно длинной строки код получится коротким, хотя длина строки большая, и оценка на длину кода тоже большая. Приведите пример такой строки.
134. Для предыдущего задания приведите пример бесконечной последовательности строк возрастающей длины, для которых проявляется описанный эффект.
135. При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
136. Проанализируйте время работы алгоритма арифметического кодирования (с учетом длинной арифметики).
137. Троичное арифметическое кодирование. Пусть при арифметичском кодировании мы используем в качестве знаменателя не $2^q$, а $3^q$, а числитель записываем как троичное число, дополненное ведущими нулями до длины $q$. Затем запишем числитель в двоичной записи, а ведущие нули заменим на нули в двоичной записи. Приведите пример строки, когда описанный метод через степени тройки будет лучше классического арифметического кодирования.
138. Приведите пример строки, когда метод из предыдущего задания будет хуже классического арифметического кодирования.
139. Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
140. Предложите алгоритм декодирования кода Барроуза-Уиллера.
141. Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
142. Предложите реализацию преобразования Move to Front за $O(n \log n)$.
143. Предложите реализацию преобразования Move to Front за $O(n)$.
144. Докажите, что при оптимальном кодировании с помощью LZ не выгодно делать повтор блока, который можно увеличить вправо
145. Разработайте алгоритм оптимального кодирования текста с помощью LZ, если на символ уходит $c$ бит, а на блок повтора $d$ бит
146. Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
147. Изучите фонетический алфавит ИКАО. Какое среднее взвешенное число символов при передаче одной буквы (вероятности символов считали в позапрошлом ДЗ).
148. Какое минимальное расстояние Хемминга между двумя последовательностями звуков русского языка для символа в фонетическом алфавите ИКАО (при сравнении слов разной длины считайте, что символы более длинного слова с номерами большими длины более короткого дают вклад +1). Хороший ли показатель в данном случае расстояние Хемминга? Какая самая неудачная пара слов в фонетическом алфавите ИКАО?
149. Изучите коды ISBN-10 и ISBN-13. Докажите, что они находят одну ошибку в десятичной системе счисления.
150. Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
151. Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n>n_0$)
152. Испорченный символ. Пусть вместо замены на противополжный символ портится, то есть при приеме вместо некоторых символов принимается неопределенность ""?"". Как изменятся определения и параметры кодов обнаруживающих и исправляющих $d$ ошибок в этом случае?
153. Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: удаление одного бита, замена одного бита на противоположный. Таким образом, при отправке сообщения длины $l$ может быть получено либо сообщение длины $l$, в котором не более одного бита исправлено на противоположный, либо сообщение длины $l - 1$, в котором все биты верные, но одного бита, неизвестно, какого, не хватает.
154. Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: добавление одного бита, замена одного бита на противоположный. Таким образом, при отправке сообщения длины $l$ может быть получено либо сообщение длины $l$, в котором не более одного бита исправлено на противоположный, либо сообщение длины $l + 1$, в котором все биты верные, а также добавлен еще один, неизвестно, какой, бит.
155. Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: обмен местами двух соседних битов.
156. Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую непустую двоичную строку длиной не больше $n$ сжать, чтобы её размер уменьшился хотя бы на один символ?
157. Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую двоичную строку длиной от 2 до $n$ сжать, чтобы её размер уменьшился хотя бы на два символа?
158. Линейность кода Хемминга. Зафиксируем количество информационных битов $n$. Докажите, что множество векторов, которые являются корректными кодами Хемминга образуют множество решений системы линейных уравнений $Ax=0$ для некоторой матрицы $A$, все вычисления происходят по модулю $2$.
159. Получение кода Хемминда умножением на матрицу. Зафиксируем количество информационных битов $n$. Докажите, что существует матрица $A$, такая что если $y$ это код Хемминга для строки $x$, то $y=Ax$.
160. Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
161. Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
162. Докажите, что $g_{i \oplus j} = g_i \oplus g_j$.
163. Выведите формулу, которая по кодовому слову возвращает его позицию в зеркальном коде Грея (аналог формулы из задания 128)
164. Разработайте код Грея для $k$-ичных векторов
165. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
166. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз, а в конце возвращается в исходную ячейку?
167. Код ""антигрея"" - постройте двоичный код, в котором соседние слова отличаются хотя бы в половине бит
168. Троичный код ""антигрея"" - постройте троичный код, в котором соседние слова отличаются во всех позициях
169. При каких $n$ и $k$ существует двоичный $n$-битный код, в котором соседние кодовые слова отличаются ровно в $k$ позициях?
170. Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
171. Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
172. Сколько существует векторов длины $n + 1$, содержащих каждое число от $1$ до $n$ хотя бы по одному разу?
173. Выведите рекуррентную формулу для числа комбинаторных объектов: вектор длины $2n$, в котором каждое число от $1$ до $n$ встречается ровно два раза.
174. Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
175. Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
176. Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
177. Докажите, что существует способ упорядочить все двоичные вектора длины $n$, чтобы любые два соседних отличались в не более, чем двух позициях, а количество единиц в $i$-м векторе не превосходило количество единиц в $j$-м векторе при $i < j$.
178. Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $i$-м разряде (нумерация разрядов с 1 от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес $i$-го разряда $i!$. Докажите, что у каждого положительного числа ровно одно представление в факториальной системе счисления (с точностью до ведущих нулей). Предложите алгоритм перевода числа в факториальную систему счисления.
179. Как связана факториальная система счисления и нумерация перестановок?
180. Фибоначчиева система счисления. Рассмотрим систему счисления, где есть две цифры, 0 и 1. Пусть нумерация разрядов ведется с 1 от младшего к старшему, вес $i$-го разряда $F_i$, где $F_i$ - $i$-е число Фибоначчи ($F_0 = 1$, $F_1 = 1$, нулевой разряд не используется). При этом запрещается исползовать две единицы в соседних разрядах. Сколько представлений в Фибоначчиевой системе счисления у положительного числа $x$? Предложите алгоритм перевода числа в фибоначчиеву систему счисления.
181. Свяжите фибоначчиеву систему счисления с нумерацией каких-либо комбинаторных объектов.
182. Выразите $n \choose k$ через $n-1 \choose k-1$, $n$ и $k$.
183. Выразите $n \choose k$ через $n-1 \choose k$, $n$ и $k$.
184. Докажите, что ${n \choose m}{m \choose k}={n \choose k}{n-k \choose m - k}$.
185. Докажите, что $\sum\limits_{k=0}^n {k \choose m}={n+1 \choose m+1}$.
186. Докажите, что $\sum\limits_{k=0}^n {m+k \choose k}={m+n+1 \choose n}$.
187. Докажите, что $\sum\limits_{k=0}^n {r \choose k}{s \choose n - k}={r+s \choose n}$.
188. Докажите, что $\sum\limits_{k=0}^m {r \choose k}\left(\frac{r}{2} - k\right)=\frac{m+1}{2}{r \choose m+1}$. // Забавно, что нет простого выражения для $\sum\limits_{k=0}^m {r \choose k}$.
189. Обобщите формулу бинома Ньютона на степень суммы трёх: $(x+y+z)^n=?$
190. Докажите, что $\sum\limits_k{r \choose m + k}{s \choose n - k}={r+s \choose m+n}$. В этом и следующих заданиях сумма берётся по всем допустимым целым $k$.
191. Докажите, что $\sum\limits_k{r \choose m + k}{s \choose n + k}={r+s \choose r-m+n}$
192. Докажите, что $\sum\limits_k(-1)^k{r \choose m + k}{s+k \choose n}=(-1)^{r+m}{s-m \choose n-r}$
193. Докажите, что $\sum\limits_k(-1)^k{r-k \choose m}{s \choose k-n}=(-1)^{r+n}{s-m-1 \choose r-m-n}$
194. Докажите, что $\sum\limits_k{m-r+s\choose k}{n+r-s \choose n-k}{r+k \choose m+n}={r \choose m}{s \choose n}$
195. Вычислите сумму $\sum\limits_{k=0}^m{m \choose k}/{n \choose k}$.
196. Докажите, что $\sum\limits_k {n - k \choose k} = F_n$ ($n$-е число Фибоначчи).
197. Докажите, что число Каталана $C_n = \frac{1}{n+1} {2n \choose n}$.
198. Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
199. Будем называть последовательность сортируемой стеком, если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана.
200. Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.
201. Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.
202. Докажите, что число разбиений вершин $2n$-угольника на пары непересекающимися хордами равно числу Каталана.
203. Докажите, что число мультимножеств из $n$ чисел от $0$ до $n$, сумма которых делится на $n+1$, равно числу Каталана.
204. Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств (например, для $n = 3$, $k = 2$ есть следующие разбиения: $\{[1], [2, 3]\}$, $\{[1], [3, 2]\}$, $\{[1, 2], [3]\}$, $\{[1, 3], [2]\}$, $\{[2, 1], [3]\}$, $\{[2], [3, 1]\}$.
205. Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами.
206. Сюръекцией называется такая функция $f : X \to Y$, что для каждого элемента $y \in Y$ существует $x \in X$, что $f(x) = y$. Придумайте рекуррентную формулу для числа сюръекций из $\{1..n\}$ в $\{1..k\}$.
207. Выведите другую формулу для числа сюръекций, используя формулу включений-исключений. Свяжите число сюръекций с числами Стирлинга второго рода.
208. Найдите число сочетаний из $n$ по $k$, что любые два выбранных числа отличаются как минимум на $d$.
209. Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые.
210. Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых.
211. Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые.
212. Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.
213. Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?
214. Докажите формулу $t^{\overline{n}}=\sum\limits_{k=0}^n\left[n\atop k\right]t^k$, где $t^{\overline{n}} = t(t+1)\ldots(t+n-1)$ называется ""$n$-й восходящей факториальной степенью $t$"".
215. Докажите формулу $t^n=\sum\limits_{k=0}^n(-1)^{n-k}\left\{n\atop k\right\}t^{\overline k}$.
216. Придумайте аналогичные двум предыдущим заданиям формулы для $t^{\underline{n}} = t(t-1)\ldots(t-(n-1))$ ($t^{\underline{n}}$ называется ""$n$-й нисходящей факториальной степенью $t$"").
217. Неподвижной точкой в перестановке называется элемент $a_i = i$. Беспорядком называется перестановка без неподвижных точек. Найдите число беспорядков длины $n$ с помощью формулы включений-исключений.
218. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ циклами без неподвижных точек.
219. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками. Не пользуйтесь формулой для подсчета беспорядков, придумайте именно рекуррентную формулу.
220. Префиксным максимумом в перестановке называется элемент, который больше всех предыдущих. Выведите рекуррентную формулу для числа перестановок размера $n$ с $k$ префиксными максимумами.
221. Транспозицией называется перестановка, которая имеет один цикл длины $2$ и остальные элементы являются неподвижными точками. Перестановка называется чётной, если ее можно представить в виде произведения чётного числа транспозиций. Докажите, что если перестановку можно представить в виде произведения циклов длины 3, то она является чётной.
222. Транспозиция называется элементарной, если она переставляет местами два соседних элемента. Докажите, что перестановка является чётной тогда и только тогда, когда любое ее представление в виде произведения элементарных транспозиций содержит чётное число сомножителей.
223. Докажите, что перестановка является чётной тогда и только тогда, когда любое ее представление в виде произведения транспозиций содержит чётное число сомножителей.
224. Докажите, что число четных перестановок равно $\frac {n!}{2}$ при $n \ge 2$.
225. Инверсией в перестановке $a$ называется пара индексов $i < j$, для которой $a_i > a_j$. Докажите, что перестановка является чётной тогда и только тогда, когда она содержит чётное число инверсий.
226. Докажите, что перестановка является чётной тогда и только тогда, когда $n - c$ четно, где $c$ - число циклов в перестановке.
227. Докажите, что множество четных перестановок с операцией композиции образует группу.
228. Есть две перестановки: первая меняет местами первые два элемента, а вторая делает циклический сдвиг на один. Покажите, что любую перестановку можно выразить, как композицию этих двух (возможно, используя каждую несколько раз).
229. Перестановка $[a_1, a_2, \ldots, a_n]$ называется пилообразной, если $a_1 > a_2 < a_3 > a_4 \ldots a_n$. Найдите количество пилообразных перестановок (можно получить формулу с $O(n)$ слагаемыми или рекуррентную формулу)
230. Перестановка $[a_1, a_2, \ldots, a_n]$ называется неразложимой, если у нее ни для какого $0 < k < n$ нет префикса длины $k$, который является перестановкой чисел от 1 до $k$. Найдите количество неразложимых перестановок (можно получить формулу с $O(n)$ слагаемыми или рекуррентную формулу)
231. Сопряжением перестановки $\alpha$ относительно перестановки $\tau$ называется перестановка $\tau^{-1}\alpha\tau$. Две перестановки $\alpha$ и $\beta$ называются сопряженными, если существует такая перестановка $\tau$, что $\beta = \tau^{-1}\alpha\tau$. Докажите, что сопряжение является отношением эквивалентности.
232. Докажите, что две перестановки являются сопряженными тогда и только тогда, когда их циклические классы совпадают.