Формула шеннона определение. Вероятностный подход к оценке количества информации

Информацио́нная энтропи́я - мера неопределённости некоторой системы (в статистической физике или теории информации), в частности непредсказуемость появления какого-либо символа первичного алфавита . В последнем случае при отсутствии информационных потерь энтропия численно равна количеству информации на символ передаваемого сообщения.

Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n {\displaystyle n} -го порядка, см. ) встречаются очень редко, то неопределённость уменьшается еще сильнее.

Формальные определения

Информационная двоичная энтропия для независимых случайных событий x {\displaystyle x} с n {\displaystyle n} возможными состояниями, распределённых с вероятностями ( i = 1 , . . . , n {\displaystyle i=1,...,n} ), рассчитывается по формуле

H (x) = − ∑ i = 1 n p i log 2 ⁡ p i . {\displaystyle H(x)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}.}

Эта величина также называется средней энтропией сообщения . Величина H i = − log 2 ⁡ p i {\displaystyle H_{i}=-\log _{2}{p_{i}}} называется частной энтропией , характеризующей только i {\displaystyle i} -e состояние. В общем случае основание логарифма в определении энтропии может быть любым, большим 1; его выбор определяет единицу измерения энтропии. Так, зачастую (например, в задачах математической статистики) более удобным может оказаться применение натурального логарифма.

Таким образом, энтропия системы x {\displaystyle x} является суммой с противоположным знаком всех относительных частот появления состояния (события) с номером i {\displaystyle i} , умноженных на их же двоичные логарифмы . Это определение для дискретных случайных событий можно формально расширить для непрерывных распределений, заданных плотностью распределения вероятностей , однако полученный функционал будет обладать несколько иными свойствами (см. дифференциальная энтропия).

Определение по Шеннону

Определение энтропии Шеннона связано с понятием термодинамической энтропии . Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Определение с помощью собственной информации

Также можно определить энтропию случайной величины, введя предварительно понятия распределения случайной величины X {\displaystyle X} , имеющей конечное число значений:

P X (x i) = p i , p i ⩾ 0 , i = 1 , 2 , … , n {\displaystyle P_{X}(x_{i})=p_{i},\quad p_{i}\geqslant 0,\;i=1,\;2,\;\ldots ,\;n} ∑ i = 1 n p i = 1 {\displaystyle \sum _{i=1}^{n}p_{i}=1} I (X) = − log ⁡ P X (X) . {\displaystyle I(X)=-\log P_{X}(X).}

Тогда энтропия определяется как:

H (X) = E (I (X)) = − ∑ i = 1 n p (i) log ⁡ p (i) . {\displaystyle H(X)=E(I(X))=-\sum _{i=1}^{n}p(i)\log p(i).}

Единицы измерения информационной энтропии

От основания логарифма зависит единица измерения количества информации и энтропии: бит , нат , трит или хартли .

Свойства

Энтропия является количеством, определённым в контексте вероятностной модели для . Например, кидание монеты имеет энтропию:

− 2 (1 2 log 2 ⁡ 1 2) = − log 2 ⁡ 1 2 = log 2 ⁡ 2 = 1 {\displaystyle -2\left({\frac {1}{2}}\log _{2}{\frac {1}{2}}\right)=-\log _{2}{\frac {1}{2}}=\log _{2}2=1} бит на одно кидание (при условии его независимости), а количество возможных состояний равно: 2 1 = 2 {\displaystyle 2^{1}=2} возможных состояния (значения) ("орёл" и "решка ").

У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: − ∑ i = 1 ∞ log 2 ⁡ 1 = 0 {\displaystyle -\sum _{i=1}^{\infty }\log _{2}1=0} , а количество возможных состояний равно: 2 0 = 1 {\displaystyle 2^{0}=1} возможное состояние (значение) («А») и от основания логарифма не зависит.
Это тоже информация, которую тоже надо учитывать. Примером запоминающих устройств в которых используются разряды с энтропией равной нулю, но с количеством информации равным 1 возможному состоянию , т.е. не равным нулю, являются разряды данных записанных в ПЗУ , в которых каждый разряд имеет только одно возможное состояние .

Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

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

Математические свойства

  1. Неотрицательность : H (X) ⩾ 0 {\displaystyle H(X)\geqslant 0} .
  2. Ограниченность : H (X) = − E (log 2 ⁡ p i) = ∑ i = 1 n p i log 2 ⁡ 1 p i = ∑ i = 1 n p i f (g i) ⩽ f (∑ i = 1 n p i g i) = log 2 ⁡ n {\displaystyle H(X)=-E(\log _{2}p_{i})=\sum _{i=1}^{n}p_{i}\log _{2}{\frac {1}{p_{i}}}=\sum _{i=1}^{n}p_{i}f(g_{i})\leqslant f\left(\sum _{i=1}^{n}p_{i}g_{i}\right)=\log _{2}n} , что вытекает из неравенства Йенсена для вогнутой функции f (g i) = log 2 ⁡ g i {\displaystyle f(g_{i})=\log _{2}g_{i}} и g i = 1 p i {\displaystyle g_{i}={\frac {1}{p_{i}}}} . Если все n {\displaystyle n} элементов из X {\displaystyle X} равновероятны, H (X) = log 2 ⁡ n {\displaystyle H(X)=\log _{2}n} .
  3. Если независимы, то H (X ⋅ Y) = H (X) + H (Y) {\displaystyle H(X\cdot Y)=H(X)+H(Y)} .
  4. Энтропия - выпуклая вверх функция распределения вероятностей элементов.
  5. Если X , Y {\displaystyle X,\;Y} имеют одинаковое распределение вероятностей элементов, то H (X) = H (Y) {\displaystyle H(X)=H(Y)} .

Эффективность

Алфавит может иметь вероятностное распределение далекое от равномерного . Если исходный алфавит содержит n {\displaystyle n} символов, тогда его можно сравнить с «оптимизированным алфавитом», вероятностное распределение которого равномерное. Соотношение энтропии исходного и оптимизированного алфавита - это эффективность исходного алфавита, которая может быть выражена в процентах. Эффективность исходного алфавита с n {\displaystyle n} символами может быть также определена как его n {\displaystyle n} -арная энтропия.

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически - типичного набора или, на практике, - кодирования Хаффмана , кодирования Лемпеля - Зива - Велча или арифметического кодирования .

