Информация будем определять через ее основные свойства (т.к. наряду с материей и энергией она является первичным понятием нашего мира и поэтому в строгом смысле не может быть определена):

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

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

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

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

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

Неопределенность неотъемлема от понятия вероятности. Уменьшение неопределенности всегда связано с выбором (отбором) одного или нескольких элементов (альтернатив) из некоторой их совокупности. Такая взаимная обратимость понятий вероятности и неопределенности послужила основой для использования понятия вероятности при измерении степени неопределенность в теории информации. Если предположить, что любой из четырех ответов на вопросы равновероятен, то его вероятность во всех вопросах равна 1/4 .

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

Теперь попробуем сравнить следующие два вопроса: на каком из четырех курсов техникума учится студент? Как упадет монета при подбрасывании: вверх «гербом» или «цифрой»? В первом случае возможны четыре равновероятных ответа, во втором – два. Следовательно, вероятность какого-то ответа во втором случае больше, чем в первом (1/2 > 1/4 ), в то время как неопределенность, снимаемая ответами, больше в первом случае. Любой из возможных ответов на первый вопрос снимает большую неопределенность, чем любой ответ на второй вопрос. Поэтому ответ на первый вопрос несет больше информации! Следовательно, чем меньше вероятность какого-либо события, тем большую неопределенность снимает сообщение о его появлении и, следовательно, тем большую информацию оно несет.

Предположим, что какое-то событие имеет m равновероятных исходов. Таким событием может быть, например, появление любого символа из алфавита, содержащего m таких символов. Как измерить количество информации, которое может быть передано при помощи такого алфавита? Это можно сделать, определив число N возможных сообщений, которые могут быть переданы при помощи этого алфавита. Если сообщение формируется из одного символа, то N = m , если из двух, то N = m · m = m 2 . Если сообщение содержит n символов (n – длина сообщения), то N = mn . Казалось бы, искомая мера количества информации найдена. Ее можно понимать как меру неопределенности исхода опыта, если под опытом подразумевать случайный выбор какого-либо сообщения из некоторого числа возможных. Однако эта мера не совсем удобна.

При наличии алфавита, состоящего из одного символа, т.е. когда m = 1 , возможно появление только этого символа. Следовательно, неопределенности в этом случае не существует, и появление этого символа не несет никакой информации. Между тем, значение N при m = 1 не обращается в нуль. Для двух независимых источников сообщений (или алфавита) с N 1 и N 2 числом возможных сообщений общее число возможных сообщений N = N 1 N 2 , в то время как логичнее было бы считать, что количество информации, получаемое от двух независимых источников, должно быть не произведением, а суммой составляющих величин.

Выход из положения был найден Р. Хартли , который предложил информацию I , приходящуюся на одно сообщение, определять логарифмом общего числа возможных сообщений N :

I (N) = log N

Если же все множество возможных сообщений состоит из одного (N = m = 1 ), то

I (N) = log 1 = 0 ,

что соответствует отсутствию информации в этом случае. При наличии независимых источников информации с N 1 и N 2 числом возможных сообщений

I (N) = log N = log N 1 N 2 = log N 1 + log N 2

т.е. количество информации, приходящееся на одно сообщение, равно сумме количеств информации, которые были бы получены от двух независимых источников, взятых порознь.

Формула, предложенная Хартли , удовлетворяет предъявленным требованиям. Поэтому ее можно использовать для измерения количества информации. Если возможность появления любого символа алфавита равновероятна (а мы до сих пор предполагали, что это именно так), то эта вероятность р= 1/m . Полагая, что N = m , получим

I = log N = log m = log (1/p) = – log p ,

Полученная формула позволяет для некоторых случаев определить количество информации. Однако для практических целей необходимо задаться единицей его измерения. Для этого предположим, что информация – это устраненная неопределенность. Тогда в простейшем случае неопределенности выбор будет производиться между двумя взаимоисключающими друг друга равновероятными сообщениями, например между двумя качественными признаками: положительным и отрицательным импульсами, импульсом и паузой и т.п.

Количество информации, переданное в этом простейшем случае, наиболее удобно принять за единицу количества информации. Полученная единица количества информации, представляющая собой выбор из двух равновероятных событий, получила название двоичной единицы, или бита. (Название bit образовано из двух начальных и последней букв английского выражения binary unit , что значит двоичная единица.)

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

