Список заданий по ДМ 2023 осень - История изменений

Admin в 15:52, 15 декабря 2023

2023-12-15T15:52:31Z

Admin в 12:58, 8 декабря 2023

2023-12-08T12:58:17Z

Admin в 06:32, 2 декабря 2023

2023-12-02T06:32:26Z

Admin в 17:04, 25 ноября 2023

2023-11-25T17:04:48Z

Admin в 10:51, 9 ноября 2023

2023-11-09T10:51:34Z

Admin в 19:20, 3 ноября 2023

2023-11-03T19:20:09Z

Admin в 08:45, 31 октября 2023

2023-10-31T08:45:36Z

Admin в 18:40, 25 октября 2023

2023-10-25T18:40:27Z

Admin в 11:53, 19 октября 2023

2023-10-19T11:53:58Z

Admin в 14:50, 11 октября 2023

2023-10-11T14:50:24Z

← Предыдущая		Версия 15:52, 15 декабря 2023
Строка 231:		Строка 231:
	# Сопряжением перестановки $\alpha$ относительно перестановки $\tau$ называется перестановка $\tau^{-1}\alpha\tau$. Две перестановки $\alpha$ и $\beta$ называются сопряженными, если существует такая перестановка $\tau$, что $\beta = \tau^{-1}\alpha\tau$. Докажите, что сопряжение является отношением эквивалентности.		# Сопряжением перестановки $\alpha$ относительно перестановки $\tau$ называется перестановка $\tau^{-1}\alpha\tau$. Две перестановки $\alpha$ и $\beta$ называются сопряженными, если существует такая перестановка $\tau$, что $\beta = \tau^{-1}\alpha\tau$. Докажите, что сопряжение является отношением эквивалентности.
	# Докажите, что две перестановки являются сопряженными тогда и только тогда, когда их циклические классы совпадают.		# Докажите, что две перестановки являются сопряженными тогда и только тогда, когда их циклические классы совпадают.
		+	# В вершинах правильного $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.
		+	# Почему мы не сделали задачу про вершины тетраэдра, вершины куба, вершины и ребра октаэдра? Неужели оставили на контрольную?

← Предыдущая		Версия 12:58, 8 декабря 2023
Строка 212:		Строка 212:
	# Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.		# Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.
	# Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?		# Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?
		+	# Докажите формулу $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$"".
		+	# Докажите формулу $t^n=\sum\limits_{k=0}^n(-1)^{n-k}\left\{n\atop k\right\}t^{\overline k}$.
		+	# Придумайте аналогичные двум предыдущим заданиям формулы для $t^{\underline{n}} = t(t-1)\ldots(t-(n-1))$ ($t^{\underline{n}}$ называется ""$n$-й нисходящей факториальной степенью $t$"").
		+	# Неподвижной точкой в перестановке называется элемент $a_i = i$. Беспорядком называется перестановка без неподвижных точек. Найдите число беспорядков длины $n$ с помощью формулы включений-исключений.
		+	# Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ циклами без неподвижных точек.
		+	# Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками. Не пользуйтесь формулой для подсчета беспорядков, придумайте именно рекуррентную формулу.
		+	# Префиксным максимумом в перестановке называется элемент, который больше всех предыдущих. Выведите рекуррентную формулу для числа перестановок размера $n$ с $k$ префиксными максимумами.
		+	# Транспозицией называется перестановка, которая имеет один цикл длины $2$ и остальные элементы являются неподвижными точками. Перестановка называется чётной, если ее можно представить в виде произведения чётного числа транспозиций. Докажите, что если перестановку можно представить в виде произведения циклов длины 3, то она является чётной.
		+	# Транспозиция называется элементарной, если она переставляет местами два соседних элемента. Докажите, что перестановка является чётной тогда и только тогда, когда любое ее представление в виде произведения элементарных транспозиций содержит чётное число сомножителей.
		+	# Докажите, что перестановка является чётной тогда и только тогда, когда '''любое''' ее представление в виде произведения транспозиций содержит чётное число сомножителей.
		+	# Докажите, что число четных перестановок равно $\frac {n!}{2}$ при $n \ge 2$.
		+	# Инверсией в перестановке $a$ называется пара индексов $i < j$, для которой $a_i > a_j$. Докажите, что перестановка является чётной тогда и только тогда, когда она содержит чётное число инверсий.
		+	# Докажите, что перестановка является чётной тогда и только тогда, когда $n - c$ четно, где $c$ - число циклов в перестановке.
		+	# Докажите, что множество четных перестановок с операцией композиции образует группу.
		+	# Есть две перестановки: первая меняет местами первые два элемента, а вторая делает циклический сдвиг на один. Покажите, что любую перестановку можно выразить, как композицию этих двух (возможно, используя каждую несколько раз).
		+	# Перестановка $[a_1, a_2, \ldots, a_n]$ называется пилообразной, если $a_1 > a_2 < a_3 > a_4 \ldots a_n$. Найдите количество пилообразных перестановок (можно получить формулу с $O(n)$ слагаемыми или рекуррентную формулу)
		+	# Перестановка $[a_1, a_2, \ldots, a_n]$ называется неразложимой, если у нее ни для какого $0 < k < n$ нет префикса длины $k$, который является перестановкой чисел от 1 до $k$. Найдите количество неразложимых перестановок (можно получить формулу с $O(n)$ слагаемыми или рекуррентную формулу)
		+	# Сопряжением перестановки $\alpha$ относительно перестановки $\tau$ называется перестановка $\tau^{-1}\alpha\tau$. Две перестановки $\alpha$ и $\beta$ называются сопряженными, если существует такая перестановка $\tau$, что $\beta = \tau^{-1}\alpha\tau$. Докажите, что сопряжение является отношением эквивалентности.
		+	# Докажите, что две перестановки являются сопряженными тогда и только тогда, когда их циклические классы совпадают.

