Задание 4 ЕГЭ по информатике 2027

Что проверяет задание 4

Буквы кодируют цепочками из нулей и единиц так, чтобы ни одна цепочка не была началом другой — это условие Фано, благодаря ему сообщение читается однозначно. Для части букв коды известны; нужно подобрать остальным самые короткие коды и найти длину кода или всего слова. Базовый уровень, ответ — число, 1 балл.

Ответчисло в поле ответа
Баллы1 балл
Проверяетумение кодировать и декодировать сообщения двоичным кодом, который читается однозначно
Сколько времени закладыватьоколо 2 минут по спецификации ФИПИ

Какие бывают подтипы

Пример с полным разбором

Условие. Сообщения из букв А, К, Л, М, П передают двоичным кодом, который удовлетворяет условию Фано. Известны коды трёх букв: Л — 00, П — 01, К — 110. Коды букв А и М подбирают так, чтобы слово ЛАМПА заняло как можно меньше двоичных знаков. Сколько двоичных знаков займёт это слово?

  1. Коды 0 и 1 уже не годятся: 0 — начало кода 00, а 1 — начало кода 110.
  2. Из кодов длины 2 свободен только 10: коды 00 и 01 заняты, а 11 — начало кода 110.
  3. Буква, которая получит 10, закроет все коды, начинающиеся с 10. Второй букве остаётся самый короткий из свободных — 111.
  4. В слове ЛАМПА буква А встречается дважды, а М — один раз, поэтому короткий код отдаём А: А — 10, М — 111.
  5. Длина слова: Л (2) + А (2) + М (3) + П (2) + А (2) = 11. Если поменять коды А и М местами, выйдет 12.

Ответ: 11

Ещё задания с решением

Кратчайший код для новой буквы

Условие.

Для букв Б, Г, Л используются кодовые слова 000, 11, 100. Для буквы Д нужно выбрать кодовое слово наименьшей длины, при котором код по-прежнему удовлетворяет условию Фано (ни одно кодовое слово не является началом другого). Какова длина такого слова?

Решение.

Кратчайшее свободное слово: 01. Все слова длины 1 и короче конфликтуют с выданными кодами: каждое либо начинается с одного из них, либо само служит началом одного из них.

Проверка: 01 не начинается ни с одного из кодов 000, 11, 100, и ни один из них не начинается с 01.

Ответ: 2

Длина закодированного слова

Условие.

Сообщения из букв А, В, Н, О, Р передают двоичным кодом, для которого выполнено условие Фано (ни одно кодовое слово не является началом другого). Коды трёх букв уже выбраны:

БукваКод
В10
Н01
Р110

Коды букв А и О можно выбрать любыми, лишь бы условие Фано не нарушилось. Какое наименьшее количество двоичных знаков может занять закодированное слово «ВОРОНА»?

Решение.

Столько раз каждая буква входит в слово «ВОРОНА».

Лучшая пара свободных слов: более короткое достаётся букве О — она встречается чаще.

Длины кодов по буквам слова.

Ответ: 14

Кратчайший код для новой буквы

Условие.

Для букв Б, Г, Д используются кодовые слова 1, 00, 011. Для буквы А нужно выбрать кодовое слово наименьшей длины, при котором код по-прежнему удовлетворяет условию Фано (ни одно кодовое слово не является началом другого). Какова длина такого слова?

Решение.

Кратчайшее свободное слово: 010. Все слова длины 2 и короче конфликтуют с выданными кодами: каждое либо начинается с одного из них, либо само служит началом одного из них.

Проверка: 010 не начинается ни с одного из кодов 1, 00, 011, и ни один из них не начинается с 010.

Ответ: 3

Частые ошибки

Что нужно знать для задания 4

Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.

  1. Код, кодовое слово и префикс
  2. Условие Фано: почему код читается однозначно
  3. Задание 4: что дают и что писать в бланк
  4. Рабочий приём: перебор кандидатов
  5. Две буквы сразу: жадность заводит в тупик
  6. Разбор: задача уровня экзамена
  7. Разбор: задача в форме демоварианта 2027 года

Открыть темы в курсе

Ответы на частые вопросы

Сколько баллов за задание 4?
Один, если число полностью совпало с верным.
Что такое условие Фано?
Требование к коду: никакое кодовое слово не является началом другого. Тогда сообщение из нулей и единиц расшифровывается однозначно. Определение приводят прямо в условии задания.
Нужен ли компьютер для задания 4?
Нет, по спецификации специальные программы здесь не нужны: коды подбирают на черновике. Спецификация отводит на задание около 2 минут — меньше, чем на любое другое.