Вариации и обобщения

b -арная энтропия

В общем случае b -арная энтропия (где b равно 2, 3, …) источника S = (S , P) {\displaystyle {\mathcal {S}}=(S,\;P)} с исходным алфавитом S = { a 1 , … , a n } {\displaystyle S=\{a_{1},\;\ldots ,\;a_{n}\}} и дискретным распределением вероятности P = { p 1 , … , p n } , {\displaystyle P=\{p_{1},\;\ldots ,\;p_{n}\},} где p i {\displaystyle p_{i}} является вероятностью ( p i = p (a i) {\displaystyle p_{i}=p(a_{i})} ), определяется формулой:

H b (S) = − ∑ i = 1 n p i log b ⁡ p i . {\displaystyle H_{b}({\mathcal {S}})=-\sum _{i=1}^{n}p_{i}\log _{b}p_{i}.}

В частности, при b = 2 {\displaystyle b=2} , мы получаем обычную двоичную энтропию, измеряемую в битах . При b = 3 {\displaystyle b=3} , мы получаем тринарную энтропию, измеряемую в тритах (один трит имеет источник информации с тремя равновероятными состояниями). При b = e {\displaystyle b=e} , мы получаем информацию измеряемую в натах .

Условная энтропия

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия), очевидно, меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть, вероятности двухбуквенных сочетаний):