← Предыдущая		Версия 06:32, 2 декабря 2023
Строка 195:		Строка 195:
	# Вычислите сумму $\sum\limits_{k=0}^m{m \choose k}/{n \choose k}$.		# Вычислите сумму $\sum\limits_{k=0}^m{m \choose k}/{n \choose k}$.
	# Докажите, что $\sum\limits_k {n - k \choose k} = F_n$ ($n$-е число Фибоначчи).		# Докажите, что $\sum\limits_k {n - k \choose k} = F_n$ ($n$-е число Фибоначчи).
		+	# Докажите, что число Каталана $C_n = \frac{1}{n+1} {2n \choose n}$.
		+	# Докажите, что число различных триангуляций правильного $n$-угольника равно числу Каталана. В этом и нескольких следующих заданиях номер соответствующего числа Каталана может отличаться от $n$, требуется также установить соответствие между размером задачи и номерами чисел Каталана.
		+	# Будем называть последовательность ''сортируемой стеком'', если ее можно отсортировать, используя в произвольном порядке следующие операции: (а) взять первый элемент входной последовательности и положить в стек (б) взять верхний элемент стека и отправить в конец выходной последовательности. Докажите, что число перестановок $n$ элементов, сортируемых стеком, равно число Каталана.
		+	# Докажите, что число перестановок $n$ элементов, в которых нет возрастающей последовательности длины 3, равно числу Каталана.
		+	# Докажите, что число способов расставить числа от 1 до $2n$ в прямоугольник $2 \times n$, чтобы числа в каждой строке и каждом столбце возрастали, равно числу Каталана.
		+	# Докажите, что число разбиений вершин $2n$-угольника на пары непересекающимися хордами равно числу Каталана.
		+	# Докажите, что число мультимножеств из $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$ подъемами.
		+	# Сюръекцией называется такая функция $f : X \to Y$, что для каждого элемента $y \in Y$ существует $x \in X$, что $f(x) = y$. Придумайте рекуррентную формулу для числа сюръекций из $\{1..n\}$ в $\{1..k\}$.
		+	# Выведите другую формулу для числа сюръекций, используя формулу включений-исключений. Свяжите число сюръекций с числами Стирлинга второго рода.
		+	# Найдите число сочетаний из $n$ по $k$, что любые два выбранных числа отличаются как минимум на $d$.
		+	# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые.
		+	# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых.
		+	# Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые.
		+	# Докажите, что число разбиений числа $n$ на нечетные слагаемые и число разбиений числа $n$ на различные слагаемые совпадает.
		+	# Для каких $n$ число разбиений $n$ на чётное число различных слагаемых и число разбиений $n$ на нечётное число различных слагаемых различно?

