Тема 1_Информатика Информация

Кафедра

информатики Энтропийный подход к измерению информации

УГАТУ

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

Количественную оценку информации как исчезнувшей неопределенности можно выразить формулой:

I = Hapr – Haps,

где Hapr – априорная энтропия о состоянии системы (до получения сообщения);

Haps – апостериорная энтропия о состоянии системы (после получения сообщения)

61

Кафедра

информатики Энтропийный подход к измерению информации

УГАТУ

В случае, когда после получения сообщения имеющаяся неопределенность снята полностью (получен конкретный результат, т.е. Haps = 0), количество полученной информации совпадает с первоначальной энтропией:

I= Hapr.

Вдальнейшем будет рассматриваться случай, когда Haps = 0

62

Кафедра
информатики Энтропийный подход к измерению информации
			УГАТУ
В 1948 г. американский инженер и математик К. Шеннон
предложил формулу для расчета энтропии системы,
которая имеет N возможных неравновероятных
состояний:		N
		H apr = − ∑ pi log pi ,
		i =1
где pi	– вероятность того, что система находится
	в i-м состоянии;
N – число всевозможных состояний системы.
Поскольку энтропия является количественной мерой
информации, то количество информации I для случая
неравновероятных состояний системы можно вычислить
по формуле Шеннона.
			63
Кафедра		Формула Шеннона
информатики
			УГАТУ
Формула Шеннона для вычисления
количества информации в случае
неравновероятных состояний системы:
		N
		I = − ∑ pi log pi ,
		i =1
		N	1
или		I = ∑ p log
		i	pi
		i =1
			64

Кафедра
информатики Энтропийный подход к измерению информации
				УГАТУ
Если все состояния системы равновероятны, т.е. pi = p = 1
				N
то получим
N		1	log 1 = − N	1 (log 1 − log N ) = log N
I = − ∑ p log p = − N
i	i	N	N	N
i =1
т.е.	I = log N
.
где N – число возможных состояний системы.
Эта формула используется для расчета количества
информации в случае равновероятных состояний системы
				65
Кафедра	Формула Хартли
информатики
				УГАТУ
Эту же формулу для расчета количества информации в
случае равновероятных событий предложил
американский математик Р. Хартли в 1928 году.
Поэтому формулу
	I = log N
называют формулой Хартли.
.
Из формулы Хартли видно, что количество информации
I, заключенное в сообщении и число возможных
состояний системы N будут связаны как:
		N = 2 I
				66

информатики	Единицы измерения информации
Кафедра

УГАТУ

За единицу измерения информации примем такое количество снятой неопределенности, что

N

I = − ∑ pi log pi = 1,

i=1

Впредыдущих формулах нигде не указывалось основание логарифма. Для определения единицы измерения информации необходимо конкретизировать число состояний объекта N и основание логарифма.

67

информатики	Единицы измерения информации
Кафедра

УГАТУ

Если взять число состояний системы N = 2, а в качестве основания логарифма взять 2, тогда получается

	2
	I = − ∑ pi log pi = − p1 log 2 p1 − p2 log 2 p2 = 1 ,
	i =1			1
	Это равенство справедливо, если	p1 = p2	=		, т.е.
	события равновероятны).		2

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

68

Кафедра	Измерение количества информации
информатики
	УГАТУ
Пример. Пусть нам нужно передать информацию об
исходе бросания монеты. До момента бросания
монеты имеется неопределенность исхода данного
события, при этом потенциально возможны два
варианта равновероятных исходов бросания.
Вероятность каждого события р1=р2=0,5.
Любое из двух сообщений о результате бросания
монеты уменьшает неопределенность ровно в два
раза.
Это и есть количество информации в 1 бит.
Действительно, согласно формуле Хартли
	I = log 22 = 1 бит
	69
Кафедра	Измерение количества информации
информатики
	УГАТУ
Пример. Сколько бит информации будет получено при бросании
пирамидки (четыре грани N = 4) и кубика (шесть граней N = 6),
при условии, что пирамидка и кубик симметричны и однородны,
т.е. исходы N событий для них равновероятны.
Решение. Согласно формуле Хартли:
Если N является целой степенью двойки, то расчеты производятся
достаточно просто, в противном случае для вычисления
логарифма следует применять таблицы Брадиса, и количество
информации не будет целым числом.
	70

Кафедра	Измерение количества информации
информатики

УГАТУ

Если система характеризуется двумя параметрами и может находиться в одном из N1 возможных состояний по первому параметру и N2 возможных состояний по второму параметру, то общее количество возможных состояний N=N1×N2. Тогда количество информации о состоянии системы будет равно:

I = log(N1 N2 ) = log N1 + log N2

