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

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

монеты после завершения первого опыта. Обозначим через а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 вариантов второго опыта. Энтропия каждого из них достаточна, чтобы иметь возможность полностью определить исход А с помощью ещё одного, третьёго, взвешивания. Значит, действительно трёх взвешиваний достаточно, чтобы ответить на поставленный в задаче вопрос. Я думаю, излишне говорить о том, что теория информации имеет огромное значение для развития