Спирина, М.С. Дискретная математика

вопросов. Поэтому количество информации, необходимое для определения (хь х2), равно log2/V| + log27V2. Тождественность раз­ ных подходов к установлению количества информации, таким образом, математически записывается в виде свойства аддитив­ ности'. log2(JV1TV2) = log2TV, + log2?V2. 9 . Какие синонимы понятия «информация» вы знаете? Знание формулы Хартли для подсчета количества информа­ ции помогает решать различные задачи в одном из разделов тео­ рии информации — теории поиска. Задачи этого раздела анало­ гичны задачам поиска фальшивой монеты из некоторого множе­ ства, решение которых было рассмотрено в теории графов. Фаль­ шивой может оказаться любая из имеющихся 27 монет, поэтому можно воспользоваться формулой Хартли. Минимальное коли­ чество информации о фальшивой (тяжелой либо легкой) монете равно J = log227 = log233 = 31og23. С другой стороны, любое взвешивание на чашечных весах даст нам три варианта ответа: либо тяжелее правая чашечка, либо ле­ вая, либо весы уравновешены. Поэтому при одном взвешивании становится известным количество информации в log23 бит. В та­ ком случае при т взвешиваниях будут выявлены т log23 бит — максимальное количество информации. Поэтому т log23 > 31og23. Так как log23 > 1, то, разделив обе части неравенства на 31og23, имеем т > 3, т. е. для выявления фальшивой монеты необходимо не менее трех взвешиваний, что и было показано в гл. 2. о ; Зависит ли количество информации от степени точности сформули­ рованных вопросов? Откуда произошла игра «Бар-Кохба» и что означает это название? Согласно легенде Бар-Кохба («сын звезды») — предводитель восста­ ния против владычества римлян — послал в лагерь римлян разведчика, которого римляне схватили, жестоко пытали и отрезали ему язык. Сбе­ жав от врагов и вернувшись в осажденную крепость, несчастный лазут­ чик не имел возможности рассказать о том, что разведал в стане римлян. Тогда ему стали задавать лишь уточняющие вопросы, на которые можно было отвечать кивком головы — положительным, в случае согласия, и отрицательным в противоположном случае. Задача 39. Найти количество информации, которое можно по­ лучить при ответе на вопрос: при бросании игрального кубика у вас выпала цифра 5? Решение. Вероятность выпадения числа 5 выпадения другой цифры р - \ - Тогда по о имеем / = - \ log24 - 4 log2 у = 0,65 бита, о о о о на кубике р = \ , а о формуле Шеннона 308