Это соотношение является законом аддитивности информации, который справедлив и в том случае, если система характеризуется любым количеством параметров N1, N2, …, Nm:

I = log N1 + log N 2 + K + log N m

71

	Кафедра	Измерение количества информации
	информатики

УГАТУ

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

•Дневная температура выбирается из N1 = 32 возможных для данного сезона,

•Облачность – из N2 = 8 возможных (солнечно, переменная облачность, пасмурно, дождь, облачность с прояснениями, без существенных осадков, небольшой дождь, ураган),

•Направление ветра – из N3 = 8 возможных (южный, северный, восточный, западный, юго-западный, юго- восточный, северо-западный, северо-восточный),

•Скорость ветра – из N4 = 32 возможных.

72

Кафедра		Измерение количества информации
информатики
			УГАТУ
Решение.
Количество возможных прогнозов:
N = N1×N2×N3×N4 = 32×8×8×32=65536.
Тогда, согласно формулы Хартли
		I = log2 65536 = 16 бит
Используя закон аддитивности, эту же задачу можно
решить так:
I = log 2 32 + log2 8 + log2 8 + log2 32 = 5 + 3 + 3 + 5 = 16 бит
			73
Кафедра		Измерение количества информации
информатики
			УГАТУ
Пусть теперь интересующее нас состояние является
	одним из k ≤ N одинаковых. В этом случае, согласно
	закону аддитивности, количество информации
	уменьшится на величину log k:
		I = log N − log k = log N
			k
Пример. В корзине 8 белых грибов и 24 подосиновика.
	Сколько бит информации несет сообщение о том,
	что из корзины достали белый гриб.
			32
		I = log2	= log2 (4) = 2 бита
			8
			74

Кафедра			Связь с теорией вероятности
информатики
											УГАТУ
Формулу Хартли для N равновероятных состояний системы
записать в виде
	=		1
I			, где p – вероятность интересующего нас события
		log
			p
Из теории вероятности известно, что если из общего числа
исходов N какого-то события нас интересует событие, которое
может произойти k раз, то вероятность этого
события p будет равна p = k .
						N
тогда зависимость между вероятностью и										I = log	N
количеством информации в сообщении о											k
нем выражается формулой:										2
											75
Кафедра			Связь с теорией вероятности
информатики
											УГАТУ
Пример. В корзине 8 белых грибов и 24 подосиновика.
	Сколько бит информации несет сообщение о том,
	что из корзины достали белый гриб.
Решение. Вероятность того, что из корзины достали
	белый гриб, равна
			p =	8	= 8 = 1				, тогда
			24 + 8			32	4
			I = log		1	= log			(4) = 2 бита
								2
				2
					p
											76

Кафедра	Связь с теорией вероятности
информатики
	УГАТУ
Качественную связь между вероятностью
некоторого события и количеством
информации в сообщении об этом событии
можно выразить так:
Чем меньше вероятность некоторого
события, тем больше информации
содержит сообщение об этом событии.
	77
Кафедра	Связь с теорией вероятности
информатики
	УГАТУ
Пример. Известно, что в пруду, в основном, водятся караси,
то вероятность поймать именно карася будет больше, чем
вероятность поймать какую-либо другую рыбу. Тогда
количество информации в сообщении о том, что рыбак
поймал карася, будет меньше, чем о том, что рыбак
поймал щуку.
Если известно, что интересующее нас событие обязательно
должно произойти (произойдет с вероятностью 1), то
сообщение о том, что это событие произошло, не несет
никакой информации, и количество информации равно
нулю . Например, сообщение о том, что после красного
сигнала светофора загорится желтый, не несет никакой
информации.
	78

Кафедра
информатики
	Другие единицы измерения информации
	УГАТУ
Минимально возможное количество информации,
содержащееся в сообщении об одном из трех возможных
равновероятных состояний системы (N = 3) (например,
результаты голосования «да», «нет», «воздержался»),
принимается за 1 трит. В этом случае основание
логарифма в приведенных выше формулах равно 3.
Минимально возможное количество информации,
содержащееся в сообщении об одном из десяти
возможных равновероятных состояний системы
(N = 10), принимается за 1 дит. В этом случае основание
логарифма в приведенных выше формулах равно 10.
Если использовать натуральный логарифм, то единица
измерения называется нит или нат. Обычно
употребляется для непрерывных величин.
	79
Кафедра
информатики
	Другие единицы измерения информации
	УГАТУ
Пример. Сколько бит, трит и дит информации будет
получено при выбрасывании одного из 32 одинаковых
шариков с номерами при розыгрыше лотереи.
Решение. Согласно формуле Хартли:
I = log232 = 5 (бит).
I = log332 ≈ 3,155 (трит).
I = log1032 ≈ 1,505 (дит).
	80