которого высока и, соответственно, низка степень неожиданности, несет немного информации.

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

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

Наиболее широкое распространение при определении среднего количества информации, которое содержится в сообщениях от источников самой разной природы, получил подход. К Шеннона .

Рассмотрим следующую ситуацию. Источник передает элементарные сигналы k различных типов. Проследим за достаточно длинным отрезком сообщения. Пусть в нем имеется N 1 сигналов первого типа, N 2 сигналов второго типа, ..., N k сигналов k -го типа, причем N 1 + N 2 + ... + N k = N – общее число сигналов в наблюдаемом отрезке, f 1 , f 2 , ..., f k – частоты соответствующих сигналов. При возрастании длины отрезка сообщения каждая из частот стремится к фиксированному пределу, т.е.

lim f i = p i , (i = 1, 2, ..., k) ,

где р i можно считать вероятностью сигнала. Предположим, получен сигнал i -го типа с вероятностью р i , содержащий – log p i единиц информации. В рассматриваемом отрезке i -й сигнал встретится примерно Np i раз (будем считать, что N достаточно велико), и общая информация, доставленная сигналами этого типа, будет равна произведению Np i log р i . То же относится к сигналам любого другого типа, поэтому полное количество информации, доставленное отрезком из N сигналов, будет примерно равно. Чтобы определить среднее количество информации, приходящееся на один сигнал, т.е. удельную информативность источника, нужно это число разделить на N . При неограниченном росте приблизительное равенство перейдет в точное.

В результате будет получено асимптотическое соотношение – формула Шеннона . Оказалось, что формула, предложенная Хартли , представляет собой частный случай более общей формулы Шеннона .

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

| Планирование уроков и материалы к урокам | 11 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю) | Количество информации

Уроки 2 - 3
Информация и вероятность. Формула Хартли. Формула Шеннона
(§1. Количество информации)

Ответить на этот вопрос стало возможно только после того, как вы изучили логарифмы в курсе математики. Из формулы

сразу следует, что I - это степень, в которую нужно возвести 2, чтобы получить N, т. е. логарифм:

Эта формула называется формулой Хартли в честь американского инженера Ральфа Хартли, который предложил её в 1928 г.

Пусть, например, на лётном поле стоят 10 самолётов (с номерами от 1 до 10) и известно, что один из них летит в Санкт-Петербург.

Сколько информации в сообщении «Самолёт № 2 летит в Санкт-Петербург»? У нас есть 10 вариантов, из которых выбирается один, поэтому по формуле Хартли количество информации равно

I = log 2 10 ≈ 3,322 бита.

Обратите внимание, что для значений N, которые не равны целой степени числа 2, количество информации в битах - дробное число.

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

I = log 2 50 ≈ 5,644 бита.

Если сообщение содержит 100 символов, его общий информационный объём примерно равен

5,644 100 = 564,4 бита.

В общем случае объём сообщения длиной L символов, использующего алфавит из N символов, равен I = L log 2 N.

Такой подход к определению количества информации называют алфавитным. Конечно, на практике невозможно использовать для кодирования символа нецелое число битов, поэтому используют первое целое число, которое больше теоретически рассчитанного значения. Например, при использовании алфавита из 50 символов каждый символ будет закодирован с помощью 6 битов (50 ≤ 2 6 = 64).

Сколько разных сообщений можно передать, если известен алфавит и длина сообщения? Предположим, что для кодирования сообщения используются 4 буквы, например «А», «Б», «В» и «Г», и сообщение состоит из двух символов. Поскольку каждый символ может быть выбран 4 разными способами, на каждый вариант выбора первого символа есть 4 варианта выбора второго. Поэтому общее число разных двухбуквенных сообщений вычисляется как 4 4 = 4 2 = 16. Если в сообщение добавить ещё один символ, то для каждой из 16 комбинаций первых двух символов третий можно выбрать четырьмя способами, так что число разных трёхсимвольных сообщений равно 4 4 4 = 4 3 = 64.

В общем случае, если используется алфавит из N символов, то количество разных возможных сообщений длиной L символов равно Q = N L .

Следующая страница

Американский инженер Р. Хартли в 1928 г. процесс получения информации рассматривал как выбор одного сообщения из конечного наперёд заданного множества из N равновероятных сообщений, а количество информации I, содержащееся в выбранном сообщении, определял как двоичный логарифм N.

Формула Хартли: I = log 2 N

Допустим, нужно угадать одно число из набора чисел от единицы до ста. По формуле Хартли можно вычислить, какое количество информации для этого требуется: I = log 2 100  6,644. Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 единицы информации.

Приведем другие примеры равновероятных сообщений :

при бросании монеты: "выпала решка" , "выпал орел" ;

на странице книги: "количество букв чётное" , "количество букв нечётное" .

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

Для задач такого рода американский учёный Клод Шеннон предложил в 1948 г. другую формулу определения количества информации, учитывающую возможную неодинаковую вероятность сообщений в наборе.

Формула Шеннона: I = - (p 1 log 2 p 1 + p 2 log 2 p 2 + . . . + p N log 2 p N),
где p i - вероятность того, что именно i -е сообщение выделено в наборе из N сообщений.

Легко заметить, что если вероятности p 1 , ..., p N равны, то каждая из них равна 1 / N , и формула Шеннона превращается в формулу Хартли.

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

В качестве единицы информации Клод Шеннон предложил принять один бит (англ . bit - bi nary digit - двоичная цифра).

Бит в теории информации - количество информации, необходимое для различения двух равновероятных сообщений (типа "орел"-"решка", "чет"-"нечет" и т.п.).

В вычислительной технике битом называют наименьшую "порцию" памяти компьютера, необходимую для хранения одного из двух знаков "0" и "1", используемых для внутримашинного представления данных и команд.

Бит - слишком мелкая единица измерения. На практике чаще применяется более крупная единица - байт , равная восьми битам. Именно восемь битов требуется для того, чтобы закодировать любой из 256 символов алфавита клавиатуры компьютера (256=2 8).

Широко используются также ещё более крупные производные единицы информации :

1 Килобайт (Кбайт) = 1024 байт = 2 10 байт,

1 Мегабайт (Мбайт) = 1024 Кбайт = 2 20 байт,

1 Гигабайт (Гбайт) = 1024 Мбайт = 2 30 байт.

В последнее время в связи с увеличением объёмов обрабатываемой информации входят в употребление такие производные единицы, как:

1 Терабайт (Тбайт) = 1024 Гбайт = 2 40 байт,

1 Петабайт (Пбайт) = 1024 Тбайт = 2 50 байт.

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

Что можно делать с информацией?

Информацию можно:

Все эти процессы, связанные с определенными операциями над информацией, называются информационными процессами.

Свойства информации.

Свойства информации:

достоверность;

ценность;

своевременность; понятность;

доступность;

краткость;

Информация достоверна, если она отражает истинное положение дел . Недостоверная информация может привести к неправильному пониманию или принятию неправильных решений.

Достоверная информация со временем может стать недостоверной , так как она обладает свойством устаревать , то есть перестаёт отражать истинное положение дел .

Информация полна, если её достаточно для понимания и принятия решений . Как неполная, так и избыточная информация сдерживает принятие решений или может повлечь ошибки .

Точность информации определяется степенью ее близости к реальному состоянию объекта, процесса, явления и т.п.

Ценность информации зависит от того, насколько она важна для решения задачи , а также от того, насколько в дальнейшем она найдёт применение в каких-либо видах деятельности человека .

Только своевременно полученная информация может принести ожидаемую пользу . Одинаково нежелательны как преждевременная подача информации (когда она ещё не может быть усвоена), так и её задержка .

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

Информация становится понятной , если она выражена языком, на котором говорят те, кому предназначена эта информация.

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

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

Обработка информации.

Обработка информации - получение одних информационных объектов из других информационных объектов путем выполнения некоторых алгоритмов.

Обработка является одной из основных операций, выполняемых над информацией, и главным средством увеличения объёма и разнообразия информации.

Средства обработки информации - это всевозможные устройства и системы, созданные человечеством, и в первую очередь, компьютер - универсальная машина для обработки информации.

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

Похожая ситуация сложилась и в отношении информации. Р. Хартли в 1928, а затем К. Шеннон в 1948 предложили формулы для вычисления количества информации, однако на вопрос о том, что такое информация, они так и не ответили. В теории связи информация выступает в виде различных сообщений: например, букв или цифр, как в телеграфии, или в виде непрерывной функции времени, как при телефонии или радиовещании. В любом из указанных примеров, в конечном итоге, задача состоит в передаче смыслового содержания человеческой речи. В свою очередь, человеческая речь может быть представлена в звуковых колебаниях или в письменном изложении.

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

