В этой статье мы решим задачу № 4 из демонстрационного варианта ЕГЭ-2023 года по информатике. Задача № 4 встречается почти в неизменном виде, начиная с ЕГЭ-2016. До 2016 года задача была в тестовом виде, где нужно было выбрать один из четырёх вариантов. В соответствии со спецификацией ФИПИ задача относится к базовому уровню сложности и оценивается в 1 балл, рекомендуемое время на решение этой задачи составляет 2 минуты. В конце статьи будет ссылка на тест на портале Эрудит.Онлайн. В этом тесте вы сможете потренироваться в решении задач такого типа. Обращайте внимание не только на правильность решения, но и на затраченное время.
Демонстрационный вариант ЕГЭ-2023 по информатике
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение
Вспомним на примере, какой код не удовлетворяет прямому условию Фано. Пусть А закодировано последовательностью 1011, Б закодировано последовательностью 101, тогда кодовое слово буквы Б является началом кодового слова буквы А, что приводит к неоднозначному декодированию.
По условию, кодовые слова известны для двух букв: Н – 1111, З – 110. Необходимо найти кодовые слова для букв А, К, Ч.
Обратим внимание, что в слове КАЗАЧКА, буква А повторяется 3 раза, а значит, чтобы слово было закодировано минимально возможным количеством двоичных знаков, для неё нужно взять кодовое слово наименьшей длины из возможных. А также буква К в слове повторяется 2 раза, следовательно, для неё постараемся выбрать длину меньше, чем для буквы Ч (так как она встречается всего 1 раз).
Чтобы не перебирать все возможные варианты кодовых слов и не проверять их на соответствие с прямым условием Фано, построим бинарное дерево и отметим на нём буквы Н, З.
Видим, что ветка 0 пуста (то есть никакая буква в данный момент не имеет кодового слова, начинающегося на 0). И самым кротким кодовым словом сейчас будет являться 0, сопоставим его с А.
Нижние ветви пропадают, так как больше никакая буква не может начинаться с 0, чтобы выполнялось условие Фано.
Следующее свободное слово минимальной длины – 10. Сопоставим его букве К и получим:
Единственный минимальный код для буквы Ч будет образовываться по ветке 1110. Таким образом, кодовое дерево имеет вид:
Подведем итог, кодовые слова для используемого алфавита: А – 0, К – 10, З – 110, Ч – 1110, Н – 1111.
Тогда слово КАЗАЧКА будет зашифровано последовательностью 10 0 110 0 1110 10 0.
Посчитав количество двоичных знаков, получаем ответ – 14.
В другой нашей статье можно посмотреть еще примеры решения аналогичных задач из ЕГЭ предыдущих лет:
Потренироваться в решении задач такого типа можно в тесте на портале Эрудит.Онлайн «ЕГЭ-2023 Задача № 4».
Разборы других задач: