Попытаемся найти закономерность в проведённых выше вычислениях. Рассматривая примеры угадывания, мы неоднократно обращали ваше внимание на то, что все возможные варианты были для угадывающего
Чем меньше вероятность правильного ответа, тем большую информацию мы получаем, выяснив его. То есть количество информации зависит от
Следовательно, информация равна степени, в которую надо возвести 2 для того, чтобы получить N, т. е.
Эта величина называется логарифмом
Конечно, число возможных вариантов правильного ответа необязательно должно быть целой степенью числа 2. Это не должно нас смущать, потому что количество информации необязательно должно выражаться целым числом.
Таблица 1
Зависимость количества полученной информации от вероятности правильности ответа
Например, если число вариантов равно пятидесяти, то, когда мы узнаем единственный правильный ответ, полученная информация будет равна степени, в которую надо возвести двойку для того, чтобы получить число 50. Нетрудно выяснить, что эта информация будет равна с точностью до третьего знака 5,644 бита.
Полученная формула информации практически в точности соответствует формуле Больцмана для энтропии (§ 8). Напрашивается предположение, что между энтропией и информацией существует большое сходство.
Рассмотрим этот вопрос подробнее. От чего зависит максимальная информация, которую можно получить, установив абсолютно точный ответ на поставленный вопрос? Чем более неопределённым было наше знание, чем меньше была вероятность угадать правильный ответ, тем большую информацию содержит сообщение, из которого мы этот ответ узнаем. По сути, наибольшая информация, которую мы можем получить из сообщения, равна количеству нашего первоначального незнания правильного ответа. Это первоначальное незнание можно измерить энтропией по той же формуле, по которой измеряется информация. Обозначив энтропию буквой
Мы видим, что формула такой энтропии совпадает с формулой Больцмана и, так же как и она, выражает степень беспорядка. Только если в термодинамике речь шла о беспорядке в расположении и движении молекул, то в теории информации этот беспорядок характеризует степень нашего незнания, неосведомлённости в данном вопросе, хаотичность и беспорядочность в поиске выбора верного ответа. Энтропия по существу представляет собой отрицательную информацию, и её точно так же можно измерять в битах.
Когда мы получаем сообщение, содержащее неизвестную прежде информацию, энтропия нашего незнания уменьшается. Величина этого уменьшения как раз и определяет количество полученной информации. Если до получения сообщения энтропия как мера нашего незнания была H0, а после его получения стала H1, то содержащаяся в сообщении информация будет равна H0 – H1.
Большая часть экзаменационных тестовых заданий построена так, что требуется выбрать один правильный ответ из четырёх предложенных. Если вам ничего не известно по заданному вопросу и у вас нет никаких предположений о верности любого из вариантов, то энтропия задания для вас равна двоичному логарифму четырёх, т. е. 2. Когда вы узнаете точный ответ, энтропия станет равной нулю, и вы получите два бита информации. Теперь представим себе более сложный вид теста. Предлагается пять вариантов ответов и сообщается, что три из них верны. Количество способов, которыми можно выбрать три варианта из пяти, равно десяти[4]. Энтропия этого задания, следовательно, составляет для вас log2 10, что приблизительно равно 3,3. Как видно, эта энтропия выше, чем в предыдущем случае, и решение этого теста содержит больше информации. Узнав точный ответ, вы получите 3,3 бита. Допустим, что какая-то «добрая душа» подсказала вам, что варианты ответов А и В верны. Если предположить, что вы доверяете этой подсказке, сколько бит информации вы получили? Для этого надо выяснить, какой стала для вас энтропия теста после получения подсказки. Вам теперь известно, что единственный оставшийся правильный ответ надо выбрать из вариантов Б, Г и Д, а следовательно, энтропия равна log2 3, что равняется примерно 1,6. Подсчитаем убыль энтропии, которая будет равна количеству содержащейся в подсказке информации. До получения подсказки энтропия задания была Н0 = 3,3 бита. После её получения она составила H1 = 1,6 бита. Отсюда получаем, что подсказка содержит 3,3 – 1,6 = 1,7 бита информации. Но пока вы продолжаете думать над тестом, другая «добрая душа» подсказывает, что ответ Д неверен. Сколько информации содержится в этом сообщении? Вы теперь не знаете ответа только на варианты Б и Г, один из которых верен, а другой – нет, и вероятность правильности любого ответа равна 1/2. Значит, оставшаяся энтропия теста составляет для вас 1 бит, в то время как до получения второй подсказки она равнялась 1,6 бита. А это означает, что последняя подсказка содержала 0,6 бит информации.
1. Какая связь существует между полученной информацией и числом необходимых вопросов, которые требуется задать для получения точного ответа?
2. Что измеряется энтропией в теории информации?
3. Как связано изменение энтропии с полученной информацией?
1. На экзамене задан вопрос: «Какая из планет Солнечной системы находится ближе всех к Солнцу?» Названия планет экзаменуемому известны, но об их положении он ничего не знает. Какова энтропия экзаменуемого по этому вопросу? Какое количество информации он получит, узнав, что это Меркурий?
2. Экзаменуемому подсказывают, что ближайшая к Солнцу планета – это не Земля и не Марс. Сколько информации содержит эта подсказка?
§ 11 Свойства информации и двоичная система счисления
Все люди делятся на десять категорий: на тех, кто понимает двоичную систему счисления, и на тех, кто её не понимает.
Мы рассмотрели случаи, когда вероятности всех возможных исходов представляются одинаковыми. Но так бывает далеко не всегда. Очень часто один вариант представляется нам более вероятным, а другой – менее вероятным. Какова будет энтропия в этом случае? К. Шеннон вывел формулу, которая позволяет вычислить энтропию при этом условии. Предположим, что имеется всего два варианта. Вам сегодня надо сдавать экзамен, на котором могут задать 10 вопросов, из которых 9 вы знаете блестяще, а по одному совсем не подготовились. Вероятность удачной сдачи экзамена равна, таким образом, 9/10, а провала соответственно 1/10. В назначенное время вы приходите на экзамен и получаете вопрос. Этот вопрос может либо обрадовать вас, либо расстроить. Какой будет информация в том и другом случае? Мы знаем, что информация тем больше, чем сильнее вы удивитесь, узнав результат. Естественно, удивление, а значит и полученная информация, будет больше, если вам достанется «неудачный» вопрос. Поскольку информация равна двоичному логарифму вероятности того, что полученный вопрос будет «удачным» или «неудачным», взятому с обратным знаком, то в первом случае Jудачи = -1og2 9/10 = 0,15, а во втором JНеудачи = -1og2 1∕l0 = 0,33 Как видно, информация, полученная в случае маловероятной «неудачи», более чем в два раза выше той, которую мы получим в случае гораздо более вероятной «удачи». Теперь с учётом всего, что нам известно, подумаем, какова была для нас энтропия, касающаяся исхода экзамена. Мы знали, что, скорее всего (с вероятностью 0,9), получим небольшую информацию, но в одном случае из десяти можем получить (в нашем случае, к сожалению) информацию, значительно большую. Это означает, что,
Вычислим энтропию для нашего примера со сдачей экзамена. Вероятность успешной сдачи составляет 0,9, а её двоичный логарифм равен -0,15.
Вероятность провала равна 0,1, а её логарифм по основанию 2 соответствует -0,33. Значит, энтропия равна:
Эта величина выражается в битах и означает степень нашей неосведомлённости по поводу результата экзамена.
Предположим теперь, что мы имеем дело с неизвестным учащимся, про степень подготовки которого мы
В реальной жизни при выборе решения мы почти всегда исходим из того, что обладаем некоторой предварительной информацией по этому вопросу. Эта информация снижает исходную энтропию выбора. Например, нам пришлось задать всего одиннадцать вопросов для того, чтобы узнать, что загадан именно Ньютон. Предварительная информация перед угадыванием заключалась в том, что задуманным должен быть человек, скорее всего известный как загадывающему, так и отгадывающему. Вряд ли игрок имел в виду младшего сына любимого раба римского сенатора Информациуса, жившего во II в. до н. э. Сколько на Земле жило достаточно общеизвестных людей? Надо думать, что не более нескольких тысяч. Если для отгадывания Ньютона нам пришлось задать одиннадцать вопросов, значит, полученная информация составила 11 бит, а количество возможных вариантов выбора было равно 211 = 2048. Вряд ли количество известных всем знаменитостей намного больше этого числа. Ну, допустим, что играющие – очень эрудированные люди и знают в пять раз больше знаменитых людей, т. е. около десяти тысяч человек. В этом случае для угадывания им будет достаточно задать не более четырнадцати вопросов, так как логарифм 10 000 по основанию 2 равен приблизительно 13,3.
А что будет в том случае, если мы не имеем никакой предварительной информации? Допустим, что мы имеем дело с авантюристом, который всё-таки загадает младшего сына любимого раба. Вы думаете, что для отгадывания надо будет задать невероятно большое число вопросов? Вовсе нет. Количество всех людей, живших на Земле в обозримый исторический период, вряд ли превышает 10 млрд. А двоичный логарифм этого числа равен 29,9. Так что, задав всего 30 вопросов, вы можете угадать любого человека из всех когда-либо живших. Разумеется, для этого требуется умение правильно задавать вопросы.
В этом заключается одна из особенностей информации – её количество растёт значительно медленнее, чем число вариантов выбора. Это связано с тем, что информация представляет собой логарифм числа выборов, а логарифмическая функция обладает такой особенностью, что при увеличении аргумента
Это свойство информации многих очень удивляет, но именно оно представляет огромную ценность для создания компьютеров, где используют так называемую двоичную систему кодирования информации. С помощью только двух цифр – 0 и 1 – выражают любое число. В десятичной системе, которую мы обычно используем, – десять цифр от 0 до 9. Следующее число пишется как 10, что означает один полный десяток и ноль цифр второго десятка. Затем мы увеличиваем число единиц во втором десятке, пока не дойдём до 19. Число 20 говорит нам, что имеется два полных десятка и ни одного числа третьего десятка. Так продолжается до тех пор, пока счёт не достигнет 99. После этого мы добавляем ещё один разряд – сотни, т. е. квадраты десяток. Число 145 означает, что в нём содержится одна сотня, четыре десятка второй сотни и пять единиц пятого десятка второй сотни. Далее мы продолжаем счёт, вводя, когда потребуется, третьи, четвёртые и дальнейшие степени десяти.
В двоичной системе нет цифр, означающих числа, большие единицы. Поэтому уже для обозначения двойки нам приходится использовать число 10, которое означает: «одна полная двойка и ноль чисел во второй двойке». Далее идёт число 3, которое пишется как 11: «одна полная двойка и одно число второй двойки». Следующим числом будет 4, а это квадрат двойки. Значит, и писать его надо так, как в десятичной системе пишется квадрат десятки, т. е. 100. Теперь посмотрим, как можно изобразить любое число в двоичной системе. Допустим, мы хотим это сделать для тех же ста сорока пяти. Сначала надо узнать, сколько в этом числе содержится целых степеней двойки. Находим, что 27 равно 128, что меньше 145, а 28 – уже 256, что превышает это число. Значит, сто сорок пять равно двум в седьмой степени (27), что записывается как единица с семью нулями (10 000 000), плюс 17 (145 – 128). Выразим 17 в двоичной системе: 16, т. е. 24 (записывается как единица с четырьмя нулями – 10 000), плюс 1. После этого посмотрим, как выглядит число 145 в двоичной системе. Для этого надо сложить все числа, которые мы получали в процессе вычисления: 10 000 000, 10 000 и 1. Следовательно, выражая это число в двоичной системе, мы получаем: 10 000 000 + 10 000 + 1 = 10 010 001.
Казалось бы, такая система слишком громоздка и неудобна для записи и вычислений. Но она является незаменимой в создании электронных устройств и вычислительной техники. Все электронные устройства состоят из отдельных элементов. Чем меньше значений может принимать каждый элемент, тем проще изготовить такие элементы. Две цифры двоичной системы могут быть легко представлены многими физическими явлениями: есть ток – нет тока, температура выше заданной – температура ниже заданной и т. п. Кроме того, чем меньше число возможных состояний элемента, тем надёжнее и быстрее он может работать. К тому же техническим устройствам значительно проще выполнять арифметические вычисления, используя двоичную систему. Например, для того чтобы сложить числа 12 и 36, надо закодировать в памяти машины значения четырёх цифр, в то время как в двоичной системе эта операция выглядит так: (23 + 22) + + (25 + 22) = 1000 + 100 + 100 000 + 100. Поставьте себя на место машины, и вы поймёте, что такую операцию выполнить значительно проще.
Поскольку в двоичной системе существует всего две цифры, то при решении какой-либо задачи требуется на каждом шагу рассуждения или вычисления выбирать один из двух одинаковых вариантов, т. е. тратить информацию, равную одному биту. А так как количество возможных вариантов решения возрастает значительно быстрее, чем число сделанных шагов, то, используя сравнительно небольшое количество двоичных действий, можно осуществить выбор из огромного числа разнообразных решений или комбинаций. Именно на этом принципе строится работа современных компьютеров.
1. Как зависит энтропия незнания ответа на какой-либо вопрос от того, насколько равны вероятности всех возможных ответов на него?
2. Как изменяется величина информации с ростом числа возможных ответов на интересующий нас вопрос?
3. Чем различается написание чисел в десятичной и двоичной системах?
1. Подсчитайте, сколько вопросов, допускающих ответы «да» или «нет», требуется задать для того, чтобы установить одного из жителей города с населением 65 тыс. человек.
2. Выразите номер этого параграфа в двоичной системе.
§ 12 Ценность и избыточность информации
…Нелегко с Кощеем сладить: смерть его на конце иглы, та игла в яйце, то яйцо в утке, та утка в зайце, тот заяц в сундуке, а сундук стоит на высоком дубу, и то дерево Кощей как свой глаз бережёт.
Используя уравнения теории информации, мы можем вычислить, какое количество информации содержится в полученном сообщении. Но оценив значение информации в нашей жизни и в окружающем нас мире, мы увидим, что это количество далеко не всегда определяет важность, ценность или полезность этого сообщения. Предположим, вы претендуете на престижное место работы или на место для обучения в известном университете. После предварительного отбора вы становитесь одним из двух претендентов на это место, причём шансы у обоих приблизительно равны. Вы переживаете и не даёте себе покоя в течение нескольких дней и наконец получаете сообщение, в котором говорится, что вы приняты. Это сообщение радикально меняет вашу жизнь, вашему счастью нет предела… А сейчас задумайтесь, сколько информации оно вам принесло. Всего один бит. Теперь представьте себе, что вы уронили монету и, перед тем как её поднять, заметили, что она лежит цифрой кверху. Это наблюдение принесло вам один бит информации, т. е. ровно столько же, сколько в предыдущем случае.
Но согласитесь, что оценка и последствия двух этих событий между собой несоизмеримы.
Поэтому в современной информатике помимо количества информации рассматривается её ценность. Ценность информации зависит от цели, которую преследует получатель этой информации. Если цель наверняка достижима, то можно определить ценность информации в соответствии с тем, насколько она уменьшает усилия или время, требуемые для достижения этой цели. Такой ценностью обладает информация, содержащаяся в поисковых системах, справочниках и каталогах. Если же достижение цели необязательно, то, для того чтобы определить ценность информации, можно воспользоваться такой формулой:
В этой формуле
Ценность информации далеко не всегда зависит от её количества. Предположим, что вам предложено решить тестовое задание, где из четырёх возможных ответов требуется выбрать один верный. Узнав ответ, вы получите информацию, величина которой равна 2 битам, а ценность – единице. Если же вам предложат выбор из шестнадцати вариантов, то в этом случае правильный ответ принесёт вам 4 бита, а ценность полученной информации останется прежней, так как и в том и в другом случае вы в результате достигаете поставленной цели – справиться с заданием. Информацию, которая не содержит никакой ценности, называют
Важной характеристикой информации служит её избыточность. Избыточная информация присутствует практически в любом тексте. Изначально избыточность текста появляется из-за того, что вероятность встречаемости букв в алфавите русского, как и любого другого, языка неодинакова. Если проанализировать встречаемость различных букв в русском тексте, то мы увидим, что в половине случаев мы обнаружим буквы О, Е, А, И, Т, Р или Н, и меньше 5 % придётся на долю букв Ю, Ж, Х, Щ, Ф, Ш, Э, Ц, И, Ъ. С учётом неравномерной встречаемости букв энтропия алфавита русского языка равна не 5 битам, а всего 4,39 бита. Отношение максимальной энтропии к реальной и определяет её избыточность.
В действительности избыточность языка оказывается ещё большей из-за того, что в языке существуют устойчивые пары или тройки сочетаний букв, вероятность появления которых значительно больше, чем у других сочетаний. Если учесть вероятность появления различных сочетаний двух букв, то энтропия становится равной 3,52, а при учёте вероятности сочетаний трёх букв – 3,05 бит/букву[5]. Благодаря этому часто даже при потере значительной части букв текст удаётся восстановить, т. е. извлечь из него всю изначально содержащуюся информацию. Классический пример можно найти в книге Жюля Верна «Дети капитана Гранта». В записке, которую извлекли из желудка акулы, было смыто морской водой 170 букв из 250. Паганель не смог полностью расшифровать испорченный текст, но ему удалось извлечь из него достаточно информации, чтобы после нескольких попыток найти потерявшуюся экспедицию. Тексты с меньшим числом потерянных знаков часто можно восстановить полностью.
Допустим, вам встретилось слово, в котором есть такое сочетание: «Б, затем утерянный знак, затем Ф». Восстановить это испорченное слово будет не так уж трудно. Скорее всего, в голову придёт что-то съедобное: «бифштекс», «ростбиф», «бефстроганов» или «буфет»; может быть, вспомните ещё «буфер», а вот дальше у вас начнутся затруднения. Набор будет очень ограничен ещё из-за того, что буква «Ф» в русском языке встречается очень редко, практически только в словах, заимствованных из других языков. Но и при более простых сочетаниях восстановить текст нетрудно в том случае, когда небольшая его часть утрачена. Особенно просто это сделать с текстом, в котором содержатся знакомые, часто употребляемые выражения. Сможете ли вы, например, прочитать такое объявление:
«До..лни…ь.ые к.н.уль.а..и п. м…ма..ке .у..т пр.в..ить.я в. …рник .осл. пя..г. ур..а»?
Из этого объявления «выпала» почти половина знаков, и тем не менее нетрудно восстановить его полный текст[6].
Различные виды текстов обладают различным количеством избыточной информации. Если вспомнить, что мерой величины информации служит её неожиданность, то часто можно услышать или прочесть в сети тексты, содержащие практически нулевую информацию. Вот типичный пример:
–
–
–
–
–
–
–
–
Часто большой избыточной информацией обладают художественные, особенно поэтические тексты. У некоторых поэтов-авангардистов встречаются тексты, абсолютно лишённые какого-либо смысла, где вся информация основана только на грамматических связях. Вот отрывок из произведения русского поэта начала прошлого века Велимира Хлебникова:
Каждая ситуация, каждый текст требуют своего уровня избыточной информации. Преимуществом избытка информации может быть либо эстетическое качество художественного произведения, либо его лучшее понимание. Если бы тексты не содержали избыточной информации, их восстановление после повреждения стало бы невозможным.
Рис. 21. Сообщения, не содержащие избыточной информации
Поэтому в тех случаях, когда цена ошибки в понимании текста может быть слишком высокой, используют сообщения с большой избыточной информацией. К ним относятся, например, переговоры авиадиспетчеров. С другой стороны, избыточная информация требует большего времени для своего восприятия и большего количества знаков для передачи сообщения. Поэтому в тех случаях, когда сообщение требует конкретных, обязательных действий, оно не содержит или почти не содержит избыточной информации. Таковы, например, указатели «Прохода нет», «Посторонним вход воспрещён», «Высокое напряжение» и т. п. (рис. 21).
1. От чего зависит ценность полученной информации?
2. Как называется информация, не несущая никакой ценности?
3. С чем связана избыточность информации языка?
4. В каких случаях большая избыточность текста оказывается полезной? Приведите примеры помимо тех, что указаны в параграфе.
1. Придумайте примеры высказываний с минимальной и избыточной информацией.
2. Оцените значение информации о современном обществе. Раскройте смысл высказывания премьер-министра Великобритании Уинстона Черчилля «Кто владеет информацией, тот владеет миром».
§ 13 Самоорганизующиеся системы
Вернёмся к вопросам, связанным с термодинамикой и термодинамическими системами. Мы знаем, что в том случае, когда система изолирована от внешней среды, в ней либо не происходит никаких процессов, либо происходят процессы, сопровождающиеся ростом энтропии и увеличением хаоса. Именно такие системы изучает классическая термодинамика. Но в действительности нам почти никогда не приходится иметь дело с изолированными системами. Все живые организмы – это открытые системы, которые постоянно поглощают и выделяют вещество и энергию. Неживые системы тоже в большинстве своём являются открытыми – энергия, приходящая от Солнца, нагревает моря или скалы, что приводит к испарению воды и изменениям скорости некоторых химических реакций (рис. 22). Представим себе систему, которая поглощает из некоторой области окружающей среды вещество или энергию и одновременно отдаёт это вещество или энергию в другую область окружающей среды. Тогда мы говорим, что через систему проходит