Р. Хартли первым ввел в теорию передачи информации методологию «измерения количества информации». При этом Р. Хартли считал, что информация, которую он собирался измерять, это «… группа физических символов - слов, точек, тире и т. п., имеющих по общему соглашению известный смысл для корреспондирующих сторон». Таким образом, Хартли ставил перед собой задачу ввести какую-то меру для измерения кодированной информации.

Пусть передаётся последовательность из n символов а 1 а 2 а 3 а n , каждый из которых принадлежит алфавиту А m , содержащему m символов. Чему равно число К различных вариантов таких последовательностей? Если n = 1 (передаётся один символ), то K = m; если n=2 (передаётся последовательность из 2-х символов), то K = m*m = m 2 ; в общем случае для последовательности из n символов получим

Количество информации, содержащееся в такой последовательности, Хартли предложил вычислять как логарифм числа K по основанию 2:

I = Log 2 K, (2.1)

где K = m n .

То есть, количество информации, содержащееся в последовательности из n символов из алфавита A m , в соответствии с формулой Хартли равно

I = Log 2 (m n) = n Log 2 m . (2.2)

Замечание 1. Хартли предполагал, что все символы алфавита A m могут с равной вероятностью (частотой) встретиться в любом месте сообщения. Это условие нарушается для алфавитов естественных языков: например, не все буквы русского алфавита встречаются в тексте с одинаковой частотой.

Замечание 2. Любое сообщение длины n в алфавите A m будет содержать одинаковое количество информации. Например, в алфавите {0; 1} сообщения 00111, 11001 и 10101 содержат одинаковое количество информации. Это означает, что при вычислении количества информации, содержащегося в сообщении, мы отвлекаемся от его смыслового содержания. «Осмысленное» сообщение и сообщение, полученное из него произвольной перестановкой символов, будут содержать одинаковое количество информации.

Пример. В телеграфном сообщении используются два символа - точка (.) и тире (-), т.е. алфавит состоит из m = 2 символов. Тогда при передаче одного символа (n =1) количество информации I = Log 2 2 = 1. Это количество было принято за единицу измерения количества информации и называется 1 бит (от английского binary unit = bit ). Если телеграфное сообщение в алфавите {. ; -} содержит n символов, то количество информации I = n Log 2 2 = n (бит).

С помощью символов 0 и 1 кодируется информация в компьютере и при передаче в вычислительных сетях, т.е. алфавит состоит из двух символов {0 ; 1}; один символ и в этом случае содержит I = Log 2 2 = 1 бит информации, поэтому сообщение длиной n символов в алфавите {0 ; 1} в соответствии с формулой Хартли (2.2) будет содержать n бит информации.

Если рассматривать передачу сообщений в алфавите русского языка, состоящего из 33 букв, то количество информации, содержащееся в сообщении из n символов, вычисленное по формуле Хартли, равно I = n*Log 2 33 » n* 5.0444 бит. Английский алфавит содержит 26 букв, один символ содержит Log 2 26 » 4.7 бит, поэтому сообщение из n символов, вычисленное по формуле Хартли, содержит n* Log 2 26 » 4.7 *n бит информации. Однако, этот результат не является правильным, так как не все буквы встречаются в тексте с одинаковой частотой. Кроме того, к буквам алфавита надо добавить разделительные знаки: пробел, точку, запятую и др.

Формула (2.1) внешне напоминает формулу Больцмана для вычисления энтропии системы с N равновероятными микросостояниями:

S= - k*Ln(W), (2.3)

где k - постоянная Больцмана = 1,38*10 -23 , а W- вероятность спонтанного принятия одного из микросостояний системы в единицу времени t = 10 -13 сек., W = 1/N, т.е.

S= -k*Ln(1/N) = k*Ln(N), (2.4)

что полностью согласуется с формулой (2.1) за исключением множителя k и основания логарифма. Из-за этого внешнего сходства величину Log 2 K в теории информации также называют энтропией и обозначают символом H. Информационная энтропия - это мера неопределённости состояния некоторой случайной величины (физической системы) с конечным или счётным числом состояний. Случайная величина (с.в.) - это величина, которая в результате эксперимента или наблюдения принимает числовое значение, заранее неизвестно какое.

