Теория информации (стр. 2 из 2)
Вообще, наименьшее число k вопросов, позволяющее найти заданное число Х, имеющее одно из n допустимых значений, определяется неравенствами
k – 1< logn ≤ k или 2k - 1 < n ≤ 2k.
Также можно заметить, что независимо от значения n
k ≥ logn;
при этом k = logn только в том случае, когда число n является целой степенью числа 2.
Имеется 25 монет одного достоинства; 24 из них имеют одинаковый вес, а одна – фальшивая – несколько легче остальных. Спрашивается, сколькими взвешиваниями на чашечных весах без гирь можно обнаружить эту фальшивую монету. 
Опыт А, результат которого требуется определить, имеет в этом случае 25 возможных исходов, значит, так как эти исходы равновероятны, Н(Б) = log 25. Опыт б1, состоящий в одном взвешивании, может иметь 3 исхода (либо перевесит левая чашка, либо правая, либо веса останутся в равновесии); поэтому Н (б1) = log 3 и информация I(б1, А), получаемая при проведении такого опыта, не превосходит log 3. Рассмотрим теперь сложный опыт Бк = б1б2…бк, заключающийся в k последовательных взвешиваниях; он даёт информацию, не превосходящую klog 3. Если опыт Бк позволяет полностью определить исход опыта А, то должно выполняться
Н (Бк) ≥ I (Бк, А) ≥ Н (А) или klog 3 ≥ log 25.
Отсюда заключаем, что 3к ≥ 25, то есть
K ≥ log3 25 =
Или, так как k – целое число, k ≥ 3.
Нетрудно показать, что с помощью трёх взвешиваний всегда можно определить фальшивую монету. Предположим, что на каждую чашку весов нами положено по n монет, не положены на весы будут 25 - 2n монет. Так как вероятность того, что фальшивая монета окажется в данной группе из n монет, равна
, то три исхода опыта б1 будут иметь наиболее близкие вероятности, если n = 8 и 25 - 2n = 9. При любом исходе опыта при втором взвешивании (опыт б2) на обе чашки весов следует положить по 3 монеты из определившейся после предыдущего опыта группы, а третьим взвешиванием мы из группы из трёх монет найдём фальшивую, положив по одной монете на обе чашки весов. Имеется 12 монет одного достоинства; 11 из них имеют одинаковый вес, а одна – фальшивая – отличается по весу от остальных (причём неизвестно, легче она или тяжелее настоящих). Каково наименьшее число взвешиваний на чашечных весах без гирь, которое позволяет обнаружить фальшивую монету и выяснить, легче она, чем остальные монеты, или тяжелее? Здесь рассматривается опыт А, имеющий 24 возможных равновероятных исхода. Энтропия Н (А) опыта А равна log 24. Таким образом, нам нужно получить log 24 единиц информации. Так как, произведя сложный опыт Ак = а1а2…ак, состоящий в k взвешиваниях, мы можем получить информацию, не большую, чем klog 3 = log 3, а 33 = 27, то с первого взгляда кажется ясным, что трёх взвешиваний будет достаточно.
Пусть при первом взвешивании мы положили на обе чашки по n монет. Если чашки весов при этом остались в равновесии, то фальшивой является одна из 12−2n отложенных монет, что отвечает 2(12−2n) исходам рассматриваемого опыта А (из общего числа 24 исходов). Если перевесила правая чашка, то либо фальшивой и более тяжёлой является одна из n «правых» монет, либо фальшивой и более лёгкой является одна из n «левых» монет − эти случаи отвечают 2n исходам А, точно так же, случаю, когда перевесила левая чашка, отвечают 2n исходов А. Таким образом, три исхода первого взвешивания имеют вероятности
, 
и 
.Отсюда сразу следует, что наибольшую энтропию опыт будет иметь при n = 4, три исхода которого равновероятны. Далее рассмотрим отдельно 2 случая.
1). При первом взвешивании чашки весов остались в равновесии. В таком случае фальшивой является одна из четырёх отложенных монет. Нам надо при помощи двух взвешиваний определить, какая именно из них является фальшивой, и выяснить, легче она или тяжелее остальных; так как у нас осталось 2∙4 = 8 возможных исходов опыта А, а 2 log 3 = log 9 > log 8, то можно ожидать, что это возможно. Если, однако, положить на каждую чашку весов по одной монете, и они останутся в равновесии, то следующим опытом нам надо будет определить исход опыта, имеющего 4 возможных исхода, что невозможно. То же самое получится, если положить на каждую чашку по две монеты. Однако рано говорить, что трёх взвешиваний недостаточно для выполнения задачи – ведь у нас ещё остались заведомо настоящие монеты после завершения первого опыта. Обозначим через аm,nопыт, состоящий в том, что на правую чашку весов кладутся m из наших подозрительных монет, а на левую n ≤ m из этих монет и ещё m−n заведомо настоящих монет. Через р(Р), р(П) и р(Л) мы обозначим соответственно вероятности того, что при опыте аm,nчашки весов останутся в равновесии и что перетянет правая или левая чашка весов. Так как, очевидно, m + n ≤ 4, то все опыты аm,nлегко перечислить: отвечающие им значения вероятностей р(Р), р(П) и р(Л) собраны в таблице, в которой также указана энтропия в битах Н(аm,n) опыта аm,n(равная − р(Р) log р(Р) − р(П) log р(П) − р(Л) log р(Л)).
| m | n | р(Р) | р(П) | р(Л) | Н(аm,n) |
| 1 | 1 | 0,5 | 0,25 | 0,25 | 1,50 |
| 1 | 0 | 0,75 | 0,125 | 0,125 | 1,06 |
| 2 | 2 | 0 | 0,5 | 0,5 | 1,00 |
| 2 | 1 | 0,25 | 0,375 | 0,375 | 1,56 |
| 2 | 0 | 0,5 | 0,25 | 0,25 | 1,50 |
| 3 | 1 | 0 | 0,5 | 0,5 | 1,00 |
| 3 | 0 | 0,25 | 0,375 | 0,375 | 1,56 |
| 4 | 0 | 0 | 0,5 | 0,5 | 1,00 |
Из этой таблицы видно, что наибольшую энтропию имеют опыты а2,1 и а3,0; поэтому для получения наибольшей информации следует воспользоваться ими. Нетрудно видеть, что в обоих случаях мы можем затем третьим взвешиванием полностью определить исход А.
2). При первом взвешивании одна из двух чашек весов (например, правая) перетянула. В таком случае, либо одна из четырёх «правых» монет является фальшивой и более тяжёлой, либо одна из четырёх «левых» − фальшивой и более лёгкой. При втором взвешивании мы можем на правую чашку весов положить n1 «правых» монет и n2 «левых», а на левую чашку − m1 «правых» монет, m2 «левых» и (n1 + n2) − (m1 + m2) заведомо настоящих из числа не участвовавших в первом взвешивании. Здесь тоже можно составить таблицу энтропий опытов аn1,n2;m1,m2 , однако, так как число всевозможных вариантов тут слишком велико, то некоторые из них целесообразно исключить с самого начала.
Заметим, что после двух взвешиваний у нас должно остаться не более трёх возможных исходов опыта А. Отсюда следует, что число сомнительных монет, не участвующих во втором взвешивании, не должно превосходить 3.
Перечислим теперь все случаи, удовлетворяющие этим условиям.
| n1 | n2 | m1 | m2 | р(Р) | р(П) | р(Л) | Н(аn1,n2;m1,m2) |
| 2 | 1 | 2 | 1 | 0,25 | 0,375 | 0,375 | 1,56 |
| 2 | 1 | 2 | 0 | 0,375 | 0,25 | 0,375 | 1,56 |
| 2 | 1 | 1 | 1 | 0,375 | 0,375 | 0,25 | 1,56 |
| 1 | 2 | 1 | 2 | 0,25 | 0,375 | 0,375 | 1,56 |
| 1 | 2 | 0 | 2 | 0,375 | 0,375 | 0,25 | 1,56 |
| 1 | 2 | 1 | 1 | 0,375 | 0,25 | 0,375 | 1,56 |
| 3 | 1 | 1 | 0 | 0,375 | 0,375 | 0,25 | 1,56 |
| 1 | 3 | 0 | 1 | 0,375 | 0,25 | 0,375 | 1,56 |
| 2 | 2 | 1 | 1 | 0,25 | 0,375 | 0,375 | 1,56 |
| 2 | 2 | 1 | 0 | 0,375 | 0,25 | 0,375 | 1,56 |
| 2 | 2 | 0 | 1 | 0,375 | 0,375 | 0,25 | 1,56 |
| 3 | 2 | 1 | 0 | 0,25 | 0,375 | 0,375 | 1,56 |
| 2 | 3 | 0 | 1 | 0,25 | 0,375 | 0,375 | 1,56 |
Таким образом, мы видим, что здесь имеется уже не два, как в предыдущем случае, а целых 13 вариантов второго опыта. Энтропия каждого из них достаточна, чтобы иметь возможность полностью определить исход А с помощью ещё одного, третьёго, взвешивания.
Значит, действительно трёх взвешиваний достаточно, чтобы ответить на поставленный в задаче вопрос.
Я думаю, излишне говорить о том, что теория информации имеет огромное значение для развития современной науки и техники. Она получила широкое применение в физике, микроэлектронике, а также во всех отраслях техники, где необходимо решать проблемы хранения, получения и передачи информации.
Список использованной литературы.
1) А. Реньи. «Записки студента теории информации».
2) А.М. Яглом, И.М. Яглом. «Вероятность и информация».