Комбинаторика. Принцип включения-исключения.

Комбинаторика – это раздел математики, посвященный способам подсчетов числа элементов в конечных множествах.

1. Отрезок натурального ряда – это мн-во, содержащее из n элементов {1,2,..,n}. Обозн. [1;n]_N

2. Если A и B мн-ва и сущ. биективное отображение f:A→B, то |A|=|B|, где |A| - число элементов в мн-ве A.

3. Число элементов пустогомн-ва равно 0.

Аксиома 2. – основной закон комбинаторики.

Отрезок натурального ряда [1;n]_Nнумерует мн-во A, если сущ. биективное отображение отрезка натур.ряда в мн-во A. Если [1;n]_Nнумерует мн-во A, то число элементов мн-ва A равно n. Если сущ. такое число n_A, что число [1;n]_Nнумерует мн-во A, то это мн-во A конечно.

Если A и B конечные непересекающиеся мн-ва, тогда: |AUB|=|A|+|B|

Если A и B конечныемн-ва, то |AUB|=|A|+|B|-|A∩B|

Правило включения-исключения: Пусть a₁,a₂,…,a_n – конечные мн-ва, тогда |A₁UA₂U…UA_n|=|A₁|+|A₂|+…+|A_n|-|A₁∩A₂|-…-|A₁∩A_n|-|A₂∩A₃|-…-|A₂∩A_n|-…-|A_n-1∩A_n|+|A₁A₂A₃|+…+|A_n-2∩ A_n-1∩ A_n|-…+(-1)^n-1| A₁∩ A₂∩…∩A_n|

Алфавитное кодирование.

Пусть заданны 2 конечных алфавита А=(а₁,..,а_r) ,B=(b₁,…,b_q).Набор Аназ-ся кодируемым алфавитом. Набор Bназ-ся кодирующий алфавитом. Конечная последовательность символов из А наз-ся символом в алфавите А, мн-во всех слов в алфавите А обозн-сяS(A) ан-но ,мно-во всех слов в алфавите Bобозн-сяS(B).Однозн-ое отображение произвольного подмн-ваM в S(A)на подм-во С в S(B)наз-ся кодирование. При этом слова из мн-ва М наз-ся сообщениями, а их образы – кодами сообщений , таким образом мн-во С явл-ся кодом сообщ-ий М. Код С наз-ся взаимно однозначным или однозначно декадируемым если каждый код сообщения явл-ся кодом ровно одного сообщения , т.е. М={m₁,m₂,m₃}; C={c₁,c₂,c₃}. Допустим что необходимо зак-тьнек-ое , т.е. посл-ть букв алфавита А , нек-уюпосл-тью букв из B , для этого зашифровывают каждую букву а_i кодирующим словом b_iназ-мым элементарным кодом , тогда схема E={a₁↔b₁,a₂↔b₂,a₃↔b₃,…,a_r↔b_r} наз-ся схемой алфавитного кодирования, эту же схему можно записать иначе С={B₁,B₂,B₃,…,B_r}. Рассмотрим процесс кодирования важно учитывать и рассмотрения обратного процесса декадирования . Например: дан код C={0,01}, тогда первой букве в алфавите Аасопоставл-ся кодовое слово 0, а второй 01, r=q=2. Выбирая из закодир-го сообщения посл-ти , где за 0 сразу следует 1 , любую посл-ть в которой не встр-ся подряд 2-ух ед-иц можно декадировать однозначно. Кодовое слово B можно разбить на 2 части B=B’B’’, тогда B’-наз-ся префиксом ,B’’- суффиксом слова B.В кач-ве префиксов и суфф-ов может выступать постое слово и само слово Bназ-ся собственным , длинной слова наз-ся число букв в нем . Говорят что схема кодирования или просто код обл-етсв-ом префф-са , если ни один элем-ый код не явл-сяпреф-ом ни какого другого эл-гокода.Код С облад-ийсв-ом префикса наз-ют префиксным кодом , вып-ие этого св-ва гарантирует однозначность декадирования.

Кодирование с минимальной избыточностью.

Пусть заданы алфавиты А={а1,а2…аr} и В={в1,в2…вq}

Задан набор вероятности Р={р1,р2…рr} появления символов а1,а2…аr.

Сумма вероятностей å Рi=1, i=1..r. (1)