Итак, пусть X - случайная величина, которая может принимать N различных значений x 1 , x 2 , … x N ; если все значения с.в. X равновероятны, то энтропия (мера неопределённости) величины X равна:

H(X) = Log 2 N. (2.5)

Замечание. Если случайная величина (система) может находиться только в одном состоянии (N=1), то её энтропия равна 0. Фактически это уже не случайная величина. Неопределённость системы тем выше, чем больше число её возможных равновероятных состояний.

Энтропия и количество информации измеряются в одних и тех же единицах - в битах.

Определение. 1 бит - это энтропия системы с двумя равновероятными состояниями.

Пусть система X может находиться в двух состояниях x1 и x2 с равной вероятностью, т.е. N = 2; тогда её энтропия H(X) = Log 2 2 = 1 бит. Пример такой системы даёт нам монета, при подбрасывании которой выпадает либо орёл (x1), либо решка (x2). Если монета «правильная», то вероятность выпадения орла или решки одинаковая и равна 1/2.

Дадим ещё одно определение единицы измерения информации.

Определение. Ответ на вопрос любой природы (любого характера) содержит 1 бит информации, если он с равной вероятностью может быть «да» или «нет».

Пример. Игра в «пусто-густо». Вы прячете мелкий предмет в одной руке и предлагаете партнёру угадать, в какой руке вы его спрятали. Он спрашивает вас « в левой руке?» (или просто выбирает руку: левую или правую). Вы отвечаете «да», если он угадал, или «нет», в противном случае. При любом варианте ответа партнёр получает 1 бит информации, а неопределённость ситуации полностью снимается.

Формулу Хартли можно использовать при решении задач на определение выделенного элемента некоторого заданного множества. Этот результат можно сформулировать в виде следующего правила.

Если в заданном множестве M, состоящем из N элементов, выделен некоторый элемент x, о котором ничего более неизвестно, то для определения этого элемента необходимо получить Log 2 N бит информации.

Рассмотрим несколько задач на применение формулы Хартли.

Задача 1. Некто задумал натуральное число в диапазоне от 1 до 32. Какое минимальное число вопросов надо задать, чтобы гарантированно угадать задуманное (выделенное) число. Ответы могут быть только «да» или «нет».

Комментарий. Можно попытаться угадать задуманное число простым перебором. Если повезёт, то придётся задать только один вопрос, а при самом неудачном варианте перебора придётся задать 31 вопрос. В предложенной задаче нужно определить минимальное число вопросов, с помощью которых вы гарантированно определяете задуманное число.

Решение. По формуле Хартли можно вычислить количество информации, которое необходимо получить для определения выделенного элемента x из множества целых чисел {1,2,3 32}. Для этого необходимо получить Н = Log 2 32 = 5 бит информации. Вопросы надо задавать так, чтобы ответы на них были равновероятны. Тогда ответ на каждый такой вопрос будет приносить 1 бит информации. Например, можно разбить числа на две равные группы от 1 до 16 и от 17 до 32 и спросить, в какой группе находится задуманное число. Далее, аналогично следует поступить с выделенной группой, которая содержит уже лишь 16 чисел, и т.д. Пусть, например, задумано число 7.

Вопрос №1: Задуманное число принадлежит множеству {17; 32}? Ответ «нет» приносит вам 1 бит информации. Мы теперь знаем, что число принадлежит множеству {1 ; 16}.

Вопрос №2: Задуманное число принадлежит множеству {1 ; 8}? Ответ «да» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {1 ; 8}.

Вопрос №3: Задуманное число принадлежит множеству {1 ; 4}? Ответ «нет» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {5 ; 8}.

Вопрос №4: Задуманное число принадлежит множеству {7 ; 8}? Ответ «да» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {7 ; 8}.

Вопрос №5: Задуманное число равно 8? Ответ «нет» приносит вам ещё 1 бит информации. Мы теперь знаем, что задуманное число равно 7. Задача решена. Было задано пять вопросов, в ответ получено 5 бит информации и определено задуманное число. ‚

Задача 2. (Задача о фальшивой монете). Имеется 27 монет, из которых 26 настоящих и одна фальшивая. Каково минимальное число взвешиваний на рычажных весах, за которое можно гарантированно определить одну фальшивую монету из 27, используя то, что фальшивая монета легче настоящей.