← Предыдущая		Версия 17:04, 25 ноября 2023
Строка 176:		Строка 176:
	# Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.		# Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
	# Докажите, что существует способ упорядочить все двоичные вектора длины $n$, чтобы любые два соседних отличались в не более, чем двух позициях, а количество единиц в $i$-м векторе не превосходило количество единиц в $j$-м векторе при $i < j$.		# Докажите, что существует способ упорядочить все двоичные вектора длины $n$, чтобы любые два соседних отличались в не более, чем двух позициях, а количество единиц в $i$-м векторе не превосходило количество единиц в $j$-м векторе при $i < j$.
		+	# Факториальная система счисления. Рассмотрим систему счисления, где бесконечно много цифр, в $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 {k \choose m}={n+1 \choose m+1}$.
		+	# Докажите, что $\sum\limits_{k=0}^n {m+k \choose k}={m+n+1 \choose n}$.
		+	# Докажите, что $\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+m}{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$-е число Фибоначчи).

← Предыдущая		Версия 10:51, 9 ноября 2023
Строка 158:		Строка 158:
	# Линейность кода Хемминга. Зафиксируем количество информационных битов $n$. Докажите, что множество векторов, которые являются корректными кодами Хемминга образуют множество решений системы линейных уравнений $Ax=0$ для некоторой матрицы $A$, все вычисления происходят по модулю $2$.		# Линейность кода Хемминга. Зафиксируем количество информационных битов $n$. Докажите, что множество векторов, которые являются корректными кодами Хемминга образуют множество решений системы линейных уравнений $Ax=0$ для некоторой матрицы $A$, все вычисления происходят по модулю $2$.
	# Получение кода Хемминда умножением на матрицу. Зафиксируем количество информационных битов $n$. Докажите, что существует матрица $A$, такая что если $y$ это код Хемминга для строки $x$, то $y=Ax$.		# Получение кода Хемминда умножением на матрицу. Зафиксируем количество информационных битов $n$. Докажите, что существует матрица $A$, такая что если $y$ это код Хемминга для строки $x$, то $y=Ax$.
		+	# Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
		+	# Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
		+	# Докажите, что $g_{i \oplus j} = g_i \oplus g_j$.
		+	# Выведите формулу, которая по кодовому слову возвращает его позицию в зеркальном коде Грея (аналог формулы из задания 128)
		+	# Разработайте код Грея для $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$. Докажите, что существует монотонный код Грея
		+	# Сколько существует векторов длины $n + 1$, содержащих каждое число от $1$ до $n$ хотя бы по одному разу?
		+	# Выведите рекуррентную формулу для числа комбинаторных объектов: вектор длины $2n$, в котором каждое число от $1$ до $n$ встречается ровно два раза.
		+	# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
		+	# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
		+	# Коды Грея для размещений. Предложите способ перечисления размещений, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
		+	# Докажите, что существует способ упорядочить все двоичные вектора длины $n$, чтобы любые два соседних отличались в не более, чем двух позициях, а количество единиц в $i$-м векторе не превосходило количество единиц в $j$-м векторе при $i < j$.

