Изменения
Нет описания правки
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)
# Перечисление всех $2^n$ двоичных векторов длины $n$ называется кодом Грея, если в нем не повторяются никакие два вектора и любые два соседних вектора отличаются ровно в одном разряде. Докажите по индукции, что для любого $n$ существует код Грея.
# Докажите, что последовательность $g_i = i \oplus \lfloor i / 2\rfloor$ образует код Грея.
# Построим последовательность $g_i$ следующим образом: пусть $g_0 = 0$ и при переходе от $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$. Докажите, что существует монотонный код Грея
# Докажите, что $\sum_{k=0}^n C_n^k = 2^n$
# Докажите, что $\sum_{k=0}^n (-1)^kC_n^k = 0$
# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
# Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?
# Сочетание с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок не важен. Чему равно число сочетаний с повторениями из $n$ по $k$?
</wikitex>
