Теорема – условие однозначности декодирования.

Теорема. Если схема ∑ обладает свойством префикса, то алфавитное кодирование будет взаимно однозначным.

Док-во (от противного).

Предположим, что некоторое слово β ∈ F_∑ A* допускает два разбиения на элементарные коды:

β = β_i1... β_ik = β_j1... β_jl &(Ǝt∀s)[s < t β_is = β_js & β_it ≠ β_jt]

Поскольку β_i1... β_ik = β_j1... β_jl, то (Ǝβ')[β_it = β_jtβ' v β_jt = β_itβ']

одно из слов β_it, β_jt является префиксом другого. Но это противоречит тому, что схема префиксная

VI. Элементы комбинаторики.

2. Подстановки. Группа подстановок. Графическое представление подстановок. Циклы. Постановки и перестановки. Инверсии. Генерация перестановок.

Подстановки.

Подстановки тоже самое, что и перестановки. (гениально)

P (n)=n!

Группа подстановок.

Взаимнооднозначная функция f :X®X называется подстановкой на X.

Если множество X конечно, то можно считать, что X=1..n.

З адание подстановок f : 1..n ® 1..n

П роизведением подстановок f и g называется их суперпозиция f °g

Т ождественная подстановка – это подстановка e, для которой e(x)=x.

О братная подстановка – это обратная функция, которая всегда существует, т.к. подстановка является биекцией.

Теорема. Множество подстановок образует группу относительно операции суперпозиции. Эта группа S _n называется симметрической степени n.

(суперпозиция – ассоциативная операция)

Г рафическое представление подстановок.

Любое подмножество G Í S_n замкнутое относительно суперпозиции

и операции обращения, называют группой перестановок степени n

Циклы.

Ц икл – это последовательность элементов x₀,…,x_k, такая, что

Цикл длины 2 называется транспозицией.

[i,i+1] – транспозиция соседних элементов.

П одстановки и перестановки.

Перестановку (и соответствующую ей подстановку) элементов 1,...,n будем обозначать (a₁,…,a_n), где все a_i – различные числа из диапазона 1..n.

Л юбую перестановку можно представить в виде суперпозиции циклов.

П ерестановка f есть перестановка типа ál₁,…,l_nñ если она содержит в разложении на циклы в точности l_i циклов длины i, i=1,2,…,n. Тип ál₁,…,l_nñ обычно записывается в виде:

(если l_i =0, то опускается).

П ример.

Тип

Инверсии.

Пару áa_i,a_jñ, i < j, называют инверсией перестановки áa₁,…,a_nñ, если a_i>a_j.

Для произвольной перестановки f Î S_n через I( f ) обозначим число ее инверсий.

sgn( f )=(-1)^{I( f )} – знак перестановки.

Перестановка f называется четной, если sgn( f )=1, и нечетной, если sgn( f )=0.

Примеры:

1. Тожд. перестановка (1,…,n) не содержит инверсий и поэтому I(e)=0 и для любого n эта перестановка – четная.

2. Перестановка (n, n-1,…,1) содержит n(n-1)/2 инверсий. Поэтому она четная для n=4k или 4k+1, и нечетной в остальных случаях.

3. f=(2,4,3,5,1). Инверсии: á2,1ñ, á4,3ñ, á4,1ñ, á3,1ñ á5,1ñ. I( f )=5. Нечетная