Задача А. Рогов
По каналу связи передаются сообщения, содержащие только буквы из набора: А, К, Л, М, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: А — 00, К — 101. Для четырёх оставшихся букв Л, М, О и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова МОЛОТОК, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Условие Фано и метод бинарного дерева
Условие Фано - это самое главное правило, которого нужно придерживаться при кодирования букв в кодовые слова. Оно гласит - никакое кодовое не может быть началом другого кодового слова.
Правило Фано было придумано для того, чтобы можно было однозначно декодировать сообщение.
Для нахождения кодовых слов есть простой и наглядный метод решения - метод бинарного дерева. Он заключается в том, что мы все возможные варианты кодовых слов разной длины, изображаем в виде разветвленной схемы, похожей на дерево.
Решение
Из условия задачи у нас есть буквы А, К, Л, М, О, Т. Мы знаем кодовые слова для буквы А - 00 и К - 101. А найти нам нужно минимальное количество знаков, для кодирования слова МОЛОТОК.
Для этого нам нужно найти кодовые слова для всех остальных букв. Воспользуемся методом бинарного дерева.
1.Сначала отметим те кодовые слова, которые нам известны, потому что если уже есть кодовое слово, значит там ветка прерывается, потому что иначе будет нарушено условие Фано.
2. При нахождении минимального количества знаков для кодирования слова, нужно обращать внимание на количество повторяющихся букв в слове. В нашем слове МОЛОТОК, буква О встречается три раза, а остальные по одному разу. Отсюда можно сделать вывод, что букву О нужно закодировать минимально возможным количеством двоичных знаков.
У нас буква О - 01, состоит из двух знаков. Остальные буквы состоят из трех знаков Л - 100, М - 110, Т - 111, К - 101. Это все кодовые слова букв в слове МОЛОТОК. Осталось только посчитать количество двоичных знаков.
Ответ: 18