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

<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$ - транзитивное антисимметричное отношение. Постройте минимальное отношение $S$, такое что $S^+ = R$
12. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
13. Является ли пара $\{x\to y, \neg x\}$ базисом?
14. Является ли набор $\{x \to y, \langle xyz\rangle, \neg x\}$ базисом?
15. Является ли набор $\{{\mathbf 0}, \langle xyz \rangle, \neg x\}$ базисом?
16. Можно ли выразить "и" через "или"?
17. Выразите медиану 5 через медиану 3
18. Выразите медиану $2n+1$ через медиану 3
19. Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
20. Докажите, что любую функцию, кроме тождественной единицы, можно записать в СКНФ
21. Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
22. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что "и" и "или" - пороговые функции.
23. Приведите пример непороговой функции
24. Рассмотрим булеву функцию $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$
25. Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
26. КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
27. Докажите, что если булеву функцию $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$
28. Докажите, что если выполнено следствие: $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$ можно задать в форме Крома.
29. Докажите, что если булеву функцию $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$
30. Докажите, что если выполнено следствие: $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$ можно задать в форме Хорна
31. Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
32. Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
33. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов.
34. Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
35. Постройте схему линейного размера для мультиплексора.
36. Постройте схему линейного размера для дешифратора.
37. Что получится, если в матричном умножителе заменить элементы "and" на элементы "or"?
38. Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
39. Докажите, что для сложения не существует схемы глубины $O(1)$
40. Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".
41. Постройте контактную схему для функции "xor".
42. Постройте контактную схему для функции медиана трех.
43. Докажите, что любую булеву функцию можно представить контактной схемой.
44. Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
45. Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
46. Постройте контактную схему, в которой для каждого из $2^n$ наборов конъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта конъюнкция, используя $O(2^n)$ ребер
47. Докажите, что любую функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер
48. Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
49. Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
50. Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
51. Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды
52. Укажите, как построить дерево Хаффмана за линейное время, если символы уже отсортированы по частоте
53. Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
54. Предложите алгоритм построения оптимального кода среди префиксных кодов, для которых коды символов упорядочены лексикографически
55. Предложите способ хранения информации об оптимальном префиксном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
56. Можно ли разработать алгоритм, который сжимает любой файл не короче заданной величины $N$ хотя бы на 1 бит?
57. Приведите пример однозначно декодируемого кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным
58. Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
59. Пусть заданы пары $(u_i, v_i)$. Предложите алгоритм проверки, что существует код Хаффмана для некоторой строки, в котором $i$-е кодовое слово содержит $u_i$ нулей и $v_i$ единиц.
60. Докажите, что если в коде Хаффмана для некоторой строки $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)$.
61. Разработайте алгоритм кодирования Move To Front строки длиной $n$ за $O(n \log n)$
62. Докажите, что при оптимальном кодирование с помощью LZ77 не выгодно делать повтор блока, который можно увеличить вправо
63. Верно ли утверждение из предыдущего задания при кодировании с помощью L78?
64. Разработайте алгоритм оптимального кодирования текста с помощью LZ77, если на символ уходит $c$ бит, а на блок повтора $d$ бит
65. Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
66. Разработайте алгоритм обратного преобразования Барроуза-Уиллера
67. Разработайте алгоритм обратного преобразования Барроуза-Уиллера за O(n)
68. Проанализируйте время работы алгоритма арифиметического кодирования
69. Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в $c$ раз лучше Хаффмана
70. При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
71. При арифметическом кодировании трудным моментом является деление отрезка в пропорциях, не являющихся степенями двойки. Рассмотрим модификацию арифметического кодирования, когда соотношения между символами приближаются дробями со знаменателями - степенями двойки. Что можно сказать про получившийся алгоритм?
72. Разработайте оптимальный код исправляющий одну ошибку при пересылке 2 битов
73. Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
74. Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)
75. Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
76. Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
77. Разработайте код Грея для k-ичных векторов
78. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
79. При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз, а в конце возвращается в исходную ячейку?
80. Код "антигрея" - постройте двоичный код, в котором соседние слова отличаются хотя бы в половине бит
81. Троичный код "антигрея" - постройте троичный код, в котором соседние слова отличаются во всех позициях
82. При каких $n$ и $k$ существует двоичный $n$-битный код, в котором соседние кодовые слова отличаются ровно в $k$ позициях?
83. Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
84. Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
85. Докажите корректность следующего алгоритма построения цепного кода. Начинаем со строки из $n$ нулей. Каждый раз пытаемся жадно приписать 1, если слово из последних $n$ символов уже встречалось раньше, то приписываем 0. Заканчиваем, когда все $2^n$ слов получены.
86. Докажите, что $\sum_{k=0}^n C_n^k = 2^n$
87. Докажите, что $\sum_{k=0}^n (-1)^kC_n^k = 0$
88. Используйте предыдущее задание для альтернативного доказательства формулы включения-исключения: посчитайте для каждого элемента, сколько раз он будет посчитан в правой части формулы.
89. Предложите алгоритм получения по перестановке ее таблицы инверсий за $O(n \log n)$.
90. Предложите алгоритм получения перестановке по ее таблице инверсий.
91. Предложите алгоритм получения перестановки по ее таблице инверсий за $O(n \log n)$.
92. Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
93. Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
94. Коды Грея для размещений. Предложите способ перечисления сочетаний, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
95. Чему равно число перестановок с заданным циклическим классом?
96. Степенью перестановки $\pi$ называется минимальное $k$, такое что $\pi^k=i$, где $i$ - тождественная перестановка. Как связана степень перестановки с ее циклическим классом?
97. Предложите алгоритм поиска перестановки из $n$ элементов с максимальной степенью за $O(n^3)$.
98. Максимумом в перестановке называется элемент, который больше своих соседей (одного, если он первый или последний, обоих иначе). Выведите рекуррентную формулу для числа перестановок $n$ элементами с $k$ максимумами
99. Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
100. Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
101. Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?
102. Сочетание с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок не важен. Чему равно число сочетаний с повторениями из $n$ по $k$?
103. Размещение с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок выбора важен. Чему равно число размещений с повторениями из $n$ по $k$?
104. Докажите, что числа Стирлинга 1 рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней
105. Докажите, что числа Стирлинга 2 рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней
106. Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств
107. Докажите, что $n$-е число Каталана равно ${2n \choose n}/(n+1)$
108. Двоичное дерево - это подвешенное дерево, где каждая вершина может иметь двух детей: левого и правого. Каждый из них также является двоичным деревом (либо отсутствует). Докажите, что число двоичных деревьев с $n$ вершинами равно $n$-му числу Каталана.
109. Подвешенное дерево с порядком на детях - это подвешенное дерево, где каждая вершина может иметь произвольное число детей, причем дети упорядочены. Каждый ребенок в свою очередь является подвешенным деревом. Докажите, что число подвешенных деревьев порядком на детях с $n$ вершинами равно $n-1$-му числу Каталана.
110. Докажите, что число триангуляций правильного $n$-угольника равно $n-2$-му числу Каталана.
111. Установите явное взаимно-однозначное соответствие между объектами из предыдущих трех заданий и правильными скобочными последовательностями.
112. Разбиение на слагаемые это представление $n$ в виде суммы набора невозрастающих положительных целых чисел. Например, есть 5 разбиений числа 4: $4$, $3+1$, $2+2$, $2+1+1$ и $1+1+1+1$. Укажите способ подсчитать число разбиений числа на слагаемые за $O(n^2)$.
113. Укажите способ подсчитать число разбиений числа на слагаемые за $O(n \sqrt{n})$
114. Решите с помощью ДП задачу о наибольшей общей подстроке за $O(n^2)$
115. Решите с помощью ДП задачу о наибольшей общей возрастающей подпоследовательности за $O(n^3)$
116. Решите с помощью ДП задачу о наибольшей общей возрастающей подпоследовательности за $O(n^2)$
117. Докажите, что минимальное число невозрастающих подпоследовательностей, на которые можно разбить заданную последовательность, равно длине ее наибольшей возрастающей подпоследовательности
118. Решите задачу о наибольшей возрастающей подпоследовательности за $O(n \log n)$
119. Решите с помощью ДП задачу о наибольшей подпоследовательности-палиндроме
120. Рассмотрим задачу: расставить знаки +, * и скобки в выражении таким образом, чтобы его значение было минимальным по модулю. Почему неправильно работает решение на базе ДП, в котором для каждого подотрезка хранится минимальное и максимальное положительное и отрицательное значение, достижимое на этом отрезке?
121. Решите с помощью ДП задачу о наибольшей пилообразной подпоследовательности (последовательность называется пилообразной, если никакие ее три подряд идущих элемента не образуют ни возрастающую, ни убывающую последовательность)
122. Докажите, что произведение длины наибольшей возрастающей подпоследовательности и наибольшей убывающей подпоследовательности перестановки не меньше $n$
123. Решите с помощью ДП задачу о наибольшей общей подпоследовательности-палиндроме
124. Будем говорить, что строки a и b образуют пару подстрок строки c, если c можно представить как xaybz, где x, y и z - произвольные строки. Решите с помощью ДП задачу о наибольшей общей паре подстрок.
125. Задача о редакционном расстоянии: найдите последовательность действий для превращения строки $s$ в строку $t$ с помощью операций вставки, удаления и замены символа. Длины строк $m$ и $n$, соответственно. Требуется решить задачу за $O(mn)$ с памятью $O(m + n)$.
126. Решите задачу о редакционном расстоянии, если помимо операций вставки, удаления и замены символа можно использовать операцию обмена местами двух соседних символов.
127. Решите битоническую задачу о комивояжере: найдите во взвешенном графе гамильтонов цикл минимального веса, который удовлетворяет дополнительно следующему свойству: сначала номера посещенных вершин возрастают, а затем убывают.
128. Задача о рюкзаке: дано $n$ предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$. Решите задачу за время время $O(nc)$ с памятью $O(x)$.
129. Задача о рюкзаке без ограничения на число одинаковых предметов: дано $n$ типов предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$. Каждого предмета можно брать несколько (любое количество) экземпляров. Решите задачу за время время $O(nc)$ с памятью $O(x)$.
130. Непрерывная задача о рюкзаке: дано $n$ жидкостей, у каждой жидкости есть доступное количество $w_i$ и стоимость единицы жидкости $v_i$, размер рюкзака $c$, требуется выбрать для каждой жидкости число $0 \le x_i \le w_i$, чтобы суммарной стоимости выбранных жидкостей $\sum x_iv_i$ была максимальна и суммарное объем взятых жидкостей $\sum x_i$ был не более $c$.
131. Задача о рюкзаке, большой рюкзак: дано $n$ типов предметов, у предмета $i$-го типа есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, предметов каждого типа можно взять любое количество, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$. Докажите, что если максимальный вес предмета $z$, то следует взять предметов с максимальным отношением $c_i/w_i$ с суммарным весом хотя бы $c - z^2$.
132. Решите задачу о рюкзаке: дано $n$ предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$, время $O(2^{n/2} \cdot poly(n))$, память $O(2^{n/2})$
133. Решите задачу: найти в дереве минимальное множество вершин, чтобы расстояние от любой вершины до одной из выбранных было не более $d$

</wikitex>