birmaga.ru
добавить свой файл

1
Измерение информации

Рассмотрим два подхода к измерению информации – содержательный (вероятностный) и символьный (алфавитный)
Содержательный (вероятностный) подход

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

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

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

Остановимся на подходе, что информация - это знания человека. Можно ли с этой точки зрения ее измерить?

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

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

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

сообщении для разных людей может быть разным! Для тех, кому сведения, содержащиеся в сообщении, известны, в нем нет информации (информация равна нулю); тем же, кому эти сведения неизвестны, сообщение несет ненулевую информацию.

Но мало сообщению быть новым, чтобы нести человеку информацию. Оно должно быть еще и понятным для этого человека. Быть понятным - это значит быть логически связанным с уже имеющимися у человека знаниями и опытом. Лекция, прочитанная на неизвестном вам языке, не принесет информации, так как язык не понятен.


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

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

Неопределенность знаний и единица информации


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

Единица измерения информации определена в теории информации. Эта единица носит название "бит". Ее определение звучит так:

Сообщение, уменьшающее неопределенность знаний в 2 раза, несет 1 бит информации.

В этом определении есть понятия, которые требуют объяснения.

Рассмотрим примеры. Допустим, вы бросаете монету, загадывая, что выпадет: орел или решка? Есть всего два варианта возможного результата бросания монеты. Причем, ни один из этих вариантов не имеет преимущества перед другим. В таком случае говорят, что они равновероятны.

Так вот, в этом случае перед подбрасыванием монеты неопределенность знаний о результате равна двум. Игральный кубик с шестью гранями может с равной вероятностью упасть на любую из них. Значит, неопределенность знаний о результате бросания кубика равна шести. Еще пример: спортсмены перед забегом путем жеребьевки определяют свой порядковый номер на старте. Допустим, если имеется 100 участников соревнований, то неопределенность знаний спортсменом своего номера до жеребьевки равна ста.


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

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

Ученик на экзамене может получить одну из четырех оценок: 5 - "отлично", 4 - "хорошо", 3 - "удовлетворительно", 2 - "неудовлетворительно". Причем, учится он очень неровно и может с одинаковой вероятностью получить любую оценку от 2 до 5. Он пришел с экзамена и на вопрос:

"Что получил?". Ответил: "Четверку!". Сколько бит информации содержится в его ответе?

Давайте подойдем к ответу постепенно. Будем отгадывать оценку, задавая вопросы, на которые можно ответить только "да" или "нет".

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

Первый вопрос:- Оценка выше тройки?

-Да!

После этого ответа число вариантов уменьшилось в два раза. Остались только 4 и 5. Получен 1 бит информации.

Второй вопрос: - Ты получил пятерку?

-Нет!

Выбран один вариант из двух оставшихся: оценка - четверка. Получен еще 1 бит информации. В сумме имеем 2 бита.

Сообщение о том, что произошло одно из четырех равновероятных событий, несет 2 бита информации.

Разберем еще одну частную задачу, а потом получим общее правило.

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

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


Задаем вопросы:


  • Банка стоит выше четвертой полки?
    - Нет.

  • Банка стоит ниже третьей полки?
    - Да.

  • Банка - на второй полке?

  • Нет.

  • Ну, теперь все ясно! Банка стоит на первой полке!

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

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

Обозначим буквой N количество возможных событий, или, как мы это еще называли, - неопределенность знаний. Буквой i будем обозначать количество информации в сообщении о том, что произошло одно из N событий.

В примере с монетой N=2 , i=l

В примере с оценками N=4, i=2

В примере со стеллажом N=8, i=3

Нетрудно заметить, что связь между этими величинами выражается такой формулой:

2i =N.

Действительно: 21 =2; 22 =4; 23 =8.

Если величина N известна, a i - неизвестно, то данная формула становится уравнением для определения i. В математике оно называется показательным уравнением. Например, пусть на стеллаже не 8, а 16 полок. Чтобы ответить на вопрос, сколько информации содержится в сообщении о том, где стоит банка, нужно решить уравнение:

2i =16

Поскольку 16=24 , то i=4.

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

2i=N.

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


    1. 5