← Предыдущая		Версия 19:20, 3 ноября 2023
Строка 142:		Строка 142:
	# Предложите реализацию преобразования Move to Front за $O(n \log n)$.		# Предложите реализацию преобразования Move to Front за $O(n \log n)$.
	# Предложите реализацию преобразования Move to Front за $O(n)$.		# Предложите реализацию преобразования Move to Front за $O(n)$.
		+	# Докажите, что при оптимальном кодировании с помощью LZ не выгодно делать повтор блока, который можно увеличить вправо
		+	# Разработайте алгоритм оптимального кодирования текста с помощью LZ, если на символ уходит $c$ бит, а на блок повтора $d$ бит
		+	# Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
		+	# Изучите фонетический алфавит ИКАО. Какое среднее взвешенное число символов при передаче одной буквы (вероятности символов считали в позапрошлом ДЗ).
		+	# Какое минимальное расстояние Хемминга между двумя последовательностями звуков русского языка для символа в фонетическом алфавите ИКАО (при сравнении слов разной длины считайте, что символы более длинного слова с номерами большими длины более короткого дают вклад +1). Хороший ли показатель в данном случае расстояние Хемминга? Какая самая неудачная пара слов в фонетическом алфавите ИКАО?
		+	# Изучите коды ISBN-10 и ISBN-13. Докажите, что они находят одну ошибку в десятичной системе счисления.
		+	# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
		+	# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n>n_0$)
		+	# Испорченный символ. Пусть вместо замены на противополжный символ портится, то есть при приеме вместо некоторых символов принимается неопределенность ""?"". Как изменятся определения и параметры кодов обнаруживающих и исправляющих $d$ ошибок в этом случае?
		+	# Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: удаление одного бита, замена одного бита на противоположный. Таким образом, при отправке сообщения длины $l$ может быть получено либо сообщение длины $l$, в котором не более одного бита исправлено на противоположный, либо сообщение длины $l - 1$, в котором все биты верные, но одного бита, неизвестно, какого, не хватает.
		+	# Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: добавление одного бита, замена одного бита на противоположный. Таким образом, при отправке сообщения длины $l$ может быть получено либо сообщение длины $l$, в котором не более одного бита исправлено на противоположный, либо сообщение длины $l + 1$, в котором все биты верные, а также добавлен еще один, неизвестно, какой, бит.
		+	# Разработайте оптимальный код, исправляющий одну ошибку при пересылке сообщения из 3 битов, где возможны следующие ошибки: обмен местами двух соседних битов.
		+	# Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую непустую двоичную строку длиной не больше $n$ сжать, чтобы её размер уменьшился хотя бы на один символ?
		+	# Кодирование с ошибками. Пусть разрешается при декодировании неверно раскодировать не более одного бита. Можно ли каждую двоичную строку длиной от 2 до $n$ сжать, чтобы её размер уменьшился хотя бы на два символа?
		+	# Линейность кода Хемминга. Зафиксируем количество информационных битов $n$. Докажите, что множество векторов, которые являются корректными кодами Хемминга образуют множество решений системы линейных уравнений $Ax=0$ для некоторой матрицы $A$, все вычисления происходят по модулю $2$.
		+	# Получение кода Хемминда умножением на матрицу. Зафиксируем количество информационных битов $n$. Докажите, что существует матрица $A$, такая что если $y$ это код Хемминга для строки $x$, то $y=Ax$.

@@ Строка 136: / Строка 136: @@
 # Проанализируйте время работы алгоритма арифметического кодирования (с учетом длинной арифметики).
 # Троичное арифметическое кодирование. Пусть при арифметичском кодировании мы используем в качестве знаменателя не $2^q$, а $3^q$, а числитель записываем как троичное число, дополненное ведущими нулями до длины $q$. Затем запишем числитель в двоичной записи, а ведущие нули заменим на нули в двоичной записи. Приведите пример строки, когда описанный метод через степени тройки будет лучше классического арифметического кодирования.
-# Приведите пример строки, когда метод из предыдущего задания будет хуже классического арифметического кодирования. # Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
+# Приведите пример строки, когда метод из предыдущего задания будет хуже классического арифметического кодирования.
 # Предложите алгоритм декодирования кода Барроуза-Уиллера.
 # Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
 # Предложите реализацию преобразования Move to Front за $O(n \log n)$.
 # Предложите реализацию преобразования Move to Front за $O(n)$.

