САЙТ
учителя информатики

ПЛОТНИКОВА СЕРГЕЯ НИКОЛАЕВИЧА

Участник Общероссийского рейтинга школьных сайтов

Теория

Тема 3. Количество и единицы измерения информации (2 часа)

Дидактические единицы: Измерение информации, единицы её измерения (биты, триты, диты, наты). Алфавитный и содержательный подходы к измерению информации. Формула Хартли. Формула Шэннона.

Вопросы к изучению:

1.
Измерение информации, единицы её измерения (биты и др.).
2. Cодержательный подход к измерению информации. Формула Хартли. Формула Шэннона.
3. Алфавитный подход к измерению информации.


1. Измерение информации, единицы её измерения (биты и др.).

Подходы к измерению информации.

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

Выясним, дома или нет наш приятель. Будет ли при этом получена информация, и какая? Естественно считать, что информация будет получена: раньше не знали, позвонили, проведали - узнали. Это и есть информация, точнее: информация есть прирост знания.

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

Если приятеля не обнаружим дома в рабочее время, то информация, полученная при этом, не будет большой. А вот если ночью? Таким образом, объём информации связывается с вероятностью события: чем менее вероятное событие произошло, тем больше информации содержит сообщение о том, что оно совершилось.

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

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

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

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

2. Cодержательный подход к измерению информации. Формула Хартли. Формула Шэннона.

Содержательный подход к измерению информации.

Будем считать, что сообщение информативно (содержит ненулевую информацию), если оно пополняет знания человека чем-то новым. Если текст непонятен, то он неинформативен. Текст понятен, если он логически связан с предыдущими знаниями. Следовательно, сообщение несёт НЕНУЛЕВУЮ информацию для человека, если содержащиеся в нём сведения являются для него новыми и понятными.

Единицы измерения информации.

Предположим, что у Вашего друга на одной из его восьми полок, стоящих друг на друге, лежит DVD-диск с новым фильмом. Какое минимальное количество вопросов, беседуя со своим другом по телефону, надо задать, чтобы узнать, на которой из полок лежит DVD-диск?

Если разделить область неизвестного пополам, то DVD может оказаться выше либо ниже границы. Вопрос можно построить так: "DVD выше четвёртой полки?" (или, что то же самое "DVD ниже пятой полки?"). Кратко друг должен отвечать только "да" или только "нет". Получив ответ "да", Вы исключаете из поиска полки 1-4. Затем снова делите пополам оставшуюся область и спрашиваете друга: "DVD выше шестой полки?" Получив ответ "нет", мы отбрасывает из области поиска полки 7 и 8. Последний вопрос может звучать так: "DVD на пятой полке?". Вы получите ответ либо "да", либо "нет". Так Вы узнаете, на которой из полок лежит фильм.

№№ полок 1-й вопрос Остались полки 2-й вопрос Остались полки 3-й вопрос Осталась полка
1 "DVD лежит выше 5-й полки?"
Пусть получен ответ "да".
Исключаем полки 5, 6, 7 и 8.
1 "DVD лежит выше 3-й полки?"
Пусть получен ответ "нет".
Исключаем полки 1 и 2.
1 "DVD на 3-й полке?"
Пусть получен ответ "нет".
Исключаем полку 3.
DVD найден.
1
2 2 2 2
3 3 3 3
4 4 4 4
5 5 5 5
6 6 6 6
7 7 7 7
8 8 8 8
1-й бит 2-й бит 3-й бит

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

ШЕННОН Клод (полн. Клод Элвуд Шеннон, Claude Elwood Shannon) (16 апреля 1916 г., Гейлорд, Мичиган - 24 февраля 2001 г., Кембридж, Массачусетс), американский математик, один из создателей математической теории информации; автор трудов по теории релейно-контактных схем, математической теории связи, кибернетики.