Обозначим за С алфавитный префиксный код. С={w1,w2…wr} в алфавите В такой, что каждое слово wiÎС и является кодом символа ai принадлежащего А. Тогда Li обозначим длину слова wi.

Li=|wi| (2)

Исходя из (1) и (2) можно определить L среднее и математическое ожидание длины слова.

Lср= åPi*Li

Lср- среднестатистическая длина слова в коде С. Эта же величина называется избыточностью кода С.

Средняя длина может меняться при переходе от одной схемы алфавита к другой.

Введем величину L^*(Р)=infLср(С,Р).

L^*(Р)-нижняя грань средней длины слова по всем схемам.

Lср(С,Р)= L^*(Р)

(Р,q) оптимальный код, гдeq-min избыточность для набора вероятностей Р.

При построении кодов по алгоритму Хаффмена вида (Р,2) справедливы следующие утверждения:

1. Среди кодовых слов max длины L оптимального (Р,2) кода найдутся 2 слова имеющие один и тот же префикс длиной L-1.

2. Если словам wi и wj соответствуют вероятности Pi и Pj причем Pi>Pj, то L(wi)<=L(wj).

3. Теорема редукции.

Пусть С={w1,w2…wr}-это код имеющий r слов, при том С-двоичный код Р={р1,р2…рr}

р1>=p2>=…pr, pi>0, åРi=1, i=1..r.

Пусть слова wi и wj, имеющие max длину и соответствующие вероятности Pi и Pj и обладающие одинаковыми префиксами длиной L-1.

Пусть Р’= Pi+ Pj тогда новое распределение вероятностей будет иметь вид:

Р={p1,p2…p’…p_i-1,p_i+1…p_j-1,p_j+1…pr} и å Рi=1, i=1..r-1.

Код С’ новый С’=(СÈ{w}) (wi,wj) является (Р’,2) оптимальным т. и т.т.к. исходный код С(Р,2)ÛС(Р’,2)

Всякому префиксному коду С в q-значномалфавитеВ с заданным набором вероятностей Р можно совоставить помеченное дерево D(C,P,q) называемое деревом кода С, следующим образом:

Каждому кодовому слову сопоставлена всяческая вершина , каждому соответствующему префиксу внутренняя вершина, причем одинаковый префикс разных кодовых слов сопоставляется одна и та же внутренняя вершина. Пустому префиксу – Л- считается корнем дерева. U и V соединенный ребра, помечаются меткой в если вÎВ. Кольцевые или висячие вершины будут иметь вероятность, соответствующую кодовым словам.

Непомеченное дерево получается из исходного с помощью убирания меток называется оставным деревом кода С .

Дерево называется оптимальным, если оно соответствует оптимальному. (Р,q) значного кода порядком ветвления вершины в дереве называется число ребер инцидентных этой вершине.

Вершина принадлежащая к-ому ярусу является к-ой вершиной корня дерева. Считается, что ребро, принадлежит к-ому ярусу , если оно соединяет вершины к-го и к+1 яруса.

(r, q) – насыщенные, если порядок ветвления всех его вершин, за исключением одной , лежит в последнем ярусе = 0 или q . Порядок ветвления этой вершины будет находиться числом q0= системе: q-1, если r/q-1ÎR или r-(r/q-1)*(q-1)в остальных случаях.

Кодирование с минимальной избыточностью. Алгоритм Хаффмена.

Алгоритм Хаффмена.

Пусть А={1,2,3,4,5,6}и В={0,1}. r=6, q=2.

Распределим вероятности Р=(0,4;0,3;0,1;0,1;0,05;0,05). å Рi=1

Шаг 1. Исключим из набора вероятностей последние 2 вероятности с индексами Рr-1 и Рr.

Шаг 2. Новую вероятность Р’ расположим так, чтобы она была возрастающей.

Шаг 3. Шаг1 и Шаг2 повторять до тех пор , пока не останется набор из двух вероятностей.

Шаг 4. Для полученного набора из двух вероятностей Р⁴(0,6;0,4).Исходя из Утв.2 р1>p2, L1>L2 запишем их в код С⁴=(0,1). Исходя из Утв.3 осуществим переход из С⁴ в С³-расширенный, чем С⁴ , количество слов в котором больше на 1, чем в С⁴ .

Шаг 5. Этот процесс продолжать до тех пор пока не дойдут до оптимального кода С, имеющего исходный Р, количество слов в котором = исходному r=6.

.