Лабораторная работа №1
Информация и информационные процессы
Решая различные задачи, человек вынужден использовать информацию об окружающем нас мире. И чем более полно и подробно человеком изучены те или иные явления, тем подчас проще найти ответ на поставленный вопрос. Так, например, знание законов физики позволяет создавать сложные приборы, а для того, чтобы перевести текст на иностранный язык, нужно знать грамматические правила и помнить много слов.
Часто приходится слышать, что сообщение или несет мало информации или, наоборот, содержит исчерпывающую информацию. При этом разные люди, получившие одно и то же сообщение (например, прочитав статью в газете), по-разному оценивают количество информации, содержащейся в нем. Это происходит оттого, что знания людей об этих событиях (явлениях) до получения сообщения были различными. Поэтому те, кто знал об этом мало, сочтут, что получили много информации, те же, кто знал больше, чем написано в статье, скажут, что информации не получили вовсе. Количество информации в сообщении, таким образом, зависит от того, насколько ново это сообщение для получателя.
Однако иногда возникает ситуация, когда людям сообщают много новых для них сведений, а информации при этом они практически не получают (в этом нетрудно убедиться во время опроса или контрольной работы). Происходит это оттого, что сама тема в данный момент слушателям не представляется интересной. Смысловая составляющая информации во многом индивидуальна. Большинство россиян не способны извлечь никакой информации из текста на японском языке. Многие взрослые, взяв учебник для начальных классов, также не сочтут его заслуживающей своего внимания информацией, хотя, в отличие от предыдущего случая, понимают что там написано. Химика редко интересуют сообщения об археологических открытиях, а большая часть литераторов активно игнорирует любые сведения из области математики. Наконец, многие образованные люди не верят в статьи, опубликованные в бульварной прессе, заранее считая их недостоверными. Таким образом, информативность любых сведений и сообщений существенно зависит от воспринимающего их человека, его предыдущих знаний, опыта, интересов, отношения к источнику информации и множества других факторов личного характера, т.е. по своей сути является субъективной.
Как же все-таки измерить информацию? Общепринятым на данный момент решением проблемы является измерение объема информации при полном игнорировании ее смысла. Такой подход, несмотря на кажущуюся бессмысленность, оказывается необычайно полезным и широко применяется на практике.
Если подбросить монету и проследить, какой стороной она упадет, то мы получим определенную информацию. Обе стороны монеты "равноправны", поэтому одинаково вероятно, что выпадет как одна, так и другая сторона. В таких случаях говорят, что событие несет информацию в 1 бит. Если положить в мешок два шарика разного цвета, то, вытащив вслепую один шар, мы также получим информацию о цвете шара в 1 бит. В качестве единицы информации принять один бит (англ. bit — binary digit — двоичная цифра) предложил американский учёный Клод Шеннон. Бит в теории информации — количество информации, необходимое для различения двух равновероятных сообщений.
В компьютерной технике бит соответствует физическому состоянию носителя информации: намагничено - не намагничено, есть отверстие - нет отверстия. При этом одно состояние принято обозначать цифрой 0, а другое - цифрой 1.
В информатике часто используется величина, называемая байтом (byte) и равная 8 битам. И если бит позволяет выбрать один вариант из двух возможных, то байт, соответственно, 1 из 256 (28).
Наряду с байтами для измерения количества информации используются более крупные единицы:
1 Килобайт (Кб) = 210 байт = 1024 байта;
1 Мегабайт (Мб) = 210 Кбайт = 1024 Кбайта;
1 Гигабайт (Гб) = 210 Мбайт = 1024 Мбайта.
1 Терабайт (Тб) = 210 Гбайт = 1024 Гбайта,
1 Петабайт (Пб) = 210 Тбайт = 1024 Тбайта.
Определить понятие «количество информации» довольно сложно. В решении этой проблемы существуют два основных подхода. Исторически они возникли почти одновременно.
Содержательный подход к измерению информации
Другое название содержательного подхода – вероятностный. Вероятность - степень возможности появления какого-либо определенного события в тех или иных условиях. Два события называются равновероятными (или равновозможными), если нет никаких объективных причин считать, что одно из них может наступить чаще, чем другое.
Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N.
Рассмотрим в качестве примера опыт, связанный с бросанием правильной игральной кости, имеющей N граней. Результаты данного опыта могут быть следующие: выпадение грани с одним из следующих знаков: 1, 2,... N.
Введем в рассмотрение численную величину, измеряющую неопределенность — энтропию (обозначим ее H). Согласно развитой теории, в случае равновероятного выпадания каждой из граней величины N и H связаны между собой формулой Хартли H = log2 N.
Важным при введении какой-либо величины является вопрос о том, что принимать за единицу ее измерения. Очевидно, H будет равно единице при N = 2. Иначе говоря, в качестве единицы принимается количество информации, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов (примером такого опыта может служить бросание монеты при котором возможны два исхода: «орел», «решка»). Такая единица количества информации и является «битом».
Приведем примеры равновероятных сообщений: при бросании монеты: "выпала решка", "выпал орел"; на странице книги: "количество букв чётное", "количество букв нечётное".
Определим теперь, являются ли равновероятными сообщения "первой выйдет из дверей здания женщина" и "первым выйдет из дверей здания мужчина". Однозначно ответить на этот вопрос нельзя. Все зависит от того, о каком именно здании идет речь. Если это, например, станция метро, то вероятность выйти из дверей первым одинакова для мужчины и женщины, а если это военная казарма, то для мужчины эта вероятность значительно выше, чем для женщины.
Для задач такого рода американский учёный Клод Шеннон предложил в 1948 г. другую формулу определения количества информации, учитывающую возможную неодинаковую вероятность сообщений в наборе.
Формула Шеннона:
I = — (p1log2 p1 + p2 log2 p2 +... + pN log2 pN),
где pi — вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.
Вероятность события А определяется формулой:
P(A) = m/n,
где m - число элементарных исходов, благоприятствующих А;
n - число всех возможных элементарных исходов испытания.
Легко заметить, что если вероятности p1,..., pN равны, то каждая из них равна 1 / N, и формула Шеннона превращается в формулу Хартли.
Рассмотрим следующий пример. Пусть при бросании несимметричной четырехгранной пирамидки вероятности выпадения граней будут следующими: p1=1/2, p2=1/4, p3=1/8, p4=1/8, тогда количество информации, получаемое после броска, можно рассчитать по формуле:
Для симметричной четырехгранной пирамидки количество информации будет: H=log24=2(бит).
Заметим, что для симметричной пирамидки количество информации оказалось больше, чем для несимметричной пирамидки. Максимальное значение количества информации достигается для равновероятных событий.
Примеры
Вероятностный подход
1. Какое количество информации несет в себе сообщение о том, что нужная вам программа находится на одной из восьми дискет?
Дано:
N=8 – количество дискет (число событий)
Решение:
N = 2I
8 = 2I
Ответ: 3 бита
2. Какое количество информации получит второй игрок при игре в крестики-нолики на поле 8х8 после первого хода первого игрока, играющего крестиками?
Дано:
N=64 – количество полей
Решение:
N = 2I
64 = 2I
Ответ: 6 бит
3. Сообщение о том, что ваш друг живет на десятом этаже несет в себе 4 бита информации. Сколько этажей в доме?
Дано:
i=4 бита
Решение:
N = 2I
N = 24
Ответ: 16
4. В коробке 5 синих и 15 красных шариков. Какое количество информации несет сообщение, что из коробки достали синий шарик?
Дано:
N1=5, N2=15
Решение:
N=N1+N2
N=15+5=20 всего шариков
K=5 – синих (его достали)
N/K=20/5=4
2i=4
i=2 бита
Ответ: 2 бита.
5. Какое количество информации о цвете вынутого шарика будет получено, если в непрозрачном пакете хранятся: 10 белых, 20 красных, 30 синих и 40 зеленых шариков?
Дано:
K=10+20+30+40=100 – общее количество шариков
N1=10; N2=20; N3=30; N4=40;
Решение:
Pбел. = 10/100 = 0,1
Pкрасн. = 20/100 = 0,2
Pсин. = 30/100 = 0,3
Pзел. = 40/100 = 0,4
I = — (p1log2 p1 + p2 log2 p2 +... + pN log2 pN);
I = – (0,1∙log20,1 + 0,2∙log20,2 + 0,3∙log20,3 + 0,4∙log20,4) ≈ 1,85 бита
Ответ: 1,85 бита
6. Студенты группы изучают один из трех языков: английский, немецкий или французский. Причем 12 студентов не учат английский. Сообщение, что случайно выбранный студент Петров изучает английский, несет log23 бит информации, а что Иванов изучает французский – 1 бит. Сколько студентов изучают немецкий язык?
Дано:
Y – учат французский
X – учат английский, 12 не учат английский. Всего 12+X студентов
N=12+X
K1=X
i1=log23 бит
i2=1 бит
Решение:
(12+X)/X=2log23
12+X=3X
X=6
N=12+6=18
K2=Y
18/Y=21
Y=9
18-X-Y=18-6-9=3 студента изучают немецкий.
Ответ: 3