Рычажные весы имеют две чашки и с их помощью можно лишь установить, одинаково ли по весу содержимое чашек, и если нет, то содержимое какой из чашек тяжелее.

Решение. Это задача на определение одного выделенного элемента из 27. По формуле Хартли мы сразу можем определить количество информации, которое нужно получить для определения фальшивой монеты: оно равно I = Log 2 27 = Log 2 (3 3) = 3 Log 2 3 бит. Отметим, что ещё не зная стратегии взвешивания, можно сказать, сколько информации мы должны получить для решения задачи.

Если положить на чашки весов равное количество монет, то возможны три равновероятных исхода:

1. Левая чашка тяжелее правой (Л > П);

2. Левая чашка легче правой (Л < П);

3. Левая чашка находится в равновесии с правой (Л = П);

Система «рычажные весы» может находиться в трёх равновероятных состояниях, поэтому одно взвешивание даёт Log 2 3 бит информации. Всего для решения задачи надо получить I = 3 Log 2 3 бит информации, значит надо сделать три взвешивания для определения фальшивой монеты. Мы уже знаем минимальное число взвешиваний, но ещё не знаем, как их следует проводить. Стратегия должна быть такой, чтобы каждое взвешивание давало максимальное количество информации. Разделим все монеты на три равные кучки A, B и C по 9 штук в каждой. Фальшивая монета, обозначим её буквой f, может с равной вероятность находиться в любой из трёх кучек. Выберем любые две из них, например A и B, и взвесим их.

Возможны три исхода:

1) A тяжелее B (A > B); значит f Î B;

2) A легче B (A < B); значит f Î A;

3) A находится в равновесии с B (A = B); значит f Î С.

При любом исходе мы определим в какой кучке находится фальшивая монета f, но в этой кучке будет уже только 9 монет. Разобъём её на три равные кучки A1, B1, C1 по 3 монеты в каждой. Выберем любые две и взвесим их. Как и на предыдущем шаге, мы определим ту кучку монет, в которой находится фальшивая монета, но теперь кучка состоит только из трёх монет. Выберем любые две монеты и взвесим их. Это будет последнее, третье взвешивание, после которого мы найдём фальшивую монету.

Задача 3 . Не используя калькулятор, оцените с точность до одного бита энтропию системы, которая может с равной вероятностью находится в 50 состояниях.

Решение. По формуле Хартли H = Log 2 50. Оценим данное выражение.

Очевидно, 32 < 50 < 64; логарифмируем это неравенство à Log 2 32 < Log 2 50 < Log 2 64 à 5 < Log 2 50 < 6. Энтропия системы с точностью до 1 бита 5 < H < 6 . ‚

Задача 4. Известно, что энтропия системы составляет 7 бит. Определите число состояний этой системы, если известно, что все они равновероятны.

Решение. Обозначим через N число состояний системы. Так как все состояния равновероятны, то H = Log 2 N à N = 2 H , т.е. N = 2 7 = 128.

Мы уже упоминали, что формула Хартли – частный случай формулы Шеннона для равновероятных альтернатив.

Подставив в формулу (1) вместо p i его (в равновероятном случае не зависящее отi ) значение, получим:

Таким образом, формула Хартли выглядит очень просто:

(2)

Из нее явно следует, что чем больше количество альтернатив (N ), тем больше неопределенность (H ). Эти величины связаны в формуле (2) не линейно, а через двоичный логарифм. Логарифмирование по основанию 2 и приводит количество вариантов к единицам измерения информации – битам.

Заметьте, что энтропия будет являться целым числом лишь в том случае, если N является степенью числа 2, т.е. еслиN принадлежит ряду:{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048…}

Рис. 10. Зависимось энтропии от количества равновероятных вариантов выбора (равнозначных альтернатив).

Напомним, что такое логарифм.

Рис. 11. Нахождение логарифма b по основаниюa - это нахождениестепени , в которую нужно возвестиa , чтобы получитьb .

Логарифм по основанию 2 называется двоичным :

log 2 (8)=3 => 2 3 =8

log 2 (10)=3,32 => 2 3,32 =10

Логарифм по основанию 10 –называется десятичным :

log 10 (100)=2 => 10 2 =100

Основные свойства логарифма:

log(1)=0, т.к. любое число в нулевой степени дает 1;

log(a b)=b*log(a);

log(a*b)=log(a)+log(b);

log(a/b)=log(a)-log(b);

