Буквы кодируют цепочками из нулей и единиц так, чтобы ни одна цепочка не была началом другой — это условие Фано, благодаря ему сообщение читается однозначно. Для части букв коды известны; нужно подобрать остальным самые короткие коды и найти длину кода или всего слова. Базовый уровень, ответ — число, 1 балл.
Ответ
число в поле ответа
Баллы
1 балл
Проверяет
умение кодировать и декодировать сообщения двоичным кодом, который читается однозначно
Сколько времени закладывать
около 2 минут по спецификации ФИПИ
Какие бывают подтипы
Кратчайший код для новой буквы — Подобрать самый короткий код, который не начинается ни с одного известного кода и сам не служит началом ни одного из них.
Длина закодированного слова — Коды двух букв неизвестны: распределить короткие коды так, чтобы всё слово заняло как можно меньше двоичных знаков.
Пример с полным разбором
Условие. Сообщения из букв А, К, Л, М, П передают двоичным кодом, который удовлетворяет условию Фано. Известны коды трёх букв: Л — 00, П — 01, К — 110. Коды букв А и М подбирают так, чтобы слово ЛАМПА заняло как можно меньше двоичных знаков. Сколько двоичных знаков займёт это слово?
Коды 0 и 1 уже не годятся: 0 — начало кода 00, а 1 — начало кода 110.
Из кодов длины 2 свободен только 10: коды 00 и 01 заняты, а 11 — начало кода 110.
Буква, которая получит 10, закроет все коды, начинающиеся с 10. Второй букве остаётся самый короткий из свободных — 111.
В слове ЛАМПА буква А встречается дважды, а М — один раз, поэтому короткий код отдаём А: А — 10, М — 111.
Длина слова: Л (2) + А (2) + М (3) + П (2) + А (2) = 11. Если поменять коды А и М местами, выйдет 12.
Ответ: 11
Частые ошибки
Проверяют только, что коды разные, а не то, что ни один не служит началом другого.
Отдают короткий код букве, которая встречается в слове реже.
Подбирают коды двух букв по очереди и не замечают, что первый выбор испортил лучший вариант для второй.
Отвечают длиной кода одной буквы, когда спрашивали длину всего слова, или наоборот.
Что нужно знать для задания 4
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.
Требование к коду: никакое кодовое слово не является началом другого. Тогда сообщение из нулей и единиц расшифровывается однозначно. Определение приводят прямо в условии задания.
Нужен ли компьютер для задания 4?
Нет, по спецификации специальные программы здесь не нужны: коды подбирают на черновике. Спецификация отводит на задание около 2 минут — меньше, чем на любое другое.