4. Информационные системы и базы данных

5. Базовые информационные технологии

ПРАКТИЧЕСКИЕ РАБОТЫ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ

1. КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ

1.1. Цель работы

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

1.2. Основные теоретические сведения

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

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

Вероятностью случайного события A называется отношение числа n исходов опыта, в которых это событие произошло, к общему числу N исходов этого опыта:

.

Из приведенного определения следует, что вероятность p может принимать значения в интервале от 0 до 1:

• если p_A = 0, то событие A является невозможным;

• если p_A = 1, то событие A является неизбежным;

• если 0 < p_A < 1, то событие A является случайным.

Например, в сообщении «мама мыла раму маша ела кашу», состоящем из 28 символов (включая пробел), буква «а» встречается 8 раз. Следовательно, вероятность появления буквы «а» в указанном сообщении будет:

p = 8 / 28 ≈ 0,286.

При определении количества информации в сообщении вероятностный подход предполагает, что существует источник сообщений, который может в каждый момент времени случайным образом передавать один символ из своего алфавита (рис. 1.1). В теории информации такой источник называют дискретным источником сообщений.

Рис. 1.1. Передача сообщений от источника к получателю

Дискретный источник сообщений в общем случае характеризуется ансамблем S, то есть алфавитом своих символов с вероятностями их появления, составляющими в сумме единицу:

; причем ;

где m – размер алфавита.

Важным является вопрос о том, сколько информации поступает при приеме одного из символов алфавита источника. Путем несложных рассуждений можно доказать (см. материал лекции «Информация, ее виды и свойства»), что количество информации I, переносимое одним символом, и вероятность p появления этого символа в сообщении связаны следующей зависимостью:

I = log_а(1/p) = – log_аp;

где основание a логарифма log_аp определяет единицу измерения информации:

• a = 2 → бит;

• a = 10 → дит (хартли);

• a = e ≈ 2,72… → нат.

В теории информации, как и в теории вероятности, принято работать с усредненными характеристиками случайных величин. Если при приеме символа s_i получаем I_i информации, то сколько информации получаем в среднем? Поскольку вероятность получить количество информации I_i равна p_i, то в среднем для каждого символа s_i получим

.

Усредняя по всему алфавиту символов размером m, получим следующую величину

, (бит/символ). (1.1)

Величина H(S) называется энтропией дискретного источника сообщений, задаваемого ансамблем S.

Энтропия дискретного источника сообщений является мерой неопределенности выбора этим источником состояния из ансамбля S и численно равна среднему количеству информации, приходящейся на один символ сообщения.

Пример 1.1. Определение энтропии дискретного источника сообщений

Пусть требуется определить энтропию H(S) дискретного источника сообщений S, алфавит которого состоит из четырех символов s₁, s₂, s₃, s₄. Вероятности появления этих символов в сообщениях соответственно равны p₁ = 0,3, p₂ =0,25, p₃ = 0,1, p₄ = 0,35.

По формуле (1.1) получим:

H(S) = – (0,3∙log₂0,3 + 0,25∙log₂0,25 + 0,1∙log₂0,1 + 0,35∙log₂0,35) = 0,5211 + 0,5000 + 0,3322 + 0,5301 = 1,8834 (бит/символ).

Таким образом, энтропия источника сообщений составляет 1,8834 (бит/символ).

Количество информации в сообщении, состоящем из n символов, может быть найдено по формуле Шеннона:

(бит). (1.2)

Пример 1.2. Определение количества информации в сообщении

Пусть требуется определить количество информации в сообщении «От сессии до сессии живут студенты весело» при отсутствии статистической связи между символами. Дополнительно требуется определить объем информации, занимаемый сообщением, если все символы закодированы в системе Unicode (16 бит).

Количество информации в дискретном сообщении можно найти по формуле Шеннона (1.2). В заданном сообщении вместе с пробелами присутствует 41 символ. С учетом отсутствия связи между символами энтропия русского алфавита (см. примечание к табл. П.2) равна 4,31 бит/символ. Отсюда количество информации будет:

I = 41∙4,31 = 176,71 (бит).

Объем информации, занимаемый сообщением:

V = 41∙16 = 246 (бит).