Комбинаторная мера

Очевидно, геометрическая мера не учитывает, какими символами заполнено сообщение.

Оценивает возможность представления информации при помощи различных комбинаций информационных элементов в заданном объеме.

Пример 1: Пусть, например, есть автомат, формирующий двузначные десятичные целые положительные числа (исходное множество информационных элементов {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}).

Автомат генерирует размещения:

Числа 34, 43 - из 10 элементов (используются 10 цифр) по 2

с повторениями - 33, 66 из одинаковых цифр.

Можно оценить, сколько различных сообщений (двузначных чисел) может сформировать автомат,

иначе говоря, можно оценить информационную емкость данного устройства: Рп(102) = 102 = 100.

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

Пример 2. Определить емкость ASCII-кода, представленного в двоичной или шестнадцатеричной системе счисления.

ASCII-код – это сообщение, которое формируется как размещение с повторениями:

- для двоичного представления – из информационных элементов {0, 1}, сообщение длиной (объемом) 8 символов;

- для шестнадцатеричного представления – из информационных элементов {0, 1, 2, …., А, В, С, …. F}, сообщение длиной (объемом) 2 символа.

Тогда в соответствии с положениями комбинаторики:

I(двоичное) = РП(2⁸) = 2⁸ = 256;

I(шестнадцатеричное) = РП(16²) = 16² = 256,

где I(двоичное), I(шестнадцатеричное) – количества информации.

Таким образом, емкость ASCII-кода для двоичного и шестнадцатеричного представления одинакова и равна 256

Комбинаторика – раздел дискретной математики, изучающий способы формирования подмножеств из элементов исходных множеств: в соответствии с положениями комбинаторики, из конечного счетного множества элементов мощности h можно сформировать следующие простейшие виды комбинаций элементов:

1. сочетания С, когда элементы исходного множества группируются в подмножества одинаковой мощности l такие, что элементы в них различаются составом, а порядок элементов безразличен. Например, пусть исходное множество имеет вид - {a,b,c} (h=3). Можно сформировать следующие подмножества мощности 2 по правилу сочетаний: {a,b}, {a,c}, {b,c}. В соответствии с определением сочетания множества {a,b} и {b,a} являются идентичными и не формируются.

2. перестановки П, когда элементы исходного множества группируются в подмножества одинаковой мощности l (l = h) такие, что элементы в них различаются только порядком. Например, из исходного множества {a,b,c} (h=3) можно сформировать подмножества по правилу перестановок: {a,b,c}, {b,c,a}, {a,c,b}, {b,a,c}, {c,a,b}, {c,b,a}.

3. размещения Р, когда элементы исходного множества группируются в подмножества одинаковой мощности l, такие, что элементы в них различаются и составом, и порядком. Например, из исходного множества {a,b,c} (h=3) можно сформировать следующие подмножества по правилу размещения: {a,b}, {b,a}, {a,c}, {c,a}, {b,c}, {c,b}.

Дата добавления: 2014-01-06