← Предыдущая		Версия 18:40, 25 октября 2023
Строка 124:		Строка 124:
	# Предложите алгоритм проверки того, что заданный двоичный код является однозначно декодируемым. Алгоритм должен работать за полином от суммы длин кодовых слов.		# Предложите алгоритм проверки того, что заданный двоичный код является однозначно декодируемым. Алгоритм должен работать за полином от суммы длин кодовых слов.
	# Обобщите алгоритм Хаффмана для ""сжатых"" алфавитов, заданных в следующем виде: дано $n$ пар $(k_i, f_i)$, означающих, что в алфавите присутствует $k_i$ символов с частотой $f_i$. Придумайте, как за полиномиальное время найти длину кода Хаффмана для такого алфавита и оцените время работы алгоритма.		# Обобщите алгоритм Хаффмана для ""сжатых"" алфавитов, заданных в следующем виде: дано $n$ пар $(k_i, f_i)$, означающих, что в алфавите присутствует $k_i$ символов с частотой $f_i$. Придумайте, как за полиномиальное время найти длину кода Хаффмана для такого алфавита и оцените время работы алгоритма.
		+	# Верно ли, что если длины кодовых слов некоторого кода удовлетворяют неравенству Крафта-МакМиллана, то это код является однозначно декодируемым?
		+	# Приведите пример префиксного кода с длинами кодовых слов $1, 2, 3, \ldots, n-1, n-1$.
		+	# Приведите пример префиксного кода с длинами кодовых слов $1, 3, 3, 5, 5, 5, 5, \ldots$ (слов длины $2i+1$ будет $2^i$ для $i$ от 1 до $k$).
		+	# Петя утверждает, что он разработал однозначно декодируемый код $c$, в котором для каждой строки $x$ длина её кода $c(x)$ не больше длины $x$, а хотя бы для одной длина кода строго меньше. Прокомментируйте результат Пети.
		+	# Вася утверждает, что он разработал однозначно декодируемый код $c$, в котором для некоторого $n$ хотя бы для половины строк $x$ длины не больше $n$ длина кода $c(x)$ строго меньше длины $x$. Прокомментируйте результат Васи.
		+	# Пусть вероятности символов упорядочены по убыванию ($p_1 \ge p_2 \ge \ldots \ge p_n$) и являются дробями, у которых числитель 1, а знаменатель - степень двойки. Что можно сказать про арифметическое кодирование в этом случае?
		+	# Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в среднем тратит в $c$ раз меньше бит на символ строки, чем код Хаффмана.
		+	# При арифметическом кодировании может повезти и у достаточно длинной строки код получится коротким, хотя длина строки большая, и оценка на длину кода тоже большая. Приведите пример такой строки.
		+	# Для предыдущего задания приведите пример бесконечной последовательности строк возрастающей длины, для которых проявляется описанный эффект.
		+	# При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
		+	# Проанализируйте время работы алгоритма арифметического кодирования (с учетом длинной арифметики).
		+	# Троичное арифметическое кодирование. Пусть при арифметичском кодировании мы используем в качестве знаменателя не $2^q$, а $3^q$, а числитель записываем как троичное число, дополненное ведущими нулями до длины $q$. Затем запишем числитель в двоичной записи, а ведущие нули заменим на нули в двоичной записи. Приведите пример строки, когда описанный метод через степени тройки будет лучше классического арифметического кодирования.
		+	# Приведите пример строки, когда метод из предыдущего задания будет хуже классического арифметического кодирования. # Предложите алгоритм построения оптимального кода среди префиксных кодов с длиной кодового слова не более L бит
		+	# Предложите алгоритм декодирования кода Барроуза-Уиллера.
		+	# Предложите алгоритм декодирования кода Барроуза-Уиллера за $O(n)$.
		+	# Предложите реализацию преобразования Move to Front за $O(n \log n)$.
		+	# Предложите реализацию преобразования Move to Front за $O(n)$.

← Предыдущая		Версия 11:53, 19 октября 2023
Строка 106:		Строка 106:
	# Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.		# Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.
	# Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.дешифратора.		# Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.дешифратора.
		+	# Найдите в интернете частоты букв в английских текстах и постройте код Хаффмана для этих частот. Придумайте, как продемонстрировать результат и сравните получившийся код с кодом постоянной длины.
		+	# Найдите в интернете частоты букв в русских текстах и постройте код Хаффмана для этих частот. Придумайте, как продемонстрировать результат и сравните получившийся код с кодом постоянной длины.
		+	# Возьмите большой несжатый файл (например, изображение .bmp) и посчитайте частоты всех возможных 256 байтов в этом файле. Постройте код Хаффмана для этих частот
		+	# Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
		+	# Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
		+	# Докажите, что если размер алфавита - степень двойки и частоты никаких двух символов не отличаются в 2 или более раз, то код Хаффмана не лучше кода постоянной длины
		+	# Модифицируйте алгоритм Хаффмана, чтобы строить $k$-ичные префиксные коды (коды, использующие алфавит не из двух символов, а из $k \ge 2$). Докажите корректность.
		+	# Укажите, как построить дерево Хаффмана за $O(n)$, если символы уже отсортированы по частоте
		+	# Предложите способ хранения информации об оптимальном префиксном бинарном коде для n-символьного алфавита, использующий не более $2n - 1 + n \lceil\log_2(n)\rceil$ бит ($\lceil x\rceil$ - округление $x$ вверх)
		+	# Приведите пример однозначно декодируемого бинарного кода оптимальной длины, который не является ни префиксным, ни развернутым префиксным (после разворота всех слов он тоже не становится префиксным)
		+	# Для каких префиксных кодов существует строка, для которой он является кодом Хаффмана? Предложите алгоритм построения такой строки.
		+	# Дан набор частот $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$.
		+	# Обозначим $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$.
		+	# Пусть заданы пары $(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. Приведите пример текста, для которого код Шеннона-Фано хуже кода Хаффмана.
		+	# Предложите алгоритм проверки того, что заданный двоичный код является однозначно декодируемым. Алгоритм должен работать за полином от суммы длин кодовых слов.
		+	# Обобщите алгоритм Хаффмана для ""сжатых"" алфавитов, заданных в следующем виде: дано $n$ пар $(k_i, f_i)$, означающих, что в алфавите присутствует $k_i$ символов с частотой $f_i$. Придумайте, как за полиномиальное время найти длину кода Хаффмана для такого алфавита и оцените время работы алгоритма.