log(1/b)=0-log(b)=-log(b).

Для решения обратных задач, когда известна неопределенность (H ) или полученное в результате ее снятия количество информации (I ) и нужно определить какое количество равновероятных альтернатив соответствует возникновению этой неопределенности, используют обратную формулу Хартли, которая выглядит еще проще:

(3)

Например, если известно, что в результате определения того, что интересующий нас Коля Иванов живет на втором этаже, было получено 3 бита информации, то количество этажей в доме можно определить по формуле (3), как N =2 3 =8 этажей .

Если же вопрос стоит так: “в доме 8 этажей, какое количество информации мы получили, узнав, что интересующий нас Коля Иванов живет на втором этаже?”, нужно воспользоваться формулой (2): I = log 2 (8)=3 бита .

1. Количество информации, получаемой в процессе сообщения

До сих пор мы приводили формулы для расчета энтропии (неопределенности) H , указывая, чтоH в них можно заменять наI , потому что количество информации, получаемоепри полном снятии неопределенности некоторой ситуации, количественно равно начальной энтропии этой ситуации.

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

(4)

Для равновероятного случая , используя для расчета энтропии формулу Хартли, получим:

(5)

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

Исходя из (5) можно вывести следующее:

Если
, то
- полное снятие неопределенности, количество полученной в сообщении информации равно неопределенности, которая существовала до получения сообщения.

Если
, то
- неопределенности не изменилась, следовательно, информации получено не было.

Если
, то
=>
, если
,
=>
. Т.е. количество полученной информации будет положительной величиной, если в результате получения сообщения количество рассматриваемых альтернатив уменьшилось, и отрицательной, если увеличилось.

Если количество рассматриваемых альтернатив в результате получения сообщения уменьшилось вдвое, т.е.
, тоI= log 2 (2)=1 бит. Другими словами, получение 1 бита информации исключает из рассмотрения половину равнозначных вариантов.

Рассмотрим в качестве примера опыт с колодой из 36 карт.

Рис. 12. Иллюстрация к опыту с колодой из 36-ти карт.

Пусть некто вынимает одну карту из колоды. Нас интересует, какую именно из 36 карт он вынул. Изначальная неопределенность, рассчитываемая по формуле (2), составляет H = log 2 (36)  5,17 бит . Вытянувший карту сообщает нам часть информации. Используя формулу (5), определим, какое количество информации мы получаем из этих сообщений:

Вариант A . “Это карт а красной масти ”.

I=log 2 (36/18)=log 2 (2)=1 бит (красных карт в колоде половина, неопределенность уменьшилась в 2 раза).

Вариант B . “Это карт а пиковой масти ”.

I=log 2 (36/9)=log 2 (4)=2 бита (пиковые карты составляют четверть колоды, неопределенность уменьшилась в 4 раза).

Вариант С. “Это одна из старших карт: валет, дама, король или туз”.

I=log 2 (36)–log 2 (16)=5,17-4=1,17 бита (неопределенность уменьшилась больше чем в два раза, поэтому полученное количество информации больше одного бита).

Вариант D . “Это одна карта из колоды".

I=log 2 (36/36)=log 2 (1)=0 бит (неопределенность не уменьшилась - сообщение не информативно).

Вариант D . “Это дама пик ".

I=log 2 (36/1)=log 2 (36)=5,17 бит (неопределенность полностью снята).

Априори известно, что шарик находится в одной из трех урн: А, В или С. Определите, сколько бит информации содержит сообщение о том, что он находится в урне В. Варианты: 1 бит, 1,58 бита, 2 бита, 2,25 бита.

Вероятность первого события составляет 0,5, а второго и третьего 0,25. Чему для такого распределения равна информационная энтропия. Варианты: 0,5 бита, 1 бит, 1,5 бита, 2 бита, 2,5 бита, 3 бита.

Вот список сотрудников некоторой организации:

Определите количество информации, недостающее для того, чтобы выполнить следующие просьбы:

Пожалуйста, позовите к телефону Иванову.

Меня интересует одна ваша сотрудница, она 1970 года рождения.

Какое из сообщений несет больше информации:

В результате подбрасывания монеты (орел, решка) выпала решка.

На светофоре (красный, желтый, зеленый) сейчас горит зеленый свет.

В результате подбрасывания игральной кости (1, 2, 3, 4, 5, 6) выпало 3 очка.