Лабораторная работа № 2. Измерение информации

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

Цель работы: Знать два подхода к измерению информации, использовать формулы Шеннона и Хартли, уметь определять необходимый объем компьютерной памяти для хранения информации.

Порядок работы:

1. Выполнить задачи на измерение информации:
- согласно содержательному подходу (по формуле Хартли);

- с учетом вероятности событий (по формуле Шеннона);

- определение необходимого объема памяти для хранения информации.

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

& краткие сведения

Содержательный подход

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

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

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

Одну и ту же информацию разные люди могут оценить по разному.

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

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

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

2^х =N

Данная формула является показательным уравнением отно­сительно неизвестной х. Из математики известно, что решение такого уравнения имеет вид:

х = log₂N

— логарифм от N по основанию 2. Если N равно целой степени двойки (2, 4, 8, 16 и т.д.), то такое уравнение можно решить «в уме». В противном случае количество информации стано­вится нецелой величиной, и для решения задачи придется вос­пользоваться таблицей логарифмов.

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

Решение Ответ может быть получен из решения уравнения: 2^х = 2, откуда, очевидно, следует: х = 1 бит.

Вывод: в любом случае сообщение ободном событииuз двух равновероятных несет 1 бит информации.

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

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

2^х = 32

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

Пример 3. При игре в кости используется кубик с шестью гранями. Сколько бит информации получает игрок при каждом бросании кубика?

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

2^х =6

Решение этого уравнения: х = log₂ 6.

Из таблицы логарифмов следует (с точностью до 3-х знаков после запятой): х = 2,585 бит

Алфавитный подход

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

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

i = log₂N,

где N — мощность алфавита. Следовательно, в 2-х символьном алфавите каждый символ «весит» 1 бит (log₂2 =» 1);
в 4-х символьном алфавите каждый символ несет 2 бита информации (lоg₂4 = 2);
в 8-ми символьном — 3 бита (log₂8 = 3) и т.д.

Один символ из алфавита мощностью 256 (2⁸) несет в тексте 8 бит информации. Такое количество информации называется байт. Алфавит из 256 символов используется для представле­ния текстов в компьютере.

1 байт = 8 бит.

Если весь текст состоит из К символов, то при алфавитном подходе размер содержащейся в нем информации равен:

I = К * i

где i — информационный вес одного символа в используемом алфавите.

Если мощность алфавита N, а макси­мальное количество букв в слове, записанном с помощью этого алфавита, m, то максимально возможное количество слов в языке L определяется с помощью формулы:

L= N^m

Для измерения информации используются и более крупные единицы:

1 Кбайт (килобайт) = 2¹⁰ байт = 1024 байта

1 Мбайт (мегабайт} =- 2¹⁰ Кбайт•= 1024 Кбайта

1 Гбайт (гигабайт) = 2¹⁰ Мбайт = 1024 Мбайта

Пример 4. Книга, набранная с помощью компьютера, содержит 150 страниц; на каждой странице — 40 строк, в каждой строке — 60 символов. Каков объем инфор­мации в книге?

Решение. Мощность компьютерного алфавита равна 256. Один символ несет 1 байт информации. Значит, страница со­держит 40 * 60 = 2400 байт информации. Объем всей инфор­мации в книге (в разных единицах):

2400 * 150 = 360 000 байт 360000/1024 = 351,5625 Кбайт 351,5625/1024 = 0,34332275 Мбайт.

Количество информации и вероятность

Рассмотрим несколько примеров.

1. В коробке имеется 50 шаров. Из них 40 белых и 10 черных. Очевидно, вероятность того, что при вытаски­вании «не глядя» попадется белый шар больше, чем вероятность попадания черного.

2. Сережа — лучший ученик в классе. Вероятность того, что за контрольную по математике Сережа получит «5» больше, чем вероятность получения двойки.

3. В пруду живут 8000 карасей, 2000 щук и 40 000 пескарей. Самая большая вероятность для рыбака — поймать в этом пруду пескаря, на втором месте — карась, на третьем — щука.

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

Решение 1. Обозначим р_ч — вероятность попадания при вытаскивании черного шара, p_б — вероятность попада­ния белого шара. Тогда:

р_ч = 10/50 = 0,2; p_б = 40/50 = 0,8.

Отсюда видно, что вероятность попадания белого шара в 4 раза больше, чем черного.

Решение 2. Представим себе, что мы изучили успевае­мость Сережи за несколько лет учебы. За это время он получил по математике 100 оценок. Из них: 60 пятерок, 30 четверок, 8 троек и 2 двойки. Допуская, что такое распре­деление оценок может сохраниться и в дальнейшем, вычислим вероятность получения каждой из оценок.

р₅ = 60/100 = 0,6; р₄ = 30/100 = 0,8;

р_з = 8/100 = 0,08; p₂ = 2/100 = 0,02.

Решение З. Всего в пруду обитают 50000 рыб. Из предыдущих примеров можно догадаться, что вероят­ность попадания на удочку каждого из видов рыб равна его доле в общем количестве. Отсюда:

р_к = 8000/50000 = 0,16;

р_щ = 2000/50000 = 0,04;

р_п = 4000/50000 = 0,8;

Из рассмотренных примеров можно сделать вывод:

если N — это общее число возможных исходов какого-то процесса (вытаскивание шара, получение оценки, ловля рыбы), и из них интересующее нас событие (вытаски­вание белого шара, получение пятерки, попадание щуки) может произойти К раз, то вероятность этого события

Р=K/N

Вероятность выражается в долях единицы. В частном слу­чае, вероятность достоверного события равна 1 (из 50 белых шаров вытащен белый шар); вероятность невозможного собы­тия равна нулю (из 50 белых шаров вытащен черный шар).

Качественную связь между вероятностью события и коли­чеством информации в сообщении об этом событии можно вы­разить так:

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

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

Количественная зависимость между вероятностью события (р) и количеством информации в сооб­щении о нем (i) выражается формулой Шеннона:

i = log₂(1/p)

Пример 5. В задаче о шарах определим количество ин­формации в сообщении о попадании белого шара и чер­ного шара:

i_б = log₂(l/0,8) = log₂(l,25) = 0,321928; i_ч= log₂(l/0,2) = log₂5 = 2,321928.

Вероятностный метод для алфавитного подхода

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

В качестве примера определим количество информации, связанное с появлением каждого символа в сообщениях, записанных на русском языке. Будем считать, что русский алфавит состоит из 33 букв и знака «пробел» для разделения слов. По формуле Хартли

Н = log₂ 34 ≈ 5 бит

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