Щепин Е.В. Теория информации и распознавание образов
Подождите немного. Документ загружается.
заключению, что все монеты настоящие. Таким образом модифицированный
алгоритм также решает задачу для 13 монет.
Модифицированный алгоритм имеет заключительный узел после двух
взвешиваний. Следовательно, z
2
≥ 1 и согласно теореме 4.1 получаем,
что 9z
1
+ 3z
2
+ z
3
= 27. А с другой стороны количество заключений
z
1
+ z
2
+ z
3
должно быть больше либо равно 2 · 13 + 1 = 27. В таком
случае 8z
1
+ 2z
2
≤ 0, что невозможно при положительном z
2
.
¤
Задачи.
(1) Карточный фокус: трижды указывается одна из трех частей
колоды, где находится загаданная карта. Каково наибольшее
число карт в колоде, чтобы можно было "честно"определить
загаданную карту.
(2) Сколько бит нужно дополнительно передать, чтобы обнаружить
наличие одной-двух ошибок.
(3) Сколько битов информации дополнительно надо передать, чтобы
можно было обнаружить и исправить две ошибки в последовательности
из n бит.
(4) Придумайте код исправляющий две ошибки для передачи 9 бит
полезной информации.
(5) Насколько арифметическая контрольная сумма более информативна
по сравнению с логической (порязрядной)?
20