H 1 (S) = − ∑ i p i ∑ j p i (j) log 2 ⁡ p i (j) , {\displaystyle H_{1}({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}p_{i}(j)\log _{2}p_{i}(j),}

где i {\displaystyle i} - это состояние, зависящее от предшествующего символа, и p i (j) {\displaystyle p_{i}(j)} - это вероятность j {\displaystyle j} при условии, что i {\displaystyle i} был предыдущим символом.

Например, для русского языка без буквы «ё» H 0 = 5 , H 1 = 4,358 , H 2 = 3 , 52 , H 3 = 3 , 01 {\displaystyle H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01} .

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы . Для описания потерь со стороны источника (то есть известен посланный сигнал) рассматривают условную вероятность получения приёмником символа при условии, что был отправлен символ a i {\displaystyle a_{i}} . При этом канальная матрица имеет следующий вид:

b 1 {\displaystyle b_{1}} b 2 {\displaystyle b_{2}} … b j {\displaystyle b_{j}} … b m {\displaystyle b_{m}}
a 1 {\displaystyle a_{1}} p (b 1 ∣ a 1) {\displaystyle p(b_{1}\mid a_{1})} p (b 2 ∣ a 1) {\displaystyle p(b_{2}\mid a_{1})} … p (b j ∣ a 1) {\displaystyle p(b_{j}\mid a_{1})} … p (b m ∣ a 1) {\displaystyle p(b_{m}\mid a_{1})}
a 2 {\displaystyle a_{2}} p (b 1 ∣ a 2) {\displaystyle p(b_{1}\mid a_{2})} p (b 2 ∣ a 2) {\displaystyle p(b_{2}\mid a_{2})} … p (b j ∣ a 2) {\displaystyle p(b_{j}\mid a_{2})} … p (b m ∣ a 2) {\displaystyle p(b_{m}\mid a_{2})}
… … … … … … …
a i {\displaystyle a_{i}} p (b 1 ∣ a i) {\displaystyle p(b_{1}\mid a_{i})} p (b 2 ∣ a i) {\displaystyle p(b_{2}\mid a_{i})} … p (b j ∣ a i) {\displaystyle p(b_{j}\mid a_{i})} … p (b m ∣ a i) {\displaystyle p(b_{m}\mid a_{i})}
… … … … … … …
a m {\displaystyle a_{m}} p (b 1 ∣ a m) {\displaystyle p(b_{1}\mid a_{m})} p (b 2 ∣ a m) {\displaystyle p(b_{2}\mid a_{m})} … p (b j ∣ a m) {\displaystyle p(b_{j}\mid a_{m})} … p (b m ∣ a m) {\displaystyle p(b_{m}\mid a_{m})}

Очевидно, вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый сигнал a i {\displaystyle a_{i}} , описываются через частную условную энтропию:

H (B ∣ a i) = − ∑ j = 1 m p (b j ∣ a i) log 2 ⁡ p (b j ∣ a i) . {\displaystyle H(B\mid a_{i})=-\sum _{j=1}^{m}p(b_{j}\mid a_{i})\log _{2}p(b_{j}\mid a_{i}).}

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

H (B ∣ A) = ∑ i p (a i) H (B ∣ a i) . {\displaystyle H(B\mid A)=\sum _{i}p(a_{i})H(B\mid a_{i}).}

H (B ∣ A) {\displaystyle H(B\mid A)} означает энтропию со стороны источника, аналогично рассматривается H (A ∣ B) {\displaystyle H(A\mid B)} - энтропия со стороны приёмника: вместо p (b j ∣ a i) {\displaystyle p(b_{j}\mid a_{i})} всюду указывается p (a i ∣ b j) {\displaystyle p(a_{i}\mid b_{j})} (суммируя элементы строки можно получить , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).

Взаимная энтропия

Взаимная энтропия или энтропия объединения предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H (A B) {\displaystyle H(AB)} , где A {\displaystyle A} характеризует передатчик, а B {\displaystyle B} - приёмник.

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий , и для полного описания характеристик канала требуется только одна матрица:

p (a 1 b 1) {\displaystyle p(a_{1}b_{1})} p (a 1 b 2) {\displaystyle p(a_{1}b_{2})} … p (a 1 b j) {\displaystyle p(a_{1}b_{j})} … p (a 1 b m) {\displaystyle p(a_{1}b_{m})}
p (a 2 b 1) {\displaystyle p(a_{2}b_{1})} p (a 2 b 2) {\displaystyle p(a_{2}b_{2})} … p (a 2 b j) {\displaystyle p(a_{2}b_{j})} … p (a 2 b m) {\displaystyle p(a_{2}b_{m})}
… … … … … …
p (a i b 1) {\displaystyle p(a_{i}b_{1})} p (a i b 2) {\displaystyle p(a_{i}b_{2})} … p (a i b j) {\displaystyle p(a_{i}b_{j})} … p (a i b m) {\displaystyle p(a_{i}b_{m})}
… … … … … …
p (a m b 1) {\displaystyle p(a_{m}b_{1})} p (a m b 2) {\displaystyle p(a_{m}b_{2})} … p (a m b j) {\displaystyle p(a_{m}b_{j})} … p (a m b m) {\displaystyle p(a_{m}b_{m})}

Для более общего случая, когда описывается не канал, а в целом взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером j {\displaystyle j} даёт p (b j) {\displaystyle p(b_{j})} , сумма строки с номером i {\displaystyle i} есть p (a i) {\displaystyle p(a_{i})} , а сумма всех элементов матрицы равна 1. Совместная вероятность p (a i b j) {\displaystyle p(a_{i}b_{j})} событий a i {\displaystyle a_{i}} и b j {\displaystyle b_{j}} вычисляется как произведение исходной и условной вероятности.

Билет 8

Информацио́нная энтропи́я - мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

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

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

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

Формула Хартли определяет количество информации, содержащееся в сообщении длины n.

Имеется алфавит А, из букв которого составляется сообщение:

Количество возможных вариантов разных сообщений:

где N - возможное количество различных сообщений, шт; m - количество букв в алфавите, шт; n - количество букв в сообщении, шт.

Пример: Алфавит состоит из двух букв «B» и «X», длина сообщения 3 буквы - таким образом, m=2, n=3. При выбранных нами алфавите и длине сообщения можно составить разных сообщений «BBB», «BBX», «BXB», «BXX», «XBB», «XBX», «XXB», «XXX» - других вариантов нет.

Формула Хартли определяется:

где I - количество информации, бит.

При равновероятности символов формула Хартли переходит в собственную информацию.

Формула Хартли была предложена Ральфом Хартли в 1928 году как один из научных подходов к оценке сообщений.

Формула Шеннона

Формулу для вычисления количества информации в случае различных вероятностей событий предложил К. Шеннон в 1948 году. В этом случае количество информации определяется по формуле:

(2.2)

Где I - количество информации;
N - количество возможных событий;
р i - вероятность i-го события.

Например, пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий будут равны:

Р 1 = 1/2, р 2 = 1/4, р 3 = 1/8, р 4 = 1/8.

Билет № 5

Способы кодирования информации.
Одна и та же информация может быть представлена (закодирована) в нескольких формах. C появлением компьютеров возникла необходимость кодирования всех видов информации, с которыми имеет дело и отдельный человек, и человечество в целом. Но решать задачу кодирования информации человечество начало задолго до появления компьютеров. Грандиозные достижения человечества - письменность и арифметика - есть не что иное, как система кодирования речи и числовой информации. Информация никогда не появляется в чистом виде, она всегда как-то представлена, как-то закодирована.
Двоичное кодирование – один из распространенных способов представления информации. В вычислительных машинах, в роботах и станках с числовым программным управлением, как правило, вся информация, с которой имеет дело устройство, кодируется в виде слов двоичного алфавита.
Кодирование символьной (текстовой) информации.
Основная операция, производимая над отдельными символами текста - сравнение символов.
При сравнении символов наиболее важными аспектами являются уникальность кода для каждого символа и длина этого кода, а сам выбор принципа кодирования практически не имеет значения.
Для кодирования текстов используются различные таблицы перекодировки. Важно, чтобы при кодировании и декодировании одного и того же текста использовалась одна и та же таблица.
Таблица перекодировки - таблица, содержащая упорядоченный некоторым образом перечень кодируемых символов, в соответствии с которой происходит преобразование символа в его двоичный код и обратно.
Наиболее популярные таблицы перекодировки: ДКОИ-8, ASCII, CP1251, Unicode.
Исторически сложилось, что в качестве длины кода для кодирования символов было выбрано 8 бит или 1 байт. Поэтому чаще всего одному символу текста, хранимому в компьютере, соответствует один байт памяти.
Различных комбинаций из 0 и 1 при длине кода 8 бит может быть 28 = 256, поэтому с помощью одной таблицы перекодировки можно закодировать не более 256 символов. При длине кода в 2 байта (16 бит) можно закодировать 65536 символов.
Кодирование числовой информации.
Сходство в кодировании числовой и текстовой информации состоит в следующем: чтобы можно было сравнивать данные этого типа, у разных чисел (как и у разных символов) должен быть различный код. Основное отличие числовых данных от символьных заключается в том, что над числами кроме операции сравнения производятся разнообразные математические операции: сложение, умножение, извлечение корня, вычисление логарифма и пр. Правила выполнения этих операций в математике подробно разработаны для чисел, представленных в позиционной системе счисления.
Основной системой счисления для представления чисел в компьютере является двоичная позиционная система счисления.
Кодирование текстовой информации
В настоящее время, большая часть пользователей, при помощи компьютера обрабатывает текстовую информацию, которая состоит из символов: букв, цифр, знаков препинания и др. Подсчитаем, сколько всего символов и какое количество бит нам нужно.
10 цифр, 12 знаков препинания, 15 знаков арифметических действий, буквы русского и латинского алфавита, ВСЕГО: 155 символов, что соответствует 8 бит информации.
Единицы измерения информации.
1 байт = 8 бит
1 Кбайт = 1024 байтам
1 Мбайт = 1024 Кбайтам
1 Гбайт = 1024 Мбайтам
1 Тбайт = 1024 Гбайтам
Суть кодирования заключается в том, что каждому символу ставят в соответствие двоичный код от 00000000 до 11111111 или соответствующий ему десятичный код от 0 до 255.
Необходимо помнить, что в настоящее время для кодировки русских букв используют пять различных кодовых таблиц (КОИ - 8, СР1251, СР866, Мас, ISO), причем тексты, закодированные при помощи одной таблицы не будут правильно отображаться в другой
Основным отображением кодирования символов является код ASCII - American Standard Code for Information Interchange- американский стандартный код обмена информацией, который представляет из себя таблицу 16 на 16, где символы закодированы в шестнадцатеричной системе счисления.
Кодирование графической информации.
Важным этапом кодирования графического изображения является разбиение его на дискретные элементы (дискретизация).
Основными способами представления графики для ее хранения и обработки с помощью компьютера являются растровые и векторные изображения
Векторное изображение представляет собой графический объект, состоящий из элементарных геометрических фигур (чаще всего отрезков и дуг). Положение этих элементарных отрезков определяется координатами точек и величиной радиуса. Для каждой линии указывается двоичные коды типа линии (сплошная, пунктирная, штрихпунктирная), толщины и цвета.
Растровое изображение представляет собой совокупность точек (пикселей), полученных в результате дискретизации изображения в соответствии с матричным принципом.
Матричный принцип кодирования графических изображений заключается в том, что изображение разбивается на заданное количество строк и столбцов. Затем каждый элемент полученной сетки кодируется по выбранному правилу.
Pixel (picture element - элемент рисунка) - минимальная единица изображения, цвет и яркость которой можно задать независимо от остального изображения.
В соответствии с матричным принципом строятся изображения, выводимые на принтер, отображаемые на экране дисплея, получаемые с помощью сканера.
Качество изображения будет тем выше, чем "плотнее" расположены пиксели, то есть чем больше разрешающая способность устройства, и чем точнее закодирован цвет каждого из них.
Для черно-белого изображения код цвета каждого пикселя задается одним битом.
Если рисунок цветной, то для каждой точки задается двоичный код ее цвета.
Поскольку и цвета кодируются в двоичном коде, то если, например, вы хотите использовать 16-цветный рисунок, то для кодирования каждого пикселя вам потребуется 4 бита (16=24), а если есть возможность использовать 16 бит (2 байта) для кодирования цвета одного пикселя, то вы можете передать тогда 216 = 65536 различных цветов. Использование трех байтов (24 битов) для кодирования цвета одной точки позволяет отразить 16777216 (или около 17 миллионов) различных оттенков цвета - так называемый режим “истинного цвета” (True Color). Заметим, что это используемые в настоящее время, но далеко не предельные возможности современных компьютеров.
Кодирование звуковой информации.
Из курса физики вам известно, что звук - это колебания воздуха. По своей природе звук является непрерывным сигналом. Если преобразовать звук в электрический сигнал (например, с помощью микрофона), мы увидим плавно изменяющееся с течением времени напряжение.
Для компьютерной обработки аналоговый сигнал нужно каким-то образом преобразовать в последовательность двоичных чисел, а для этого его необходимо дискретизировать и оцифровать.
Можно поступить следующим образом: измерять амплитуду сигнала через равные промежутки времени и записывать полученные числовые значения в память компьютера.

Билет № 3

В истории развития цивилизации произошло несколько информационных революций - преобразований общественных отношений из-за кардинальных изменений в сфере обработки информации. Следствием подобных преобразований являлось приобретение человеческим обществом нового качества.

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

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

Третья (конец XIX в.) обусловлена изобретением электричества, благодаря которому появились телеграф, телефон, радио, позволяющие оперативно передавать и накапливать информацию в любом объеме.

Четвертая (70-е гг. XX в.) связана с изобретением микропроцессорной технологии и появлением персонального компьютера. На микропроцессорах и интегральных схемах создаются компьютеры, компьютерные сети, системы передачи данных (информационные коммуникации). Этот период характеризуют три фундаментальные инновации:

Переход от механических и электрических средств преобразования информации к

электронным;

Миниатюризация всех узлов, устройств, приборов, машин;

Создание программно-управляемых устройств и процессов.

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

Наиболее яркий пример такого явления и результат пятой революции - Интернет. Суть этой революции заключается в интеграции в едином информационном пространстве по всему миру программно-технических средств, средств связи и телекоммуникаций, информационных запасов или запасов знаний как единой информационной телекоммуникационной инфраструктуры, в которой активно действуют юридические и физические лица, органы государственной власти и местного самоуправления. В итоге неимоверно возрастают скорости и объемы обрабатываемой информации, появляются новые уникальные возможности производства, передачи и распространения информации, поиска и получения информации, новые виды традиционной деятельности в этих сетях.

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

Билет № 11

Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).

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

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

Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.

Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление ). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом , если в нем первая вершина совпадает с последней.

Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).

Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.

Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i , j ), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).

