Мобильные телефоны и гаджеты

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

Для дальнейшего изложения необходимо использовать некоторые понятия теории вероятности: случайное событие, опыт, вероятность события, случайная величина. В окружающем нас мире происходят различные события, причём мы можем интуитивно, основываясь на опыте, оценивать одни из них как более возможные, чем другие. Случайным называют событие, которое может наступить или не наступить в результате некоторого испытания, опыта или эксперимента. Будем обозначать события заглавными буквами A, B, C и т.д. Количественная мера возможности наступления некоторого события A называется его вероятностью и обозначается как p(A), p – от английского probability. Чем более возможно наступление случайного события, тем больше его вероятность: если A более возможно чем B, то p(A) > p(B). Вводится понятие достоверного события – событие, которое обязательно наступит. Это событие обозначают W и полагают, что его вероятность p(W) = 1. Невозможным называют событие, которое никогда не произойдёт. Его обозначают Æ и полагают, что его вероятность p(Æ) = 0. Для вероятностей всех остальных событий A выполняется неравенство p(Æ) < p(A) < p(W), или 0 < p(A) < 1.

Для событий вводится понятие суммы и произведения. Сумма событий A+B – это событие, которое состоит в наступлении события A или В. Произведение событий A*B состоит в одновременном наступлении события A и B. События A и B несовместны , если они не могут наступить вместе в результате одного испытания. Вероятность суммы несовместных событий равна сумме их вероятностей. Если А и В несовместные события, то p(A+B) = p(A) + p(B).

События A1, A2, A3, …An образуют полную группу , если в результате опыта обязательно наступит хотя бы одно из них. Если события A1, A2, A3, …An попарно несовместны и образуют полную группу, то сумма их вероятностей p1+p2+p3+ …. pn =1. Если они при этом ещё и равновероятны, то вероятность каждого равна p = 1/n , где n – число событий. Вероятность события определяется как отношение числа благоприятных событию исходов опыта к общему числу исходов. Частота события – эмпирическое приближение его вероятности. Она вычисляется в результате проведения серии опытов как отношение числа опытов, в которых событие наступило к общему числу опытов. При большом числе опытов (испытаний) частота события стремится к его вероятности.

К. Шеннон, используя подход Р. Хартли, обратил внимание на то, что при передаче словесных сообщений частота (вероятность) использования различных букв алфавита не одинакова: некоторые буквы используются очень часто, другие - редко.

Рассмотрим алфавит A m состоящий из m символов. Обозначим через p i вероятность (частоту) появления i-ого символа в любой позиции передаваемого сообщения, состоящего из n символов. Один i – ый символ алфавита несёт количество информации равное -Log 2 (p i). Перед логарифмом стоит «минус» потому, что количество информации величина неотрицательная, а Log 2 (x) <0 при 0

На месте каждого символа в сообщении может стоять любой символ алфавита A m ; количество информации, приходящееся на один символ сообщения, равно среднему значению информации по всем символам алфавита A m:

Общее количество информации, содержащееся в сообщении из n символов равно:

Если все символы алфавита A m появляются с равной вероятностью, то все p i = p. Так как Sр i = 1, то p = 1/m.

Формула (3.2) в случае, когда все символы алфавита равновероятны, принимает вид

Вывод: формула Шеннона (3.2) в случае, когда все символы алфавита равновероятны, переходит в формулу Хартли (2.2).

В общем случае количество энтропии H произвольной системы X (случайной величины), которая может находиться в m различных состояниях x 1 , x 2 , … x m c вероятностями p 1 , p 2 , … p m , вычисленное по формуле Шеннона, равно

Напомним, что p 1 + p 2 + … +p m = 1. Если все p i одинаковы, то все состояния системы X равновероятны; в этом случае p i = 1/m, и формула (3.3) переходит в формулу Хартли (2.5): H(X) = Log 2 (m).

Замечание. Количество энтропии системы (случайной величины) Х не зависит от того, в каких конкретно состояниях x 1 , x 2 , … x m может находиться система, но зависит от числа m этих состояний и от вероятностей p 1 , p 2 , … p m , с которыми система может находиться в этих состояниях. Это означает, что две системы, у которых число состояний одинаково, а вероятности этих состояний p 1 , p 2 , … p m равны (с точностью до порядка перечисления), имеют равные энтропии.

Теорема. Максимум энтропии H(X) достигается в том случае, когда все состояния системы равновероятны. Это означает, что

Американский инженер Р. Хартли в 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 двоичных разрядов.

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

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

Американский инженер Р. Хартли в 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 очка.

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

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

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

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

Pi - вероятности отдельных событий.

Для частного, но широко распространенного и рассмотренного выше случая, когда события равновероятны (р; = 1 / N), величину количества информации I можно рассчитать по формуле:

Задание «Бросание пирамидки». Определить количество информации, которое мы получаем в результате бросания несимметричной и симметричной пирамидок.

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

Количество информации, которое мы получим после бросания несимметричной пирамидки, можно рассчитать по формуле (2.3):

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

Количество информации, которое мы получим после бросания симметричной пирамидки, можно рассчитать по формуле (2.4):

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

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

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

Количество информации, которое несет знак, зависит от вероятности его получения. Если получатель заранее точно знает, какой знак придет, то полученное количество информации будет равно 0. Наоборот, чем менее вероятно получение знака, тем больше его информационная емкость.

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

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

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

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

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

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

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

Таблица 2.4

Информационная модель игры «Угадай число»

Практическое задание «Определение количества информации».

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

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

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

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

Контрольные вопросы

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

Задания для самостоятельного выполнения

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

Практикум к главе 2

Практическая работа 2.1. Перевод единиц измерения количества информации с помощью калькулятора

Практическая работа 2.2. Определение количества информации по формуле Шеннона с помощью калькулятора

Понятие Энтропи́и впервые введено в 1865 Р. Клаузиусом в термодинамике для определения меры необратимого рассеяния энергии. Энтропия применяется в разных отраслях науки, в том числе и в теории информации как мера неопределенности какого-либо опыта, испытания, который может иметь разные исходы. Эти определения энтропии имеют глубокую внутреннюю связь. Так на основе представлений об информации можно вывести все важнейшие положения статистической физики. [БЭС. Физика. М: Большая российская энциклопедия, 1998].

Информационная двоичная энтропия для независимых (неравновероятных) случайных событий x с n возможными состояниями (от 1 до n , p - функция вероятности) рассчитывается по формуле Шеннона :

Эта величина также называется средней энтропией сообщения. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины .
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других.
В 1948 году, исследуя проблему рациональной передачи информации через зашумлённый коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки теории информации, которая использует понятие вероятности. Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.

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

, где I – количество передаваемой информации, p – вероятность события, N – возможное количество различных (равновероятных) сообщений.

Задание 1. На равновероятные события.
В колоде 36 карт. Какое количество информации содержится в сообщении, что из колоды взята карта с портретом “туз”; “туз пик”?

Вероятность p1 = 4/36 = 1/9, а p2 = 1/36. Используя формулу Хартли имеем:

Ответ: 3.17; 5.17 бит
Заметим (из второго результата), что для кодирования всех карт, необходимо 6 бит.
Из результатов также ясно, что чем меньше вероятность события, тем больше информации оно содержит. (Данное свойство называется монотонностью )

Задание 2. На неравновероятные события
В колоде 36 карт. Из них 12 карт с “портретами”. Поочередно из колоды достается и показывается одна из карт для определения изображен ли на ней портрет. Карта возвращается в колоду. Определить количество информации, передаваемой каждый раз, при показе одной карты.