← Предыдущая		Версия 14:50, 11 октября 2023
Строка 89:		Строка 89:
	# Можно ли выразить медиану трех через медиану пяти?		# Можно ли выразить медиану трех через медиану пяти?
	# Будем называть длиной ДНФ количество вхождений перменных в нее. Например, $(x\wedge y)\vee (\neg x \wedge z)$ имеет длину 4. Постройте ДНФ минимальной длины для функции $x_1 \oplus x_2 \oplus \ldots \oplus x_n$.		# Будем называть длиной ДНФ количество вхождений перменных в нее. Например, $(x\wedge y)\vee (\neg x \wedge z)$ имеет длину 4. Постройте ДНФ минимальной длины для функции $x_1 \oplus x_2 \oplus \ldots \oplus x_n$.
		+	# Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами''). Зафиксируем некоторые значения переменным. Тогда ''замкнутыми'' называются ребра, на которых записана 1, ребра, на которых записан 0, называются ''разомкнутыми''. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций ""и"", ""или"" и ""не"".
		+	# Постройте контактную схему для функции ""xor"".
		+	# Постройте контактную схему для функции медиана трех.
		+	# Докажите, что любую булеву функцию можно представить контактной схемой.
		+	# Постройте контактную схему ""xor от $n$ переменных"", содержащую $O(n)$ ребер.
		+	# Постройте контактную схему ""большинство из $2n+1$ переменных"", содержащую $O(n^2)$ ребер.
		+	# Постройте контактную схему, в которой для каждого из $2^n$ наборов дизъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта дизъюнкция, используя $O(2^n)$ ребер.
		+	# Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
		+	# Приведите пример формулы, которая одновременно (а) равна тождественному нулю (б) находится в форме Хорна (в) находится в форме Крома (г) содержит хотя бы 3 переменные
		+	# Предложите алгоритм, который по заданной своей таблицей истинности $n$-арной булевой функции строит за полином от $2^n$ монотонную булеву функцию, которая одновременно (а) мажорирует заданную на каждом входном наборе (б) имеет минимальное число входных наборов, на которых она равна 1.
		+	# Формулы с кванторами. Рассмотрим формулу с кванторами $Qx_1Qx_2\ldots Qx_n f(x_1, \ldots, x_n)$, где $Q$ может быть квантором ""существует"" или ""для любого"". Докажите, что если если $f(x_1,\ldots,x_n)$ имеет ровно $k$ удовлетворяющих её назначений переменных, то существует ровно $k$ (из $2^n$ возможных) формул с кванторами в указанной форме, которые являются истинными.
		+	# Дана формула в КНФ. Можно каждое вхождение переменной x заменить на её отрицание. Необходимо добиться, чтобы формула после этих преобразований оказалась в форме Хорна. Предложите алгоритм, который сводит эту задачу к задаче 2SAT.
		+	# Свести 3SAT к проверке существования удовлетворяющего назначения для формулы, которая является конъюнкцией клозов, каждый из которых является либо клозом Хорна, либо клозом Крома
		+	# Игра ""два шага вперед, один назад"". Задана булева функция от $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$.
		+	# Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)=x_1\oplus x_2\oplus \ldots\oplus x_n$.
		+	# Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.
		+	# Проанализируйте игру ""два шага вперед, один назад"" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.дешифратора.