244
правки
Изменения
Нет описания правки
# Троичное арифметическое кодирование. Пусть при арифметичском кодировании мы используем в качестве знаменателя не $2^q$, а $3^q$, а числитель записываем как троичное число, дополненное ведущими нулями до длины $q$. Затем запишем числитель в двоичной записи, а ведущие нули заменим на нули в двоичной записи. Приведите пример строки, когда описанный метод через степени тройки будет лучше классического арифметического кодирования.
# Приведите пример строки, когда такой метод будет хуже классического арифметического кодирования.
# Факториальная система счисления. Рассмотрим систему счисленияДокажите, где бесконечно много цифрчто в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$# Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$-м разряде (нумерация разрядов меняется тот же бит, который меняется с 0 на 1 при переходе от младшего к старшему) разрешается использовать цифры от 0 до $i$, вес к $i+1$-го разряда # Докажите, что $g_{i!\oplus j} = g_i \oplus g_j$. Докажите# Выведите формулу, что у каждого положительного числа ровно одно представление которая по кодовому слову возвращает его позицию в факториальной системе счисления зеркальном коде Грея (с точностью до ведущих нулейаналог формулы из задания 128). Предложите алгоритм перевода числа в факториальную систему счисления.# Как связана факториальная система счисления и нумерация перестановок?Разработайте код Грея для $k$-ичных векторов# Фибоначчиева система счисления. Рассмотрим систему счисленияПри каких $a_1, где есть две цифрыa_2, 0 и 1. Пусть нумерация разрядов ведется с 1 от младшего к старшему.., вес a_n$iсуществует обход гиперпараллелепипеда $-го разряда a_1 \times a_2 \times ... \times a_n$F_i, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?# При каких $a_1, a_2, ..., где a_n$F_iсуществует обход гиперпараллелепипеда $ - $i$-е число Фибоначчи ($F_0 = 1a_1 \times a_2 \times ... \times a_n$, $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}$.существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк# ДокажитеКод Грея назвается монотонным, что если нет таких слов $g_i$ и $\sum\limits_{k=0}^n {k \choose m}={n+1 \choose m+1}g_j$.# Докажите, что $\sum\limits_{k=0}^n {m+k \choose k}={m+n+1 \choose n}i < j$.# Докажите, что а $\sum\limits_{k=0}^n {r \choose k}{s \choose n - k}={r+s \choose n}g_i$.# Докажитесодержит на 2 или больше единиц больше, что чем $\sum\limits_{k=0}^m {r \choose k}\left(\frac{r}{2} - k\right)=\frac{m+1}{2}{r \choose m+1}g_j$. // ЗабавноДокажите, что нет простого выражения для $\sum\limits_{k=0}^m {r \choose k}$.существует монотонный код Грея# Обобщите формулу бинома Ньютона на степень суммы трёх: Сколько существует векторов длины $(xn +y+z)^n=?1$# Докажите, что содержащих каждое число от $1$ до $\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}2n$# Докажите, что в котором каждое число от $\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 $, чтобы любые два соседних отличались в не более, чем двух позициях, а количество единиц в $i$- k \choose k} = F_nм векторе не превосходило количество единиц в $j$ (-м векторе при $ni < j$-е число Фибоначчи).
