Лекция "измерение информации. меры информации"

тема 1 вопрос 7 измерение информации. меры информации В информатике используются различные подходы к измерению информации: Содержательный подход к измерению информации. Сообщение – информативный поток, который в  процессе передачи информации поступает к приемнику.  Сообщение несет информацию для человека,  если содержащиеся в нем сведения являются для него новыми и понятными  Информация ­ знания  человека ? сообщение должно быть информативно. Если сообщение не информативно, то количество  информации с точки зрения человека = 0. (Пример: вузовский учебник по высшей математике содержит  знания, но они не доступны 1­класснику) В содержательном подходе количество информации, заключенное в сообщении, определяется объемом  знаний, который это сообщение несет получающему его человеку.  Вспомним, что с «человеческой» точки зрения информация ­ это знания, которые мы получаем из  внешнего мира. Количество информации, заключенное в сообщении, должно быть тем больше, чем  больше оно пополняет наши знания.  Вы уже знаете, что за единицу измерения информации принимается 1 бит.  1 бит ­ минимальная единица измерения количества информации. Проблема измерения информации исследована в теории информации, основатель которой ­ Клод  Шеннон.  В теории информации для бита дается следующее определение: Сообщение, уменьшающее неопределенность знания в два раза, несет 1 бит информации. Что такое неопределенность знания, поясним на примерах.  Допустим, вы бросаете монету, загадывая, что выпадет: орел или решка. Есть всего два возможных  результата бросания монеты. Причем ни один из этих результатов не имеет преимущества перед другим.  В таком случае говорят, что они равновероятны.  В случае с монетой перед ее подбрасыванием неопределенность знания о результате равна двум.   Игральный же кубик с шестью гранями может с равной вероятностью упасть на любую из них. Значит,  неопределенность знания о результате бросания кубика равна шести.  Еще пример: спортсмены­лыжники перед забегом путем жеребьевки определяют свои порядковые  номера на старте. Допустим, что имеется 100 участников соревнований, тогда неопределенность знания  спортсмена о своем номере до жеребьевки равна 100.  Следовательно, можно сказать так: Неопределенность знания о результате некоторого события (бросание монеты или игрального кубика,  вытаскивание жребия и др.) ­ это количество возможных результатов. Вернемся к примеру с монетой. После того как вы бросили монету и посмотрели на нее, вы получили  зрительное сообщение, что выпал, например, орел. Определился один из двух возможных результатов.  Неопределенность знания уменьшилась в два раза: было два варианта, остался один. Значит, узнав  результат бросания монеты, вы получили 1 бит информации. Сообщение об одном из двух равновероятных результатов некоторого события несет 1 бит информации. Пусть в некотором сообщении содержатся сведения о том, что произошло одно из N равновероятных  событий.   Тогда количество информации i, содержащееся в сообщении о том, что произошло одно из N  равновероятных событий, можно определить из формулы Хартли: N=2i.  Данная формула является показательным уравнением относительно неизвестного i.   Из математики известно, что решение такого уравнения имеет вид:  i=log2N ­ логарифм N по основанию 2.  Если N равно целой степени двойки (2,4,8,16 и т. д.), то такое уравнение можно решить «в уме».  Пример: Шахматная доска состоит из 64 полей: 8 столбцов на 8 строк.  Какое количество бит несет сообщение о выборе одного шахматного поля?  Решение. Поскольку выбор любой из 64 клеток равновероятен, то количество бит находится из формулы: 2i=64, i=log264=6, так как 26=64.  Следовательно,  i=6 бит.В противном случае количество информации становится нецелой величиной, и для решения задачи  придется воспользоваться таблицей двоичных логарифмов.   Также, если N не является целой степенью 2, то можно выполнить округление i в большую сторону. При  решении задач в таком случае i можно найти как log2K, где K ­ ближайшая к N степень двойки, такая,  что K>N. Пример: При игре в кости используется кубик с шестью гранями.  Сколько битов информации получает игрок при каждом бросании кубика?   Решение.  Выпадение каждой грани кубика равновероятно. Поэтому количество информации от одного результата  бросания находится из уравнения:2i=6. Решение этого уравнения: i=log26 Из таблицы двоичных логарифмов следует (с точностью до 3­х знаков после запятой): i=2,585 бита.  Данную задачу также можно решить округлением i в большую сторону:  2i=6<8=23,i=3 бита. Алфавитный подход к измерению информации не связывает кол­во информации с содержанием  сообщения. Алфавитный подход ­ объективный подход к измерению информации. Он  удобен при  использовании технических средств работы с информацией, т.к. не зависит от содержания сообщения.  Кол­во информации зависит от объема текста и мощности алфавита. Ограничений на max мощность  алфавита нет, но есть достаточный алфавит мощностью 256 символов. Этот алфавит используется для  представления текстов в компьютере. Поскольку 256=28, то 1символ несет в тексте 8 бит информации. лфавитный (объёмный) подход к измерению информации позволяет определить количество информации, заключенной в тексте, записанном с помощью некоторого алфавита. Алфавит ­ множество используемых символов в языке.  Обычно под алфавитом понимают не только буквы, но и цифры, знаки препинания и пробел. Мощность алфавита (N) ­ количество символов, используемых в алфавите. Например, мощность алфавита из русских букв равна 32 (буква ё обычно не используется).  Если допустить, что все символы алфавита встречаются в тексте с одинаковой частотой  (равновероятно), то количество информации, которое несет каждый символ, вычисляется по формуле  Хартли:  i=log2N,  где N ­ мощность алфавита.  Формула Хартли задает связь между количеством возможных событий N и количеством информации i:   N=2i   Из базового курса информатики известно, что в компьютерах используется двоичное кодирование  информации. Для двоичного представления текстов в компьютере чаще всего используется равномерный восьмиразрядный код. С его помощью можно закодировать алфавит из 256 символов, поскольку  256=28.    В стандартную кодовую таблицу (например, ASCII) помещаются все необходимые символы: английские и русские прописные и строчные буквы, цифры, знаки препинания, знаки арифметических операций,  всевозможные скобки и пр. В двоичном коде один двоичный разряд несет одну единицу информации, которая называется 1 бит. Например, в 2­символьном алфавите каждый символ «весит» 1 бит (log22=1); в 4­символьном  алфавите каждый символ несет 2 бита информации (log24=2); в 8­символьном ­ 3 бита (log28=3) и  т. д. Один символ из алфавита мощностью 256 (28) несет в тексте 8 битов информации. Такое количество  информации называется байтом.   1 байт =8 битов Информационный объем текста в памяти компьютера измеряется в байтах. Он равен количеству знаков в записи текста. Для измерения информации используются и более крупные единицы: Название единицы измерения Численная величина в байтах Точное количество байтов Килобайт (Кбайт)  байтМегабайт (Мбайт) Гигабайт (Гбайт) Терабайт (Тбайт) Петабайт (Пбайт) Эксабайт (Эбайт) Зеттабайт (Збайт) Йоттабайт (Йбайт)  килобайт  576  байт  мегабайт 741 824 байт  гигабайт  511 627 776 байт  терабайт  899 906 842 624 байт  петабайт  921 504 606 846 976 байт  эксабайт  591 620 717 411 303 424 байт  зеттабайт  1208925819614629174706176 байт  Единицы измерения количества информации, в названии которых есть приставки «кило», «мега» и т. д.,  с точки зрения теории измерений не являются корректными, поскольку эти приставки используются в  метрической системе мер, в которой в качестве множителей кратных единиц используется коэффициент  10, где n=3,6,9 и т. д.   Для устранения этой некорректности Международная электротехническая комиссия, занимающаяся  созданием стандартов для отрасли электронных технологий, утвердила ряд новых приставок для единиц  измерения количества информации: киби (kibi), меби (mebi), гиби (gibi), теби (tebi), пети (peti), эксби  (exbi). Однако пока используются старые обозначения единиц измерения количества информации, и  требуется время, чтобы новые названия начали широко применяться. Если весь текст состоит из K символов, то при алфавитном подходе объём V содержащейся в нем  информации равен:  V=K⋅i  где i ­ информационный вес одного символа в используемом алфавите.  Зная, что i=log2N, данную выше формулу можно представить в другом виде:  если количество символов алфавита равно N, а количество символов в записи сообщения ­ K, то  информационный объем V данного сообщения вычисляется по формуле:  V=K⋅log2N  При алфавитном подходе к измерению информации информационный объем текста зависит только от  размера текста и от мощности алфавита, а не от содержания. Поэтому нельзя сравнивать  информационные объемы текстов, написанных на разных языках, по размеру текста. Пример: 1. Считая, что каждый символ кодируется одним байтом, оцените информационный объем следующего  предложения: Белеет Парус Одинокий В Тумане Моря Голубом!  Решение.  Так как в предложении 44 символа (считая знаки препинания и пробелы), то информационный объем  вычисляется по формуле:  V=44⋅1 байт=44 байта=44⋅8 бит=352 бита   2. Объем сообщения равен 11 Кбайт. Сообщение содержит 11264 символа. Какова мощность  алфавита?  Решение.  Выясним, какое количество бит выделено на 1 символ. Для этого переведем объем сообщения в биты:11 Кбайт=11⋅210 байт=11⋅210⋅23 бит=11⋅213 бит и разделим его на число символов.  На 1 символ приходится: 11⋅21311264=11⋅21311⋅210=23=8 бит.  Мощность алфавита определяем из формулы Хартли: N=28=256 символов. Вероятностный подход к измерения информации. Все события происходят с различной вероятностью, но  зависимость между вероятностью событий и количеством информации, полученной при совершении  того или иного события можно выразить формулой которую в 1948 году предложил  Шеннон. В реальной жизни существует множество ситуаций с различными вероятностями. Например, если у  монеты одна сторона тяжелей другой, то при ее бросании вероятность выпадения «орла» и «решки»  будет различной.  Сначала разберемся с понятием «вероятность». Введем следующие понятия: испытание ­ любой эксперимент; единичное испытание ­ испытание, в котором совершается одно действие с одним предметом (например,  подбрасывается монетка, или из корзины извлекается шар); исходы испытаний ­ результаты испытания (например, при подбрасывании монеты выпал «орел», или из  корзины извлекли белый шар); множество исходов испытания ­ множество всех возможных исходов испытания; случайное событие ­ событие, которое может произойти или не произойти (например, выигрыш билета в  лотерее, извлечение карты определенной масти из колоды карт). Вероятностью случайного события (p) называется отношение числа благоприятствующих событию  исходов (m) к общему числу исходов (n):  p=mn. Заметим, что вероятность случайного события может изменяться от 0 до 1. Пример: В беспроигрышной лотерее разыгрывается 3 книги, 2 альбома, 10 наборов маркеров, 10 блокнотов.  Какова вероятность выиграть книгу?  Решение.  Общее число исходов 2+3+10+10=25; число благоприятствующих исходу событий равно 3.  Вероятность выигрыша книги вычисляется по формуле: p=325=0,12. Заметим, что во многих случаях события происходят с разной вероятностью, а значит формула N=2i не  всегда применима.  Вероятностный подход предполагает, что возможные события имеют различные вероятности  реализации.  В этом случае, зная вероятность (p) событий, можно определить количество информации (i) в  сообщении о каждом из них из формулы:  2i=1p.  Количество информации будет определяться по формуле Шеннона, предложенной им в 1948 г. для  различных вероятностных событий: I=−∑i=1Npilog2pi или I=−(p1log2p1+p2log2p2+...+pNlog2pN),  где I ­ количество информации; N ­ количество возможных событий; pi ­  вероятность i­го события. Качественная связь между вероятностью события и количеством информации в сообщении состоит в  следующем: чем меньше вероятность некоторого события, тем больше информации содержит сообщение  об этом событии. Пример: В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что  достали черный шар?  Решение. Общее число исходов: 8+24=32, число благоприятствующих исходу событий равно 8.  Вероятность выбора черного шара определяется как p=832=14=0,25 Количество информации вычисляем из соотношения 2i=10,25=114/=4, значит, i=2 бита. Пример:Пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий равны:  p1=12; p2=14; p3=18; p4=18.  Тогда  количество информации, которое будет получено после реализации одного из событий, можно  вычислить по формуле Шеннона:  I=−(12log212+14log214+18log218+18log218)=(12+24+38+38)=148(бит)=1,75(бита ). Источники: Количество информации  ­ это мера уменьшения неопределенности. 1 БИТ – такое кол­во информации, которое содержит сообщение, уменьшающее неопределенность  знаний в два раза.  БИТ­ это аименьшая единица измерения информации Единицы измерения информации: 1байт = 8 бит 1Кб (килобайт) = 210 байт = 1024 байт 1Мб (мегабайт) = 210 Кб = 1024 Кб 1Гб (гигабайт) = 210 Мб = 1024 Мб Формула  Шеннона      I  ­ количество информации    N – количество возможных событий pi – вероятности отдельных событий Задача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 бит  Количество информации достигает max значения, если события равновероятны, поэтому количество  информации можно расcчитать  по формуле  Задача2 : В корзине лежит 16 шаров разного цвета. Сколько информации несет сообщение, что достали  белый шар? т.к. N = 16 шаров,  то  I = log2 N = log2 16 = 4 бит.