Константин Кноп, Konstantin@Knop.com
Опубликовано:
10.2.1997
- Скажите, какая разница между разведчиком и
шпионом?
- Если это "свой", то разведчик, а если "чужой" - то
шпион!
"Командир разведывательного взвода и восемь его разведчиков десантировались на вражеский остров. Им нужно обнаружить на этом острове секретный вражеский объект. Ровно через два часа они должны вновь собраться на месте высадки и ждать самолета. Командиру точно известно, что объект находится в часе ходьбы по одной из четырех дорог, которые сходятся в точке приземления разведчиков. Но по какой именно дороге? Командир принимает решение: разделить разведчиков на четыре группы по два человека и отправить по всем дорогам, дав каждой группе час на путь "туда" и час на возвращение. Но тут вмешиваются вражеские шпионы..."
Неплохой сценарий для шпионского фильма? А на самом деле это одна из красивейших задач теории информации. Какое отношение имеет теория информации к вражеским шпионам? Не торопитесь, дослушайте до конца.
"...Командир знает, что двое человек из его разведгруппы - вражеские шпионы (вот только не знает, кто). Они, конечно, не посмеют ослушаться приказа, но почти наверняка попытаются не выдать секретный объект. Проще говоря - будут врать. А значит, посылать людей по двое совершенно бессмысленно: если случайно окажется, что в одну пару попали оба шпиона, то возможен вариант, когда все группы вернутся с совершенно одинаковым донесением "объект не обнаружен". Кто при этом соврал - не известно. Задание провалено, а Центр за это по головке не погладит. И даже если шпионы окажутся в разных группах, беды все равно не избежать: в обеих группах один разведчик будет утверждать, что видел объект, а другой - что ничего не видел. И все четверо будут обвинять своих напарников в шпионаже. Поди разберись!..."
Командир задумался (впрочем, тут я завираюсь - все размышления остались позади, а правильное решение было найдено им еще по пути на остров). Итак...
"...По одной дороге командир отправился сам. По двум другим направил группы из трех разведчиков. По последней дороге разведчики пошли вдвоем.
Прошло два часа. Все вернулись обратно, быстро погрузились в прилетевший самолет и улетели. Уже в самолете командир опросил всех. К его удивлению, никакого вранья не было: одна группа разведчиков дружно сообщила, что объект найден, а остальные так же дружно подтвердили, что ничего не видели. Подумав, командир догадался, что его шпионы тоже не лыком шиты: как только они сообразили, что командир все равно сможет узнать правду, тут же решили не "засвечиваться".
Как же командир собирался обнаружить обман? И, самое главное, как можно в случае обмана определить настоящее местонахождение объекта?
Рассуждать можно примерно так (ограничимся только теми случаями, когда сам командир объекта не увидит. Сообщения группы разведчиков, естественно, делятся на противоречивые и непротиворечивые):
Какое же отношение имеет эта красивая логическая задача к теории информации? Оказывается, самое прямое. Именно теория информации занимается исследованием вопросов об исправлении ошибок при передаче сигналов. Будем считать, что каждое сообщение о наличии объекта на дороге закодировано единичным битом, а каждое сообщение о его отсутствии - нулевым. Таким образом, командир получает от разведчиков восемь бит информации. Если бы вранья не было вовсе, то командир бы получил один из трех вариантов:
А так как возможны "искажения передачи информации вследствие диффамации" (то есть вранья), то ему вполне могут сообщить что-нибудь типа:
и нужно разобраться, какой из трех вариантов имеет место на самом деле.
Это и есть типичная задача теории информации: передается любое
сообщение из некоторого набора "кодовых слов", но при этом в словах возможны
искажения (обычно, как и в данном случае, искажения возникают из-за помех в
работе канала связи). Каждое искажение означает изменение одного двоичного
разряда.
Расстоянием Хемминга между двумя словами называется количество
несовпадающих в них разрядов. Очевидно, что изменив произвольным образом два
разряда, мы окажемся от исходного кодового слова на расстоянии 2. А поскольку
наши три кодовых слова находятся друг от друга на расстоянии не меньше пяти
(точнее, 5 или 6), то "расшифровка" искаженного сообщения чрезвычайно проста:
нужно определить ближайшее к нему кодовое слово. Таким образом, решение
укладывается в одну короткую инструкцию: сравнить полученное сообщение со всеми
тремя правильными и выбрать ближайшее (в смысле расстояния Хемминга).
Это же рассуждение лежит в основе доказательства одной из самых общих теорем теории информации:
"Если расстояние между любыми двумя кодовыми словами равно 2n+1, то такой код позволяет исправить любые n ошибок".
В заключение предложу еще две вариации на ту же тему:
Телефон редакции: (095) 232-2263
E-mail редакции: site@computerra.ru
По вопросам
размещения рекламы обращаться к Алене Шагиной или Ирине Лашковой по телефону +7
(095) 232-2263 или электронной почте reclama@computerra.ru