Граф называется связным , если любые две его вершины можно соединить маршрутом (или путем). На рис. 1 изображен связный граф.

Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком .

Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).

Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей , если ее степень равна единице.

Лемма 1 . Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.

Билет №13

Релейно-контактные схемы (их часто называют переключательными схемами) широко используются в технике автоматического управления.

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

1) переключателей , которыми могут быть механические устройства, электромагнитные реле, полупроводники и т.д.;

2) соединяющие их проводники ;

3) входы в схему и выходы из нее (клеммы, на которые подается электрическое напряжение). Они называются полюсами.

Простейшая схема содержит один переключатель Р и имеет один вход А и один выход В . Переключателю Р поставим в соответствии высказывание р , гласящее: - “Переключатель Р замкнут ”. Если р истинно, то импульс, поступающий на полюс А , может быть снят на полюсе В без потери напряжения, то есть схема пропускает ток. Если р ложно, то переключатель разомкнут и схема тока не проводит. Таким образом, если принять во внимание не смысл высказывания, а только его значение, то можно считать, что любому высказыванию может быть поставлена в соответсвие переключательная схема с двумя полюсами (двухполюсная схема).

Тогда РКС для данной формулы имеет вид:

Пример 2. Упростить РКС:

Решение. Составим по данной РКС формулу (функцию проводимости) и упростим ее:

(к последним двум слагаемым применили закон поглощения).

Тогда упрощенная схема выглядит так:

Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N.

Формула Хартли: I = log 2 N или N = 2 i

Допустим, нужно угадать одно число из набора чисел от единицы до ста. По формуле Хартли можно вычислить, какое количество информации для этого требуется: I = log 2 100 > 6,644. Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 единицы информации.

Приведем другие примеры равновероятных сообщений :

1. при бросании монеты: «выпала решка», «выпал орел»;

2. на странице книги: «количество букв чётное», «количество букв нечётное».

Определим теперь, являются ли равновероятными сообщения «первой выйдет из дверей здания женщина» и«первым выйдет из дверей здания мужчина ». Однозначно ответить на этот вопрос нельзя. Все зависит от того, о каком именно здании идет речь. Если это, например, станция метро, то вероятность выйти из дверей первым одинакова для мужчины и женщины, а если это военная казарма, то для мужчины эта вероятность значительно выше, чем для женщины.

Для задач такого рода американский учёный Клод Шеннон предложил в 1948 г. другую формулу определения количества информации, учитывающую возможную неодинаковую вероятность сообщений в наборе .

Формула Шеннона: I = - (p 1 log 2 p 1 + p 2 log 2 p 2 + . . . + p N log 2 p N),

где p i - вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Легко заметить, что если вероятности p 1 , ..., p N равны, то каждая из них равна 1 / N, и формула Шеннона превращается в формулу Хартли.

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

В качестве единицы информации Клод Шеннон предложил принять один бит (англ. bit - binary digit - двоичная цифра).

Бит в теории информации - количество информации, необходимое для различения двух равновероятных сообщений (типа «орел»-«решка», «чет»-«нечет» и т.п.).

В вычислительной технике битом называют наименьшую «порцию» памяти компьютера, необходимую для хранения одного из двух знаков «0» и «1», используемых для внутримашинного представления данных и команд.

Бит - слишком мелкая единица измерения. На практике чаще применяется более крупная единица - байт , равная восьми битам. Именно восемь битов требуется для того, чтобы закодировать любой из 256 символов алфавита клавиатуры компьютера (256=2 8).



Широко используются также ещё более крупные производные единицы информации:

1 Килобайт (Кбайт) = 1024 байт = 210 байт,

1 Мегабайт (Мбайт) = 1024 Кбайт = 220 байт,

1 Гигабайт (Гбайт) = 1024 Мбайт = 230 байт.

В последнее время в связи с увеличением объёмов обрабатываемой информации входят в употребление такие производные единицы, как:

1 Терабайт (Тбайт) = 1024 Гбайт = 240 байт,

1 Петабайт (Пбайт) = 1024 Тбайт = 250 байт.

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

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

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

За единицу количества информации принято такое количество информации, которое мы получаем при уменьшении неопределенности в 2 раза. Такая единица названа бит .

В компьютере информация представлена в двоичном коде или на машинном языке, алфавит которого состоит из двух цифр (0 и 1). Эти цифры можно рассматривать как два равновероятных состояния. При записи одного двоичного разряда реализуется выбор одного из двух возможных состояний (одной из двух цифр) и, следовательно, один двоичный разряд несет количество информации в 1 бит. Два двоичных разряда несут информацию 2 бита, три разряда – 3 бита и т.д.



Поставим теперь обратную задачу и определим: «Какое количество различных двоичных чисел N можно записать с помощью I двоичных разрядов?» С помощью одного двоичного разряда можно записать 2 различных числа (N=2=2 1), с помощью двух двоичных разрядов можно записать четыре двоичных числа (N=4=2 2), с помощью трех двоичных разрядов можно записать восемь двоичных чисел (N=8=2 3) и т.д.

В общем случае количество различных двоичных чисел можно определить по формуле

N – количество возможных событий (равновероятных)!!!;

В математике существует функция, с помощью которой решается показательное уравнение, эта функция называется логарифмом. Решение такого уравнения имеет вид:

Если события равновероятны , то количество информации определяется по данной формуле.

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

,

где I – количество информации;

N – количество возможных событий;

P i – вероятность отдельных событий.

Пример 3.4

В барабане для розыгрыша лотереи находится 32 шара. Сколько информации содержит сообщение о первом выпавшем номере (например, выпал номер 15)?

Решение:

Поскольку вытаскивание любого из 32 шаров равновероятно, то количество информации об одном выпавшем номере находится из уравнения: 2 I =32.

Но 32=2 5 . Следовательно, I=5 бит. Очевидно, ответ не зависит от того, какой именно выпал номер.

Пример 3.5

Какое количество вопросов достаточно задать вашему собеседнику, чтобы наверняка определить месяц, в котором он родился?

Решение:

Будем рассматривать 12 месяцев как 12 возможных событий. Если спрашивать о конкретном месяце рождения, то, возможно, придется задать 11 вопросов (если на 11 первых вопросов был получен отрицательный ответ, то 12-й задавать не обязательно, так как он и будет правильным).

Правильнее задавать «двоичные» вопросы, то есть вопросы, на которые можно ответить только «да» или «нет». Например, «Вы родились во второй половине года?». Каждый такой вопрос разбивает множество вариантов на два подмножества: одно соответствует ответу «да», а другое – ответу «нет».

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

По формуле 2 и с помощью калькулятора получаем:

бита.

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

Пример 3.6

После экзамена по информатике, который сдавали ваши друзья, объявляются оценки («2», «3», «4» или «5»). Какое количество информации будет нести сообщение об оценке учащегося А, который выучил лишь половину билетов, и сообщение об оценке учащегося В, который выучил все билеты.

Решение:

Опыт показывает, что для учащегося А все четыре оценки (события) равновероятны и тогда количество информации, которое несет сообщение об оценке, можно вычислить по формуле (1):

На основании опыта можно также предположить, что для учащегося В наиболее вероятной оценкой является «5» (p 1 =1/2), вероятность оценки «4» в два раза меньше (p 2 =1/4), а вероятности оценок «2» и «3» еще в два раза меньше (p 3 =p 4 =1/8). Так как события неравновероятны, воспользуемся для подсчета количества информации в сообщении формулой 2:

Вычисления показали, что при равновероятных событиях мы получаем большее количество информации, чем при неравновероятных событиях.

Пример 3.7

В непрозрачном мешочке хранятся 10 белых, 20 красных, 30 синих и 40 зеленых шариков. Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика.

Решение:

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

P б =0,1; P к =0,2; P с =0,3; P з =0,4.

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

Для вычисления этого выражения, содержащего логарифмы можно воспользоваться калькулятором. I»1,85 бита.

Пример 3.8

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

I=log 2 256=8 бит=1 байт

Следовательно, для двоичного кодирования 1 символа необходим 1 байт информации или 8 двоичных разрядов.

Какое количество информации содержится, к примеру, в тексте романа «Война и мир», во фресках Рафаэля или в генетическом коде человека? Ответа на эти вопросы наука не даёт и, по всей вероятности, даст не скоро. А возможно ли объективно измерить количество информации? Важнейшим результатом теории информации является следующий вывод:«В определенных, весьма широких условиях можно пренебречь качественными особенностями информации, выразить её количество числом, а также сравнить количество информации, содержащейся в различных группах данных».

В настоящее время получили распространение подходы к определению понятия «количество информации», основанные на том, что информацию, содержащуюся в сообщении, можно нестрого трактовать в смысле её новизны или, иначе, уменьшения неопределённости наших знаний об объекте. Эти подходы используют математические понятия вероятности и логарифма.

В общем случае , энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P : {p 0 , p 1 , …p N -1 } , т.е. H =F (N , P ) . Расчет энтропии в этом случае производится по формуле Шеннона , предложенной им в 1948 году в статье "Математическая теория связи".

В частном случае , когда все варианты равновероятны , остается зависимость только от количества рассматриваемых вариантов, т.е. H =F (N ) . В этом случае формула Шеннона значительно упрощается и совпадает с формулой Хартли , которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, т.е. не 20 лет раньше.

Формула Шеннона имеет следующий вид:

Знак минус в формуле (1) не означает, что энтропия – отрицательная величина. Объясняется это тем, что p i £ 1 по определению, а логарифм числа меньшего единицы - величина отрицательная. По свойству логарифма , поэтому эту формулу можно записать и во втором варианте, без минуса перед знаком суммы.

Интерпретируется как частное количество информации , получаемое в случае реализации i -ого варианта. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины {I 0 , I 1, … I N -1 } .

Приведем пример расчета энтропии по формуле Шеннона. Пусть в некотором учреждении состав работников распределяется так: ¾ - женщины, ¼ - мужчины. Тогда неопределенность, например, относительно того, кого вы встретите первым, зайдя в учреждение, будет рассчитана рядом действий, показанных в таблице 1.

Таблица 1.

p i

1/p i

I i = log 2 (1/p i ), бит

p i *log 2 (1/p i ), бит

log 2 (4/3)=0,42

å

H=0,81 бит

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

Таблица 2.

p i

1/p i

I i = log 2 (1/p i ), бит

p i *log 2 (1/p i ), бит

1 /2

log 2 (2 )=1

1/2 * 1 =1/2

log 2 (2 )=1

1/2 * 1 =1/2

å

H=1 бит

Формула Шеннона (1) совпала по форме с формулой Больцмана, полученной на 70 лет ранее для измерения термодинамической энтропии идеального газа. Эта связь между количеством информации и термодинамической энтропией послужила сначала причиной горячих дискуссий, а затем – ключом к решению ряда научных проблем. В самом общем случае энтропия понимается как мера неупорядоченности, неорганизованности материальных систем .

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

Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I , содержащееся в выбранном сообщении, определял как двоичный логарифм N .

Формула Хартли:

I = log2N.

Допустим, нужно угадать одно число из набора чисел от единицы до ста. По формуле Хартли можно вычислить, какое количество информации для этого требуется: I = log2100 > 6,644. Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 единицы информации.

Приведем другие примеры равновероятных сообщений :

1. при бросании монеты: «выпала решка» , «выпал орел» ;

2. на странице книги: «количество букв чётное» , «количество букв нечётное» .

Определим теперь, являются ли равновероятными сообщения «первой выйдет из дверей здания женщина» и «первым выйдет из дверей здания мужчина» . Однозначно ответить на этот вопрос нельзя . Все зависит от того, о каком именно здании идет речь. Если это, например, станция метро, то вероятность выйти из дверей первым одинакова для мужчины и женщины, а если это военная казарма, то для мужчины эта вероятность значительно выше, чем для женщины.

Для задач такого рода американский учёный Клод Шеннон предложил в 1948 г. другую формулу определения количества информации, учитывающую возможную неодинаковую вероятность сообщений в наборе .

Формула Шеннона:

I = - (p 1log2p 1 + p 2 log2p 2 +... + p N log2pN ),


где pi - вероятность того, что именно i -е сообщение выделено в наборе из N сообщений.

Легко заметить, что если вероятности p 1, ...,pN равны, то каждая из них равна 1/N , и формула Шеннона превращается в формулу Хартли.

Клод Шеннон определил информацию , как снятую неопределенность . Точнее сказать, получение информации - необходимое условие для снятия неопределенности. Неопределенность возникает в ситуации выбора. Задача, которая решается в ходе снятия неопределенности – уменьшение количества рассматриваемых вариантов (уменьшение разнообразия), и в итоге выбор одного соответствующего ситуации варианта из числа возможных. Снятие неопределенности дает возможность принимать обоснованные решения и действовать. В этом управляющая роль информации.

Представьте, что вы зашли в магазин и попросили продать вам жевательную резинку. Продавщица, у которой, скажем, 16 сортов жевательной резинки, находится в состоянии неопределенности. Она не может выполнить вашу просьбу без получения дополнительной информации. Если вы уточнили, скажем, - «Orbit», и из 16 первоначальных вариантов продавщица рассматривает теперь только 8, вы уменьшили ее неопределенность в два раза (забегая вперед, скажем, что уменьшение неопределенности вдвое соответствует получению 1 бита информации ). Если вы, не мудрствуя лукаво, просто указали пальцем на витрине, - «вот эту!», то неопределенность была снята полностью. Опять же, забегая вперед, скажем, что этим жестом в данном примере вы сообщили продавщице 4 бита информации.

