Комбинаторная мера
Оценивает возможность представления информации при помощи различных комбинаций информационных элементов в заданном объеме. Использует типы комбинаций элементов и соответствующие математические соотношения, которые приводятся в одном из разделов дискретной математики – комбинаторике.
Комбинаторная мера может использоваться для оценки информационных возможностей некоторого автомата, который способен генерировать дискретные сигналы (сообщения) в соответствии с определенным правилом комбинаторики. Пусть, например, есть автомат, формирующий двузначные десятичные целые положительные числа (исходное множество информационных элементов {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}). В соответствии с положениями комбинаторики, данный автомат генерирует размещения (различаются числа, например, 34 и 43) из 10 элементов (используются 10 цифр) по 2 (по условию задачи, формируются двузначные числа) с повторениями (очевидно, возможны числа, состоящие из одинаковых цифр, например, 33). Тогда можно оценить, сколько различных сообщений (двузначных чисел) может сформировать автомат, иначе говоря, можно оценить информационную емкость данного устройства: Рп(102) = 102 = 100.
Комбинаторная мера используется для определения возможностей кодирующих систем, которые широко используются в информационной технике.
Пример 1. Определить емкость ASCII-кода, представленного в двоичной или шестнадцатеричной системе счисления.
ASCII-код – это сообщение, которое формируется как размещение с повторениями:
для двоичного представления – из информационных элементов {0, 1}, сообщение длиной (объемом) 8 символов;
для шестнадцатеричного представления – из информационных элементов {0, 1, 2, …., А, В, С, …. F}, сообщение длиной (объемом) 2 символа.
Тогда в соответствии с положениями комбинаторики:
I(двоичное) = РП(28) = 28 = 256;
I(шестнадцатеричное) = РП(162) = 162 = 256,
где I(двоичное), I(шестнадцатеричное) – количества информации, соответственно, для двоичного и шестнадцатеричного представления ASCII-кода.
Таким образом, емкость ASCII-кода для двоичного и шестнадцатеричного представления одинакова и равна 256.
Следует отметить, что все коды постоянной длины формируются по правилам комбинаторики или их комбинациям.
В случае, когда сообщения формируются как размещения с повторениями из элементов алфавита мощности h и известно количество сообщений М, можно определить требуемый объем сообщения (т.е. его длину l) для того, чтобы в этом объеме представить все сообщения: l = log h М .
Например, есть 4 сообщения – a, b, c, d. Выполняется двоичное кодирование этих сообщений кодом постоянной длины. Для этого требуются 2 двоичных разряда. В самом деле: l = log 2 4 = 2.
Очевидно, комбинаторная мера является развитием геометрической меры, так как помимо длины сообщения учитывает объем исходного алфавита и правила, по которым из его символов строятся сообщения.
Особенностью комбинаторной меры является то, что ею измеряется информация не конкретного сообщения, а всего множества сообщений, которые могут быть получены.
Единицей измерения информации в комбинаторной мере является число комбинаций информационных элементов.
|
Положения комбинаторики, используемые в измерении информации
Комбинаторика – раздел дискретной математики, изучающий способы формирования подмножеств из элементов исходных множеств: в соответствии с положениями комбинаторики, из конечного счетного множества элементов мощности 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}, {b,c,a}, {a,c,b}, {b,a,c}, {c,a,b}, {c,b,a}.
3. размещения Р, когда элементы исходного множества группируются в подмножества одинаковой мощности l, такие, что элементы в них различаются и составом, и порядком. Например, из приведенного выше исходного множества можно сформировать следующие подмножества по правилу размещения: {a,b}, {b,a}, {a,c}, {c,a}, {b,c}, {c,b}.
Помимо указанных способов, возможны их модификации, когда элементы в результирующих подмножествах могут повторяться (тогда указанные соотношения между l и h не выполняются). В этом случае говорят о группировании элементов с повторениями, причем для перестановки указывается, сколько раз повторяется в результирующем подмножестве каждый элемент. Так, получаем следующие результаты для примера исходного множества:
Комбинаторика позволяет для каждого из указанных способов группирования элементов рассчитывать число получаемых подмножеств:
Рассчитаем число получаемых подмножеств элементов для приведенного выше примера. Имеем:
П(3) = 3! = 1*2*3 = 6
Pп(32) = 32 = 9. |
