信息论讨论题.ppt

讨论题 设有12枚同值硬币，其中有一枚为假币，且只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现采用天平比较左右两边轻重的方法来测量（因无砝码）。为了在天平上称出哪一枚是假币，试问至少必须称多少次？ 解答：在12枚同值硬币中，哪一枚是假币，假币的重量是比真币的重量重还是轻，都是“无知”、“不确定的”。而用天平比较左右两边轻重的测量方法，每测一次，能获得一定的信息量，能消除部分不确定性，则就能确定出其中一枚假币及其重量。因此， 设“在12枚同值硬币中，某一枚为假币”这事件为 ,其出现的概率为 又设“假币的重量比真币的重量是重或轻”这事件为 ，其出现的概率为 事件 的不确定性为 事件 的不确定性为 要发现某假币并知其比真币重还是轻所需的信息量就是要消除这两个事件的不确定性。因为这两个事件是统计独立事件，所以需要获得的信息量为 而在天平上称一次能判断出三种情况：重、轻和相等，这事件为 。这三种情况是等概率的。其概率为 。 所以，天平测一次能获得的信息量（即消除的不确定性）为 则至少必须称的次数为 因此至少必须称三次 也可不用信息量的方法解答: 首先分成3分，每分4个。称任意两分。 如果两边相平就可以断定假币在另一份中，刚刚称过的为标准币。把有假币的一份标记为1，2，3，4。第二次称，取3枚标准币和1，2，3称，如果平则假币是4。那么用1枚标准币和4称可知假币轻重。如果不平，不妨设1，2，3重，则1，2，3中有重币，称1，2。如果平则3是假币，重。否则，谁重谁就是假币。轻者，同样处理。 如果第一次称两边不平，则把重的标记为1，2，3，4，轻的标记为5，6，7，8。剩下的标记为9，10，11，12。可知9，10，11，12为标准币。第二次称1，9，10，11和5，2，3，4。如果平，则说明6，7，8中有一个轻币，称6，7。如果平，则8是假币，轻。如果不平，则轻者为假。好，如果第二次不平，不妨设1，9，10，11重，则有2种可能，1重或者是5轻。第三次只要称1和标准币就可以知道了。如果1重，则1是假币。否则5是假币，轻。 那么如果第二次不平，5，2，3，4重，则可以说明2，3，4中有一个重币。那么第三次称2，3。如果平，则4是重币，否则重者为假币。 至此，在3次内称出了结果。 讨论 题中所问为找一种方法至少必须称多少次能够找出假币 经过理论推算我们肯定有一种最优的方法可以在3次内找出这枚假币。由理论知要找出这枚假币至少要得到4.585比特的信息量，而若要在三次内找到这枚假币就必须保证每次称量获得的信息量至少为1.585比特。 但是实际中有可能有的人只用一次就找到了假币，这种概率很小,当然这个人只一次就获得了很大的信息量；也有可能有人方法不当测了很多次都找不到这枚假币，所以说由理论得出的结论只是一种最优次数。 第二章 信源熵 * * * * *