Клод Шэннон предложил термин "bit", соединив два английских слова: binary digit. Он предложил считать, что сообщение, уменьшающее неопределённость наших знаний о чём-либо в два раза, несёт в себе 1 бит информации. Неопределённость знаний о некотором событии - это количество возможных результатов события (бросания кубика, монеты, вытягивания жребия, стрельбы по мишени и т.п.).
Примеры: При бросании монеты неопределённость знаний о результате (которой из сторон она упадёт на пол) равна 2. При бросании тетраэдра (четырёхгранной пирамидки из равносторонних треугольников) неопределённость знаний о результате равна 4. При бросании игральной кости неопределённость знаний равна 6.


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

Сообщение о том, что произошло одно событие из двух равновероятных, несёт 1 бит информации. Сообщение о том, что произошло одно событие из четырёх равновероятных, несёт 2 бита информации. Откуда взялись именно такие величины?

Ральф Винтон Лайон Хартли (англ. Ralph Vinton Lyon Hartley), родился 30 ноября 1888 г. в Ели, штате Невада, умер 1 мая 1970 г. Американский учёный-электронщик. Предложил генератор Хартли, преобразование Хартли и сделал вклад в теорию информации

Количество информации i, содержащееся в сообщении о том, что произошло одно из N равновероятных событий, определяется из решения показательного уравнения (формулы Хартли) 2i=N, где i=0, 1, 2 ...

Решение этого уравнения выглядит как i=log2N

Сводная таблица исчисления количества информации для равновероятных событий Объект с двумя гранями (монетка) Объект с четырьмя гранями (тетраэдр) Объект с шестью гранями (куб) Объект с восемью равновероятными состояниями (шляпа с разноцветными шариками внутри)
Неопределённость знаний о результате N 2 4 6 8
Вероятность события 1/N 1/2 1/4 1/6 1/8
Количество информации в сообщении о событии i 1 бит 2 бита 2 бита < i < 3 бита 3 бита
Формула Хартли 2¹=2
log22=1
2²=4
log24=2
22,584962501...=6
log26≈2,584962501
2³=8
log28=3


Из таблицы видно, что когда число возможных исходов событий равно целым степеням двойки, показательное уравнение решается в уме. Если же число возможных исходов событий не равно целым степеням двойки, то приходится пользоваться таблицей логарифмов. Тем, у кого под руками компьютер с установленными на нём электронными таблицами (например, Microsoft Excel или OpenOffice.org Calc), можно воспользоваться встроенной функцией вычисления логарифмов. Анимация ниже покажет, как можно вычислить логарифм числа 6 по основанию 2, вводя данные в лист электронной книги вручную.

Как вычислить логарфим числа по основанию 2 с помощью электронной таблицы


Вероятность и информация.

Принято считать, что 1 бит есть количество информации, уменьшающее неопределённость знаний в 2 раза. Если имеется N равновероятных событий, то количество информации i2 в битах можно вычислить по формуле Хартли i2=log2N. Но количество информации иногда измеряется и другими величинами. Можно назвать единицу количества информации 1 трит, если реализуется одно событие из трёх равновероятных. В этом случае надо решить показательное уравнение i=logзN. 1 дит - количество информации, уменьшающее неопределённость знаний в 10 раз, т.е. i10=lgN. 1 нат - количество информации, исчисляемое по уравнению ie=lnN, по степени основания e≈2,718281828459045... натурального логарифма.

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

Если события имеют разные вероятности, то применяется формула Шеннона, имеющая вид:

формула Шэннона

где Pi - вероятность того, что именно i-е сообщение выделено в наборе из N сообщений. Если вероятности P1, P2, P3 ... Pn-1, Pn равны, то каждая из них равна 1/N и формула Шеннона превращается в формулу Хартли.

Рассмотрим два примера

Пример 1. Синдбад-мореход в числе 10 других купцов плывёт в дальние страны на корабле с командой из 40 человек. Корабль захватили пираты, разграбили груз, разделили одежды пленников. Их привели на рынок невольников для продажи на галеры. Торг только начался.Какова вероятность пиратам продать на рынке невольников бывшего моряка? Велика ли вероятность пиратам продать на галеры бывшего купца? С какой вероятностью на галеры продадут именно Синдбада?

