22. Повторные выборки, сочетания и размещения (с возвращением и без возвращения элементов). Комбинаторные принципы.

    1. выборка k различных элементов из n элементов с упорядочиванием выбранных элементов

- число размещений из N по k

2. выборка k различных элементов из N без упорядочивания

- число сочетаний из N по k

3. выборка k различных элементов из n с возвращением выбранных элементов и их упорядочиванием

- число размещений с повторениями из N по k

4. выборка k различных элементов из n с возвращением выбранных элементов, но без упорядочивания

- число размещений с повторениями из N по k

Комбинаторные принципы:

1. умножения

пример: 25 человек, 18 девушек и 7 парней. Сколько групп можно получить (3 девушки и 2 юношей)?

2. сложения.

Пример: выбрать книгу или диск из 10 книг и 12 дисков можно 10 + 12 = 22 способами.

3. Дополнения

Найти число пятизначных чисел, состоящих из 1,2, …, 9 \0, в которых не менее 2-х раз встречается 7.

Все пятизначные числа

Числа в которых 7 встречается 0 или 1 раз – лишние. и .

Ответ:

23. Биномиальные и полиномиальные коэффициенты, бином Ньютона, треугольник Паскаля. Полиномиальная формула.

– биномиальный коэффициент.

Быстрый способ вычисления биномиального коэффициента – треугольник Паскаля

Свойства биномиального коэффициента:

1. симметричность

2. 

3. 

Полиномиальная формула

– полиномиальный коэффициент

В полиномиальной формуле в правой части количество слагаемых равно

24. Алфавитное кодирование: необходимое и достаточные условия однозначности декодирования, теорема Маркова, алгоритм Маркова.

A={a₁, a₂, …, a_n} – исходный алфавит

B={b₁, b₂, …, b_n} – кодирующий алфавит

КАКОЙ-НИБУДЬ ПРИМЕРЧИК (простая замена какая-нибудь)

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

ПРИМЕРЧИКИ ОДНОЗНАЧНОГО И НЕОДНОЗНАЧНОГО

Равномерной схемой кодирования называется такая схема, у которой все кодовые слова попарно различны и имеют одинаковую длину.

Если схема является равномерной, то она однозначно декодируема.

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

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

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

Любая префиксная или суффиксная схема однозначно декодируема.

Необходимое условие однозначности декодирования.

Для того, чтобы схема была однозначно декодируемой, необходимо, чтобы выполнялось неравенство МакМиллана

Проверка на однозначность декодируемости (на примере):

Кодовые слова: ab, bc, acb, abac, babbc

r=5, q=3

l₁=2

l₂=2

l₃=3

l₄=4

l₅=5

1. Проверяем неравенство МакМиллана

2. Не префиксная, не суффиксная

3. Алгоритм Маркова

   1. Анализ кодовых слов, разбиение на префиксы и суффиксы.

ab: a b

bc: b c

acb: a cb=ac b

abac: a bac=ab ac=aba c=^ aba c

babbc: b abbc=ba bbc=bab bc=babb c=bab bc ^

Префикс и суффикс не должны быть кодовым словом. Префикс и суффикс должны быть единственными, могут быть пустыми. Корень – кодовое слово или последовательность кодовых слов.

2. Построение графа G_∑

S – множество таких фрагментов кодовых слов, которые являются и суффиксами, и префиксами одновременно.

S={b,ac,^}

3. Поиск ориентированных циклов в графе

Схема является однозначно декодируемой тогда и только тогда, когда в графе нет ориентированных циклов, проходящих через вершину ^.

ВЫВОД: проверяемая схема ∑ не является однозначно декодируемой.

Теорема Маркова.

– множество всех слов, которые получается кодированием из W(A,N) схемой ∑.

- множество всех слов в алфавите А, длина которых не превосходит N.

, где r – количество букв в А.

Для любой схемы кодирования ∑ существует параметр N, такой что схема ∑ будет однозначно декодируемой тогда и только тогда, когда однозначно декодируемы все слова из множества .

Примечание. Для числа N выполняется неравенство , где Т – максимальное количество кодовых слов, которые могут содержаться внутри другого кодового слова; L – суммарная длина всех кодовых слов.