Ситуация максимальной неопределенности предполагает наличие нескольких равновероятных альтернатив (вариантов), т.е. ни один из вариантов не является более предпочтительным. Причем, чем больше равновероятных вариантов наблюдается, тем больше неопределенность, тем сложнее сделать однозначный выбор и тем больше информации требуется для этого получить. Для N вариантов эта ситуация описывается следующим распределением вероятностей: {1/N ,1/N , …,1/N }.

Минимальная неопределенность равна 0 , т.е. эта ситуация полной определенности , означающая что выбор сделан, и вся необходимая информация получена. Распределение вероятностей для ситуации полной определенности выглядит так: {1, 0, …0}.

Величина, характеризующая количество неопределенности в теории информации обозначается символом H и имеет название энтропия , точнееинформационная энтропия .

Энтропия (H ) – мера неопределенности , выраженная в битах. Так же энтропию можно рассматривать как меру равномерности распределения случайной величины.

Рис. 3.4 Поведение энтропии для случая двух альтернатив

На рис. 3.4 показано поведение энтропии для случая двух альтернатив, при изменении соотношения их вероятностей (P , (1-P )).

Максимального значения энтропия достигает в данном случае тогда, когда обе вероятности равны между собой и равны 1/2, нулевое значение энтропии соответствует случаям (P 0=0, P 1=1) и (P 0=1, P 1=0).

Количество информации I и энтропия H характеризуют одну и ту же ситуацию, но с качественно противоположенных сторон. I – это количество информации, которое требуется для снятия неопределенности H. По определению Леона Бриллюэна информация есть отрицательная энтропия (негэнтропия ) .

Когда неопределенность снята полностью, количество полученной информации I равно изначально существовавшей неопределенности H .

При частичном снятии неопределенности, полученное количество информации и оставшаяся неснятой неопределенность составляют в сумме исходную неопределенность. Ht + It = H (рис. 3.5).

Рис. 3.5 Связь между энтропией и количеством информации

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

В общем случае , энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P: {p 0,p 1, …,pN- 1}, т.е. H=F (N ,P ). Расчет энтропии в этом случае производится по формуле Шеннона , предложенной им в 1948 году в статье «Математическая теория связи».

В частном случае , когда все варианты равновероятны , остается зависимость только от количества рассматриваемых вариантов, т.е. H=F (N ). В этом случае формула Шеннона значительно упрощается и совпадает с формулой Хартли , которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, т.е. на 20 лет раньше.

Формула Шеннона имеет следующий вид:

Знак минус в формуле (2.1) не означает, что энтропия – отрицательная величина. Объясняется это тем, чтоpi £ 1 по определению, а логарифм числа меньшего единицы - величина отрицательная. По свойству логарифма, поэтому эту формулу можно записать и во втором варианте, без минуса перед знаком суммы.

Выражение интерпретируется как частное количество информации It , получаемое в случае реализации i -ого варианта. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины {I 0,I 1, …,I N- 1}.

Приведем пример расчета энтропии по формуле Шеннона. Пусть в некотором учреждении состав работников распределяется так: 3/4 - женщины, 1/4 - мужчины. Тогда неопределенность, например, относительно того, кого вы встретите первым, зайдя в учреждение, будет рассчитана рядом действий, показанных в табл. 3.1.

Таблица 3.1

pi 1/pi Ii= log2(1/pi ),бит pi* log2(1/pi ),бит
Ж 3/4 4/3 log2(4/3)=0,42 3/4 * 0,42=0,31
М 1/4 4/1 log2(4)=2 1/4 * 2=0,5
å H= 0,81бит

Мы уже упоминали, что формула Хартли – частный случай формулы Шеннона для равновероятных альтернатив.

Подставив в формулу (2.1) вместо pi его (в равновероятном случае не зависящее от i )значение, получим:

Таким образом, формула Хартли выглядит очень просто:

Из нее явно следует, что чем больше количество альтернатив (N ), тем больше неопределенность (H ). Логарифмирование по основанию 2 приводит количество вариантов к единицам измерения информации – битам. На рис.3.6 представлена зависимость энтропии от количества равновероятных вариантов выбора.

Рис. 3.6 Зависимость энтропии от количества равновероятных вариантов выбора (равнозначных альтернатив)

Для решения обратных задач, когда известна неопределенность (H ) или полученное в результате ее снятия количество информации (I ) и нужно определить какое количество равновероятных альтернатив соответствует возникновению этой неопределенности, используют обратную формулу Хартли, которая выглядит еще проще:

Например, если известно, что в результате определения того, что интересующий нас Коля Иванов живет на втором этаже, было получено 3 бита информации, то количество этажей в доме можно определить по формуле (2.3), как N= 23= 8этажей.

Если же вопрос стоит так: «В доме 8 этажей, какое количество информации мы получили, узнав, что интересующий нас Коля Иванов живет на втором этаже?», нужно воспользоваться формулой (2.2): I = log2(8) = 3 бита.

До сих пор мы приводили формулы для расчета энтропии (неопределенности) H , указывая, что H в них можно заменять на I , потому что количество информации, получаемое при полном снятии неопределенности некоторой ситуации, количественно равно начальной энтропии этой ситуации.

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

Для равновероятного случая , используя для расчета энтропии формулу Хартли, получим:

Второе равенство выводится на основании свойств логарифма. Таким образом, в равновероятном случае I зависит от того, во сколько раз изменилось количество рассматриваемых вариантов выбора (рассматриваемое разнообразие).

Исходя из (3.5) можно вывести следующее:

Если, то - полное снятие неопределенности, количество полученной в сообщении информации равно неопределенности, которая существовала до получения сообщения.

Если, то - неопределенности не изменилась, следовательно, информации получено не было.