Обозначим вероятность (по-английски probability) продажи бывшего купца pm, а вероятность продажи бывшего моряка ps. Тогда pm=10/50=0,2, а ps=40/50=0,8. pm/ps=1/4.Значит, вероятность продажи бывшего купца в 4 раза меньше вероятности продажи бывшего моряка.

Все возможные продажи 50 пленников составят тогда 0,2+0,8=1. Значит, поскольку Синдаб - один из 50 пленников, вероятность, что на галеры продадут именно его, равна 1/50.

Пример 2. В царстве 3/9, государстве 3/10 перепись, проведённая в годы правления царя Еремея, показала, что простолюдинов обоего пола податных сословий проживает 70 000, военно-служилых 8 000, а лиц дворянского звания - 2 000. Царь Еремей за непослушание отцовской воле приказал отдать дочь свою царевну Несмеяну за первого встречного замуж. Какова вероятность для Несмеяны стать женой простолюдина, либо военного, либо дворянина?

Из первого примера можно догадаться, что вероятность выйти замуж за представителя одного из сословий равна доле этого сословия во всём населении царства-государства. Обозначим вероятность для царевны Несмеяны выйти замуж за простолюдина как ps, за военного - pw, за дворянина - pс. Численность населения равна 80 000 человек. Тогда вероятность для Несмеяны оказаться замужем за

простолюдином ps=70 000/80 000=7/8=0,875
военным pw=8 000/80 000=1/10=0,1
дворянином pс=2 000/80 000=2/80=1/40=0,025
0,875+0,1+0,025=1

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

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

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

Объективное восприятие информации. Для тех, кто знает, сколько людей и какого звания было на захваченном судне, сообщение, что на галеры продан пленный купец более информативно, чем сообщение о том, что на галеры продан боцман-невольник. Зависимость между вероятностью события (P) и количеством информации в сообщении о нём (i) выражается формулой: i= log2 (1/P).

Из таблицы выше видно, что неопределённость знаний о результате N и вероятность события P суть взаимоообратные величины, т.е. N=1/P, P=1/N. Тогда i = log2(1/P) = log2N. Установленные соотношения дают возможность исчислить количество информации о событии, исходя из его вероятности.

В примере 1 про Синдбада-морехода подсчитаем количество информации в сообщении о том, что на галеры продан боцман с захваченного пиратами корабля, а затем о том, что на галеры продан купец с того же корабля. Вероятность продажи моряка ps=4/5=0,8, а вероятность продажи бывшего купца pm=1/5=0,2. По формуле для случая с боцманом (моряком) имеем is= log2(1/Ps) = log2(1/0,8) = log2(10/8) = log2(1,25)≈0,321928095... бит, а для случая с купцом имеем im = log2(1/Pm) = log2(1/0,2) = log2(10/2)=log25≈2,321928095... бит.

Ответ: сообщение о том, что на рынке невольников продан боцман с корабля Синдбада, несёт приблизительно 0,32 бита информации, а о том, что продан сам Синдбад-мореход - около 2,32 бит.

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


3. Алфавитный подход к измерению информации.
Народный сказитель-домовой Бабай Абай повествует о славных подвигах великого воина Айки Бабайки
БАЙКА "АЙКА БАБАЙКА"

В графстве КАЙЙА КААББА, населённом домовыми, каждый вечер местный книгочей АБАК БАЙБАК направляется в КАБАК, где он слушает и записывает на свиток пергамена байку "АЙКА БАБАЙКА", которую распевает бродячий сказитель-рунопевец БАБАЙ АБАЙ. Эта байка повествует о славных ночных походах легендарного воина Айки Бабайки в жилища людей, о его потрясающих победах над человеческими детёнышами, о пугании засыпающих детей из-под стола во время просушивания своих боевых онучей и портянок на батарее парового отопления. Наречие АБАЙКА, на котором написан героический эпос домовых, использует 4 буквы (А, Б, Й, К), пробел для разделения слов и знак препинания - точку. Домовые-лингвисты насчитали в эпосе 10 000 слов.

