Тема 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-й бит |
Таким методом дихотомического деления (деления пополам) Вы каждый раз, получая однозначный ответ, уменьшаете область неизвестного (неопределённость наших знаний) в два раза.
Клод Шэннон предложил термин "bit", соединив два английских слова: binary digit. Он предложил считать, что сообщение, уменьшающее неопределённость наших знаний о чём-либо в два раза, несёт в себе 1 бит информации. Неопределённость знаний о некотором событии - это количество возможных результатов события (бросания кубика, монеты, вытягивания жребия, стрельбы по мишени и т.п.). |
Сообщение о том, что произошло одно событие из двух равновероятных, несёт 1 бит информации. Сообщение о том, что произошло одно событие из четырёх равновероятных, несёт 2 бита информации. Откуда взялись именно такие величины?
Количество информации 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, вводя данные в лист электронной книги вручную.
Принято считать, что 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пробел + i••n•=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 способна вместить в себя все алфавиты естественных и формальных языков, существовавших и существующих на Земле.
На современных компьютерах можно сохранить так много информации, что попытки выразить их наполнение с помощью бита или байта будут подобны измерению расстояния от Перми до Москвы с помощью школьной линейки. И люди условились о том, как считать объёмы информации большие, нежели байт.
Перевод в Web-формат © Σταυρος Τεκτονος