Изменения
Нет описания правки
# Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
# Докажите корректность следующего алгоритма построения цепного кода. Начинаем со строки из $n$ нулей. Каждый раз пытаемся жадно приписать 1, если слово из последних $n$ символов уже встречалось раньше, то приписываем 0. Заканчиваем, когда все $2^n$ слов получены.
# Докажите, что $\sum_{k=0}^n C_n^k = 2^n$# Докажите, что $\sum_{k=0}^n (-1)^kC_n^k = 0$# Используйте предыдущее задание для альтернативного доказательства формулы включения-исключения: посчитайте для каждого элемента, сколько раз он будет посчитан в правой части формулы.# Предложите алгоритм получения по перестановке ее таблицы инверсий за $O(n \log n)$.# Предложите алгоритм получения перестановке по ее таблице инверсий.# Предложите алгоритм получения перестановки по ее таблице инверсий за $O(n \log n)$.# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.# Коды Грея для размещений. Предложите способ перечисления сочетаний, в котором соседние размещения отличаются заменой одного элемента в одной позиции.# Чему равно число перестановок с заданным циклическим классом?# Степенью перестановки $\pi$ называется минимальное $k$, такое что $\pi^k=i$, где $i$ - тождественная перестановка. Как связана степень перестановки с ее циклическим классом?# Предложите алгоритм поиска перестановки из $n$ элементов с максимальной степенью за $O(n^3)$.# Максимумом в перестановке называется элемент, который больше своих соседей (одного, если он первый или последний, обоих иначе). Выведите рекуррентную формулу для числа перестановок $n$ элементами с $k$ максимумами# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками# Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?
</wikitex>
