Оглавление

1. Кодирование конечных множеств

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

Выясним, какой одинаковой наименьшей длины коды нужны, чтобы закодировать все множество . Для этого будем считать длину известной и найдем, сколько имен вообще может существовать такой длины.

Если в имени единиц, а остальные цифр – это нули, то различных между собой имен получится . Учтем еще одно имя, состоящее из одних нулей (), и одно имя, состоящее из одних единиц ().

Значит, количество всех таких имен-кодов равно сумме

.

Отсюда получим: чтобы наша задача была разрешимой, должно выполняться неравенство , а значит, .

Число может не быть целым. Поэтому наименьшая возможная длина двоичного кода для элементов равна или .

Число называется энтропией множества (состоящего из элементов).

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

Естественно, возникает вопрос: что делать в случае бесконечных множеств?

Ни одной конечной длины кодов не хватает, чтобы закодировать бесконечное множество элементов.

Поэтому вместо данного бесконечного множества берется другое конечное множество из элементов, которые можно закодировать, используя коды длины . Число элементов подбирается в зависимости от требуемой точности восстановления элементов множества . Зная эти коды, можно присвоить код любому элементу бесконечного множества с «нужной точностью». Для этого от данного элемента мы переходим к «близкому» к нему элементу , который уже закодирован. Код элемента и служит кодом элемента (с определенной точностью).

Нахождение множества (нужной точности) для заданного множества называется табулированием множества .

Однако не для всякого бесконечного множества эту схему кодирования элементов множества возможно реализовать. Разрешимость задачи зависит от определенных свойств, которыми должно обладать рассматриваемое множество. Перейдем к изучению этих свойств, которые вместе принято называть свойством компактности множеств.