Изменения

Перейти к: навигация, поиск

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

30 569 байт добавлено, 16:54, 22 декабря 2020
Нет описания правки
# Дана формула в КНФ. Можно каждое вхождение переменной 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)$.
# Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
# Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
# Разработайте код Грея для k-ичных векторов
# При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
# При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз, а в конце возвращается в исходную ячейку?
# Код ""антигрея"" - постройте двоичный код, в котором соседние слова отличаются хотя бы в половине бит
# Троичный код ""антигрея"" - постройте троичный код, в котором соседние слова отличаются во всех позициях
# При каких $n$ и $k$ существует двоичный $n$-битный код, в котором соседние кодовые слова отличаются ровно в $k$ позициях?
# Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
# Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
# Выведите рекуррентную формулу для числа комбинаторных объектов: вектор длины $2n$, в котором каждое число от $1$ до $n$ встречается ровно два раза.
# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
# Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
# Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $i$-м разряде (нумерация разрядов с 1 от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес $i$-го разряда $i!$. Докажите, что у каждого положительного числа ровно одно представление в факториальной системе счисления (с точностью до ведущих нулей). Предложите алгоритм перевода числа в факториальную систему счисления.
# Как связана факториальная система счисления и нумерация перестановок?
# Фибоначчиева система счисления. Рассмотрим систему счисления, где есть две цифры, 0 и 1. Пусть нумерация разрядов ведется с 1 от младшего к старшему, вес $i$-го разряда $F_i$, где $F_i$ - $i$-е число Фибоначчи ($F_0 = 1$, $F_1 = 1$, нулевой разряд не используется). При этом запрещается исползовать две единицы в соседних разрядах. Сколько представлений в Фибоначчиевой системе счисления у положительного числа $x$? Предложите алгоритм перевода числа в фибоначчиеву систему счисления.
# Свяжите фибоначчиеву систему счисления с нумерацией каких-либо комбинаторных объектов.
# Выразите $n \choose k$ через $n-1 \choose k-1$, $n$ и $k$.
# Выразите $n \choose k$ через $n-1 \choose k$, $n$ и $k$.
# Докажите, что ${n \choose m}{m \choose k}={n \choose k}{n-k \choose m - k}$.
# Докажите, что $\sum\limits_{k=0}^n {m+k \choose k}={m+n+1 \choose n}$.
# Докажите, что $\sum\limits_{k=0}^n {k \choose m}={n+1 \choose m+1}$.
# Докажите, что $\sum\limits_{k=0}^n {r \choose k}{s \choose n - k}={r+s \choose n}$.
# Докажите, что $\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}$.
# Обобщите формулу бинома Ньютона на степень суммы трёх: $(x+y+z)^n=?$
# Докажите, что $\sum\limits_k{r \choose m + k}{s \choose n - k}={r+s \choose m+n}$. В этом и следующих заданиях сумма берётся по всем допустимым целым $k$.
# Докажите, что $\sum\limits_k{r \choose m + k}{s \choose n + k}={r+s \choose r-m+n}$
# Докажите, что $\sum\limits_k(-1)^k{r \choose m + k}{s+k \choose n}=(-1)^{r+n}{s-m \choose n-r}$
# Докажите, что $\sum\limits_k(-1)^k{r-k \choose m}{s \choose k-n}=(-1)^{r+n}{s-m-1 \choose r-m-n}$
# Докажите, что $\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}$
# Вычислите сумму $\sum\limits_{k=0}^m{m \choose k}/{n \choose k}$.
# Докажите, что $\sum\limits_k {n - k \choose k} = F_n$ ($n$-е число Фибоначчи).
# Докажите, что число Каталана $C_n = \frac{1}{n+1}C_{2n}^n$.
# Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
# Докажите, что число подвешенных деревьев с порядком на детях с $n$ вершинами равно числу Каталана.
# Будем называть последовательность ''сортируемой стеком'', если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана.
# Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.
# Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.
# Докажите, что число мультимножеств из $n$ чисел от $0$ до $n$, сумма которых делится на $n+1$, равно числу Каталана
# Укажите способ подсчитать число разбиений заданного $n$-элементного множества на $k$ упорядоченных непустых подмножеств (например, для $n = 3$, $k = 2$ есть следующие разбиения: $\{[1], [2, 3]\}$, $\{[1], [3, 2]\}$, $\{[1, 2], [3]\}$, $\{[1, 3], [2]\}$, $\{[2, 1], [3]\}$, $\{[2], [3, 1]\}$.
# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками. Не пользуйтесь формулой для подсчета беспорядков, придумайте именно рекуррентную формулу.
# Докажите формулу $t^{\overline{n}}=\sum\limits_{k=0}^n\left[n\atop k\right]t^k$
# Докажите формулу $t^n=\sum\limits_{k=0}^n(-1)^{n-k}\left\{n\atop k\right\}t^{\overline k}$
# Придумайте аналогичные двум предыдущим заданиям формулы для $t^{\underline{n}}$.
# Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ циклами без неподвижных точек
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых
# Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые
# Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.
# Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?
# Есть две перестановки: первая меняет местами первые два элемента, а вторая делает циклический сдвиг на один. Покажите, что любую перестановку можно выразить, как композицию этих двух (возможно, используя каждую несколько раз).
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Докажите, что композиция отражения и поворота является отражением.
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Докажите, что композиция двух отражений является поворотом.
# В вершинах правильного $n$-угольника записаны числа от $1$ до $n$. Рассмотрим две операции: поворот на угол $2\pi i/n$ и отражение относительно прямой, проходящей через центр многоугольника, после которого вершины оказываются в тех же точках. Зафиксируем конкретную прямую, относительно которой можно делать отражение. Докажите, что композиция любой последовательности отражений и поворотов является либо поворотом, либо композицией поворота и отражения относительно зафиксированной прямой.
# Выведите формулу для числа ожерелий из $n$ бусинок $k$ цветов с точностью до циклического сдвига и отражения.
# Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно две белые бусины.
# Выведите формулу для числа ожерелий из $n$ бусинок 2 цветов с точностью до циклического сдвига, в которых ровно $k$ белых бусин.
# Пусть $p$ простое. Найдите число ожерелий из $p^2$ бусинок 2 цветов с точностью до циклического сдвига.
# Пусть $p$ и $q$ простые. Найдите число ожерелий из $pq$ бусинок 2 цветов с точностью до циклического сдвига.
# Найдите число таких различных булевых функций от 2 переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над некоторыми переменными
# Найдите число таких различных булевых функций от $n$ переменных, что ни одна из них не может быть получена ни из какой другой навешиванием отрицаний над некоторыми переменными
# Выведите формулу для числа раскрасок $n$ шаров в $k$ цветов, порядок не важен.
# Выведите формулу для числа раскрасок прямоугольника $n \times m$ в $k$ цветов с точностью до отражения относительно горизонтальной и вертикальной оси.
# Выведите формулу для числа раскрасок граней тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок ребер тетраэдра в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок граней куба в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок ребер куба в $k$ цветов с точностью до любого поворота в 3D.
# Выведите формулу для числа раскрасок граней октаэдра в $k$ цветов с точностью до любого поворота в 3D.
# Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?
# Пусть 3 - множество из трех различных элементов, каждый из которых имеет вес 1. Можно условно называть их красный, синий и зелёный. Что представляет собой $Seq(3)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $Set(3)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $MSet(3)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $Cycle(3)$? Посчитайте число элементов для него, в зависимости от веса.
# Пусть $F$ - множество из трёх различных элементов, два из которых имеют вес 1, а один - 2. Можно условно называть их маленький чёрный, маленький белый и большой. Что представляет собой $Seq(F)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $Set(F)$? Посчитайте число элементов для него, в зависимости от веса.
# Что представляет собой $MSet(F)$? Посчитайте число элементов для него, в зависимости от веса.
# Постройте множество неотрицательных четных чисел как непомеченный комбинаторный класс (в этом классе должен быть ровно один объект веса 0, 2, 4, ...).
# Постройте множество неотрицательных нечетных чисел как непомеченный комбинаторный класс (в этом классе должен быть ровно один объект веса 1, 3, 5, ...).
# Пусть $A$ - множество помеченных комбинаторных объектов, известно количество объектов любого веса $a_0$, $a_1$, ... Выведите рекуррентную формулу $c_{n, k}$ для количества объектов веса $n$ в классе $Cycle^k(A)$ (не используя рекуррентную формулу для $Seq^k(A)$).
# Пусть $A$ - множество помеченных комбинаторных объектов, известно количество объектов веса 0 $a_0$, веса 1 $a_1$, ... Выведите рекуррентную формулу $b_{n, k}$ для количества объектов веса $n$ в классе $Set^k(A)$ (не используя рекуррентную формулу для $Seq^k(A)$).
# Обозначим за $Z$ множество помеченных комбинаторных объектов, содержащее только один элемент веса 1. Используя конструкцию $Set^k(Cycle(Z))$ и предыдущее задание, постройте альтернативную рекуррентную формулу для чисел Стирлинга 1 рода.
# Обозначим за $Set^+(A)$ множество непустых множеств, состоящих из элементов класса $A$. Используя конструкцию $Set^k(Set^+(Z))$, постройте альтернативную рекуррентную формулу для чисел Стирлинга 2 рода.
# Используя конструкцию $Set(Set^+(Z))$, постройте рекуррентную формулу для чисел Белла.
# Пусть $k$ - константа. Постройте отображения $\{1..n\} \to \{1..k\}$ как помеченные комбинаторные объекты. Найдите формулу количества объектов веса $n$.
# Сюръекцией называется функция $A \to B$, что для любого $b \in B$ существует $a \in A$, что $f(a) = b$. Пусть $k$ - константа. Постройте сюръекции $\{1..n\} \to \{1..k\}$ как помеченные комбинаторные объекты.
Анонимный участник

Навигация