Теория информации — страница 3

  • Просмотров 2359
  • Скачиваний 229
  • Размер файла 28
    Кб

требуется определить, в каком городе он находится, или в каком городе живёт его собеседник (жители А могут заходить в Б и наоборот), или то и другое вместе. Спрашивается, каково наименьшее число вопросов, которые должен задать Н. (на все вопросы встречные отвечают лишь да или нет)?   Пусть Н. надо определить, в каком городе он находится. Здесь опыт А может иметь 2 равновероятных исхода. Энтропия Н(А) опыта А равна одному биту. Далее,

опыт Б в составе одного вопроса, также может иметь два исхода, поэтому энтропия Н(Б) самое большее равна одному биту. Следовательно, можно надеяться, что при удачно поставленном вопросе Б будет иметь место равенство I(Б,А) = Н(А) Для этого только необходимо, чтобы оба ответа на вопрос Б были равновероятны, и исход Б полностью определял результат А. Всем этим условиям удовлетворяет вопрос «Живёте ли вы в этом городе?» (положительный

ответ может быть дан только в городе А, а отрицательный – в Б). Ещё проще узнать, в каком городе живёт его собеседник – для этого достаточно задать какой-нибудь вопрос, ответ на который Н. знает заранее (например, равно ли дважды два четырём?). Если же Н. должен узнать ответы на оба вопроса, ему предстоит определить исход сложного опыта А1А2. В этом случае он нуждается в информации, большей 1 бита. Таким образом, оценки количества

информации дают нам строгое доказательство того, что за один вопрос выяснить, где находится Н. и откуда родом отвечающий. Для этого нужно как минимум 2 вопроса.    Сколько вопросов надо задать, чтобы отгадать задуманное число, не превосходящее 10, если спрашиваемый отвечает на вопросы лишь «да» и «нет»? Опыт А, состоящий в выяснении задуманного числа, может иметь 10 различных исходов. До ответа на первый вопрос все эти исходы

можно считать равновероятными, так что энтропия Н(А) опыта А равна log 103,32 бита. Рассмотрим сложный опыт Бк = б1б2б3…бк, заключающийся в том, что спрашивающий задаёт к вопросов. Для того чтобы исход опыта Бк полностью определял исход А, необходимо, чтобы имело место равенство I (Бк, А) = Н (А). Отсюда: log 10 = Н (А) = I (Бк, А)Н (Бк)к то есть кlog 103,32 или, так как к - целое число, к4. Теперь рассмотрим, какие вопросы выгоднее всего задавать. Во-первых,

нужно, чтобы энтропия была возможно большей (то есть действительно равнялась одному биту), а значит оба варианта ответа должны быть равновероятны. Далее нужно, чтобы информация I(б1, А) относительно А, заключённая в б1, равнялась энтропии Н (б1) опыта б1, а не была бы меньше этой величины. Для этого надо, чтобы ответ на первый вопрос не содержал «посторонней» информации, то есть чтобы условная энтропия На (б1) равнялась нулю. Эти условия