32 +


    1. 16

    2. 10

  1. Сколько информации несет сообщение о том, что было угадано число в диапазоне целых чисел от 684 до 811? 811-684=127. 27=128

    1. 128 бит

    2. 6 бит

    3. 127 бит

    4. 7 бит +

  2. На двухцветном светофоре горит красный свет. Какой объем информации несет сообщение о том, что загорится зеленый? Может произойти только одно событие, то есть 2i=1

    1. 1 байт

    2. 0 бит +

    3. 2 бита

  3. Среди 64 монет есть фальшивая (более легкая). Указать минимальное количество
    взвешиваний, которое потребуется для поиска этой монеты.

    1. 64

    2. 6 +

    3. 32

    4. 5

  4. В детской игре "Угадай число" первый участник загадал целое число в промежутке от 1 до 16. Второй участник задает вопросы: "Загаданное число больше числа...?" Какое максимальное количество вопросов при правильной стратегии (интервал чисел в каждом вопросе делится пополам) должен задать второй участник, чтобы отгадать число?

    1. 2

    2. 3

    3. 4 +

    4. 5

До сих пор мы выбирали такие примеры, в которых N выражалось целой степенью двойки. Но пусть, например, N=12. Тогда придется решать уравнение

2i=12

Такое уравнение не имеет целочисленного решения. Нетрудно догадаться, что i будет иметь значение, лежащее между 3 и 4 , потому что

23=8, а 24=16.

Значит для N=12 i равно три с "хвостиком": 3,... Следовательно, количество информации может быть дробным числом.

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


i=log2N

Вычисление для случая, когда N=12, можно записать в такой форме:
i=log212 = 3,5850 бит

Для вычисления использовать формулу , то есть

Для определения количества информации, содержащейся в сообщении о том, что произошло одно из N равновероятных событий, используется формула I=Log2N
Эта формула была выведена американским инженером Ричардом Хартли в 1928 году и поэтому известна под названием формулы Хартли.

Вероятность и информация
Рассмотрим не равновероятные события. Например, в коробке лежат белые и черные шары. Черных шаров больше. Значит вероятность достать черный шар больше чем белый.

Чем меньше вероятность события (то есть чем больше N и меньше K), тем больше информации оно несет.

Здесь P – вероятность события

K – число событий (сколько раз может произойти данное событие – вынуть черный шар)

N – число исходов (сколько всего возможных событий – всего шаров в коробке)

Значит объем информации события обратно пропорционален его вероятности.




Задачи:


  1. В корзине лежало 8 черных и 24 белых шара. Достали черный шар. Чему равно количество информации (i).

N=32, K=8



i=2

  1. В коробке 64 цветных карандаша. Количество информации о том, что достали белый шар=4 бита. Сколько белых карандашей в коробке.


N=64, i=4, K=?





  1. В классе 30 человек. За контрольную работу получили следующие оценки

6 – пятерок

15 – четверок

8 – троек

1 – двойка

Какое количество информации содержит сообщение, что Иванов получил 4.

N=30, K=15

Значит

i=1 биту


  1. В коробке лежат белые и черные шары, из них 18 – черных. Информация о том, что достали белый шар = 2 битам. Сколько в коробке белых шаров.

Обозначим Х – число белых шаров.

Значит

4х=х+18

3х=18

Х=6
Символьный (алфавитный подход)
Проще всего это понять на примере текста, написанного на каком-нибудь языке. Для нас удобнее, чтобы это был русский язык.

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

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

Полное количество символов алфавита или его размер принято называть мощностью алфавита. Будем обозначать эту величину буквой N. Например, мощность алфавита из русских букв и отмеченных дополнительных символов равна 54.


В каждой очередной позиции текста может появиться любой из N символов. Тогда, согласно известной нам формуле, каждый такой символ несет i бит информации, которое можно определить из решения уравнения:
2i=N

Для N=54 получаем:

i= 5,755 бит

столько информации несет один символ в русском тексте! А теперь для того, чтобы найти количество информации во всем тексте, нужно посчитать число символов в нем и умножить на i.

Посчитаем количество информации на одной странице книги. Пусть страница содержит 50 строк. В каждой строке - 60 символов. Значит, на странице умещается 50x60=3000 знаков. Тогда объем информации будет равен:

5,755x3000= 17265 бит.

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

Чтобы посчитать количество информации в английском тексте, надо знать размер английского алфавита. Он включает в себя 26 букв. А если добавить дополнительные знаки, то получится 47.

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

2i =47

Решая уравнение, получим:

i = 5,555 бит. На всей странице будет

3000x5,555 = 16665 бит

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

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

мощности алфавита.

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

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


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

Количество информации, содержащееся в символьном сообщении, равно

Kxi,

где К - количество символов в тексте сообщения, a i - информационный вес символа, который находится из уравнения 2i=N, где N - мощность используемого алфавита (число символов в алфавите)
Тест:


  1. В лотерее разыгрывалось 64 шара. Выигрышная комбинация состояла из X шаров, и сообщение о ней несет 42 бита информации. Чему равно X?

    1. 7; так как i=6, i·X=42, X=7

    2. 42;

    3. 2;

    4. 64.

  2. Сообщение, записанное буквами из 64-символьного алфавита, содержит 20 символов. Какой объем информации оно несет?

    1. 120 бит, так как i=6, 6·20=120

    2. 20 байт;

    3. 64 бита;

    4. 64 байта.

  3. Книга состоит из 64 страниц. На каждой странице — 256 символов. Какой объем информации содержится в книге, если используемый алфавит состоит из 32 символов?

    1. 8 1920 байт;

    2. 40 Кб;

    3. 10 Кб, так как (5 ·28 ·26)/(210·23)=5·2=10

    4. 16 Кб.

  4. Если вариант теста в среднем имеет объем 20 килобайт (на каждой странице теста 40 строк по 64 символа в каждой, 1 символ занимает 8 бит), то количество страниц в тесте равно:

    1. 10,

    2. 16;

    3. 8 так как (20·210·23)/(40·26·23)=24/20=8

    4. 4

  5. В слове Информатика содержится следующее количество бит (используется система кодировки ASCII):

    1. 11;

    2. 88, так как 11· 8

    3. 44;

    4. 1.

Измерение информации - резюме

Символьный (алфавитный) подход

Для кодирования одного символа в разных видах кодировки используется разное число бит. Назовем его i. Это число определяет (для символьного подхода) количество информации, которое несет один символ. Количество всех символов, которые можно закодировать количеством бит = i определяется известной нам формулой 2i. Обозначим это количество буквой N. Величину N еще называют мощностью алфавита, то есть это количество символов в алфавите

N=2i

Это выражение называется формулой Хартли – по имени американского инженера Ричарда Хартли, который вывел ее в 1928 году. Количество информации определяется формулой:
i=Log 2 N
Итак, количество информации, которую несет один символ определяется числом бит, используемых для его кода. Значит количество информации, которое несет x символов = i · x

K= i · x
Содержательный (вероятностный) подход
Для равновероятных событий
Сообщение, уменьшающее неопределенность знаний в 2 раза, несет 1 бит информации.
В примере с монетой N=2 , i=l

В примере с оценками N=4, i=2

В примере со стеллажом N=8, i=3
Нетрудно заметить, что связь между этими величинами выражается такой же формулой, как и для символьного подхода, только здесь N – количество возможных равновероятных событий

2i =N

Действительно: 21 =2; 22 =4; 23 =8

До сих пор мы выбирали такие примеры, в которых N выражалось целой степенью двойки. Но пусть, например, N=12. Тогда придется решать уравнение

2i=12

Такое уравнение не имеет целочисленного решения. Нетрудно догадаться, что i будет иметь значение, лежащее между 3 и 4 , потому что

23=8, а 24=16.

Значит для N=12 i равно три с "хвостиком": 3,... Следовательно, количество информации может быть дробным числом.

Для не равновероятных событий
Например, в коробке лежат белые и черные шары. Черных шаров больше. Значит вероятность достать черный шар больше чем белый.

Чем меньше вероятность события (то есть чем больше N и меньше K), тем больше информации оно несет.


Здесь P – вероятность события

K – число событий (сколько раз может произойти данное событие – вынуть черный шар)

N – число исходов (сколько всего возможных событий – всего шаров в коробке)

Значит объем информации события обратно пропорционален его вероятности.