Айка Бабайка в полном боевом облачении и блеске своей воинской славы

Они же установили, что, как и в языках сынов Адама, буквы алфавита АБАЙКА встречаются в тексте с разной частотой.

Буква А Б Й К Пробел Точка
Встретилась, раз 4 000 1 000 2000 1500 1000 500

В своих школах на уроках информатики учителя-домовые требуют от юных домовят узнать, какой объём информации содержит байка "Айка Бабайка".

Решение:
Поскольку объём книги достаточно большой, то можно допустить, что вычисленная по ней частота встречаемости в тексте каждого из символов алфавита характерна для любого текста на языке АБАЙКА. Подсчитаем частоту встречаемости каждого символа во всем тексте книги (т.е. вероятность) и ин-формационные веса символов:

Буква Частота встречаемости
(вероятность встретить символ)
Информационный вес символа i, бит
А 4000/10000=0,4 iА=log2(1/0,4)=log2(10/4)=log22,5≈1,321928 бит
Б 1000/10000=0,1 iБ=log2(1/0,1)=log2(10/1)=log210≈3,1928 бит
Й 2000/10000=0,2 iЙ=log2(1/0,2)=log2(10/1)=log25≈2,321928 бит
К 1500/10000=0,15 iК=log2(1/0,15)=log2(100/15)=log26,(6)≈2,736966 бит
пробел 1000/10000=0,1 i_=log2(1/0,1)=log2(10/1)=log210≈3,1928 бит
500/10000=0,05 i=log2(1/0,05)=log2(100/5)=log220≈4,321928 бит

Общий объём информации в книге вычислим как сумму произведений информационного веса каждого символа на число повторений этого символа в книге i=iАnА + iБnБ + iЙnЙ + iКnК + iпробелnпробел + in=1,321928•4000 + 3,19281•1000 + 2,3219282•1000 + 2,736966•1500 + 3,321928•1000 + 4,321928•500 = 22841,84 бита

Единицы измерения информации, производные от бита и байта.

Как мы уже выяснили в теме 2, при помощи 1-го байта (8 бит) можно закодировать 256 различных символов. Понятие байта менялось со временем. Сначала байт приравнивали 5-т битам, затем 6-и. В конце концов байт приравняли 8-и битам. Как нам уже известно, одним байтом кодируется один символ в тексте, хранящемся в памяти компьютера. 28= 256 различных букв содержится в алфавите компьютерной кодовой таблицы ASCII. С помощью двухбайтной кодировки, называемой Unicode, можно закодировать 2 8+8 = 2562 = 65536 символов. Unicode способна вместить в себя все алфавиты естественных и формальных языков, существовавших и существующих на Земле.

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

1 килобайт = 1 Кб (1 Kb)= 210 байт = 1024 байта
1 мегабайт = 1 Мб (1 Mb)= 2 20 байт = 2 10 Кбайт = 1024 Кбайта
1 Гигабайт = 1 Гб (1 Gb)= 2 30 байт = 2 20 Кбайт =2 10 Мбайт =1024 Мбайта
1 Терабайт (1 Тb)= 2 40 байт = 2 30 Кбайт =2 20 Мбайт=2 10 Гбайт=1024 Гбайта
1 Петабайт (Pb)=2 50 байт =240 Кбайт=2 30 Мбайт=2 20 Гбайт=2 10 Тбайт = 1024 Тb
1 Эксабайт (Pb)=2 60 байт =250 Кбайт=2 40 Мбайт=2 30 Гбайт=2 20 Тбайт =2 10 Пбайт = 1024 Pb

Перевод в Web-формат © Σταυρος Τεκτονος

Партнёры



©StavrosTektonos