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

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 1 семестр

1. Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
2. Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
3. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
4. Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
5. Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
6. Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
7. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их композиция?
8. Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричным их композиция?
9. Постройте пример рефлексивного, симметричного, но не транзитивного отношения
10. Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
11. Пусть $R$ - отношение на $A$. Рассмотрим $Tr(R)$ - пересечение всех транзитивных отношений на $A$, содержащих $R$. Докажите, что $Tr(R) = R^{+}$.
12. Пусть $R$ - транзитивное антисимметричное отношение. Предложите способ за полиномиальное время построить минимальное отношение $S$, такое что $S^+ = R$.
13. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
14. В каком случае транзитивное замыкание отношения будет отношением эквивалентности?
15. В каком случае транзитивное замыкание отношения будет отношением частичного порядка?
16. Выразите в явном виде "и", "или" и "не" через стрелку Пирса
17. Выразите в явном виде "и", "или" и "не" через штрих Шеффера
18. Является ли пара $\{x\to y, \neg x\}$ базисом?
19. Является ли набор $\{x \to y, \langle xyz\rangle, \neg x\}$ базисом?
20. Является ли набор $\{{\mathbf 0}, \langle xyz \rangle, \neg x\}$ базисом?
21. Можно ли выразить "и" через "или"?
22. Выразите медиану 5 через медиану 3
23. Выразите медиану $2n+1$ через медиану 3
24. Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
25. Докажите, что любую функцию, кроме тождественной единицы, можно записать в СКНФ
26. Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
27. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что "и" и "или" - пороговые функции.
28. Приведите пример непороговой функции
29. Рассмотрим булеву функцию $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$
30. Сколько существует самодвойственных функций от $n$ переменных?
31. Приведите пример функции, которая лежит во всех пяти классах Поста.
32. Приведите пример функции, которая лежит во всех пяти классах Поста и существенно зависит хотя бы от трех переменных.
33. Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
34. КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
35. Докажите, что если булеву функцию $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$
36. Докажите, что если выполнено следствие: $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$ можно задать в форме Крома.
37. Докажите, что если булеву функцию $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$
38. Докажите, что если выполнено следствие: $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$ можно задать в форме Хорна
39. Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
40. Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
41. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов.
42. Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$.
43. Докажите, что не существует схем константной глубины для функций $x_1 \oplus ... \oplus x_n$.
44. Докажите, что не существует схемы константной глубины для сложения.
45. Постройте схему из функциональных элементов с тремя входами: $x, y, z$ и одним выходом. Значение на выходе равно $x$, если $z=0$ и $y$, если $z=1$. Используйте базис из всех не более чем бинарных функций.
46. Мультиплексор - функциональная схема с $n = 2^k + k$ и одним выходом. Обозначим первые $2^k$ входов как $x_0, x_1, \ldots, x_{2^k-1}$, а оставшиеся $k$ как $y_0, y_1, \ldots, y_{k-1}$. Выход мультиплексора равен $x_i$, где $i$ --- число, двоичное представление которого подано на входы $y_0, y_1, \ldots, y_{k-1}$. Постройте схему линейного от $n$ размера для мультиплексора.
47. Дешифратор - функциональная схема с $k + 1$ входом и $n = 2^k$ выходами. Обозначим первые $k$ входов как $y_0, y_1, \ldots, y_{k-1}$, а последний как $z$. Обозначим выходы дешифратора как $x_0, x_1, \ldots, x_{2^k-1}$. Значение на выходах дешифратора 0 на всех выходах, кроме $x_i$, где $i$ --- число, двоичное представление которого подано на входы $y_0, y_1, \ldots, y_{k-1}$, а на выходе $x_i$ равно значению $z$. Постройте схему линейного размера для дешифратора.
48. Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
49. На одном китайском заводе в матричном умножителе случайно использовали элементы "или" вместо "и". Можно ли из получившихся значений получить произведение исходных чисел (доступа к входам нет, есть только доступ к $n\times 2n$ выходам матричного псевдоумножителя).
50. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
51. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n/n)$ элементов.
52. Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".
53. Постройте контактную схему для функции "xor".
54. Постройте контактную схему для функции медиана трех.
55. Докажите, что любую булеву функцию можно представить контактной схемой.
56. Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
57. Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
58. Постройте контактную схему, в которой для каждого из $2^n$ наборов конъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта конъюнкция, используя $O(2^n)$ ребер.
59. Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
60. Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
61. Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
62. Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
63. Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды
64. Укажите, как построить дерево Хаффмана за линейное время, если символы уже отсортированы по частоте
65. Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
66. Предложите алгоритм построения оптимального кода среди префиксных кодов, для которых коды символов упорядочены лексикографически
67. Предложите способ хранения информации об оптимальном префиксном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
68. Можно ли разработать алгоритм, который сжимает любой файл не короче заданной величины $N$ хотя бы на 1 бит?
69. Приведите пример однозначно декодируемого кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным
70. Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
71. Пусть заданы пары $(u_i, v_i)$. Предложите алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.
72. Докажите, что если в коде Хаффмана для некоторой строки $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)$.

</wikitex>