Если, то => ,

если, то => .

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

Если количество рассматриваемых альтернатив в результате получения сообщения уменьшилось вдвое, т.е., то I =log2(2)=1бит. Другими словами, получение 1 бита информации исключает из рассмотрения половину равнозначных вариантов.

Рассмотрим в качестве примера опыт с колодой из 36 карт (рис.3.7).

Рис. 3.7 Иллюстрация к опыту с колодой из 36-ти карт

Пусть некто вынимает одну карту из колоды. Нас интересует, какую именно из 36 карт он вынул. Изначальная неопределенность, рассчитываемая по формуле (3.2), составляет H= log2(36)@5,17бит . Вытянувший карту сообщает нам часть информации. Используя формулу (3.5), определим, какое количество информации мы получаем из этих сообщений:

Вариант A. “Это карта красной масти”.

I =log2(36/18)=log2(2)=1бит (красных карт в колоде половина, неопределенность уменьшилась в 2 раза).

Вариант B. “Это карта пиковой масти”.

I =log2(36/9)=log2(4)=2 бита (пиковые карты составляют четверть колоды, неопределенность уменьшилась в 4 раза).

Вариант С. “Это одна из старших карт: валет, дама, король или туз”.

I =log2(36)–log2(16)=5,17-4=1,17 бита (неопределенность уменьшилась больше чем в два раза, поэтому полученное количество информации больше одного бита).

Вариант D. “Это одна карта из колоды".

I =log2(36/36)=log2(1)=0 бит (неопределенность не уменьшилась - сообщение не информативно).

Вариант E. “Это дама пик".

I =log2(36/1)=log2(36)=5,17 бит (неопределенность полностью снята).

Задача 1. Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика, если в непрозрачном мешочке находится 50 белых, 25 красных, 25 синих шариков?

Решение .

1) всего шаров 50+25+25=100

2) вероятности шаров 50/100=1/2, 25/100=1/4, 25/100=1/4

3)I = -(1/2 log21/2 + 1/4 log21/4 + 1/4 log21/4) = -(1/2(0-1) +1/4(0-2) +1/4(0-2)) = =1,5 бит

Задача 2. В корзине лежит 16 шаров разного цвета. Сколько информации несет сообщение, что достали белый шар?

Решение . Т.к. N = 16 шаров, то I = log2 N = log2 16 = 4 бит.

Задача 3. В корзине лежат черные и белые шары. Среди них18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?

1) 18 2) 24 3) 36 4)48

Решение . Найдем по формуле Шеннона вероятность получения белого шара: log2N=2, N=4, следовательно, вероятность получения белого шара равна 1/4 (25%), а вероятность получения черного шара соответственно 3/4(75%). Если 75% всех шариков черные, их количество 18, тогда 25% всех шариков белые, их количество (18*25)/75=6.

Осталось найти количество всех шариков в корзине 18+6=24.

Ответ: 24 шарика.

Задача 4. В некоторой стране автомобильный номер длиной 5 символов составляется из заглавных букв (всего используется 30 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 50 автомобильных номеров.

1) 100 байт 2) 150 байт 3) 200 байт 4)250 байт

Решение . Количество символов используемых для кодирования номера составляет: 30 букв + 10 цифр = 40 символов. Количество информации несущий один символ равен 6 бит (2I=40, но количество информации не может быть дробным числом, поэтому берем ближайшую степень двойки большую количества символов 26=64).

Мы нашли количество информации, заложенное в каждом символе, количество символов в номере равно 5, следовательно, 5*6=30 бит. Каждый номер равен 30 битам информации, но по условию задачи каждый номер кодируется одинаковым и минимально возможным количеством байт, следовательно, нам необходимо узнать, сколько байт в 30 битах. Если разделить 30 на 8 получится дробное число, а нам необходимо найти целое количество байт на каждый номер, поэтому находим ближайший множитель 8-ки, который превысит количество бит, это 4 (8*4=32). Каждый номер кодируется 4 байтами.

Для хранения 50 автомобильных номеров потребуется: 4*50=200 байт.

Выбор оптимальной стратегии в игре «Угадай число». На получении максимального количества информации строится выбор оптимальной стратегии в игре «Угадай число», в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16), а второй - должен «угадать» задуманное число. Если рассмотреть эту игру с информационной точки зрения, то начальная неопределенность знаний для второго участника составляет 16 возможных событий (вариантов загаданных чисел).

При оптимальной стратегии интервал чисел всегда должен делиться пополам, тогда количество возможных событий (чисел) в каждом из полученных интервалов будет одинаково и отгадывание интервалов равновероятно. В этом случае на каждом шаге ответ первого игрока («Да» или «Нет») будет нести максимальное количество информации (1 бит).

Как видно из табл. 1.1, угадывание числа 3 произошло за четыре шага, на каждом из которых неопределенность знаний второго участника уменьшалась в два раза за счет получения сообщения от первого участника, содержащего 1 бит информации. Таким образом, количество информации, необходимое для отгадывания одного из 16 чисел, составило 4 бита.

Контрольные вопросы и задания

1. Априори известно, что шарик находится в одной из трех урн: А, В или С. Определите, сколько бит информации содержит сообщение о том, что он находится в урне В.

Варианты: 1бит, 1,58бита, 2бита, 2,25бита.

2. Вероятность первого события составляет 0,5, а второго и третьего 0,25. Чему для такого распределения равна информационная энтропия. Варианты: 0,5бита, 1 бит, 1,5бита, 2бита, 2,5бита, 3бита.

3. Вот список сотрудников некоторой организации:

Определите количество информации, недостающее для того, чтобы выполнить следующие просьбы:

Пожалуйста, позовите к телефону Иванову.

Меня интересует одна ваша сотрудница, она 1970 года рождения.

4. Какое из сообщений несет больше информации:

· В результате подбрасывания монеты (орел, решка) выпала решка.

· На светофоре (красный, желтый, зеленый) сейчас горит зеленый свет.

· В результате подбрасывания игральной кости (1, 2, 3, 4, 5, 6) выпало 3 очка.