Задание 4 · ЕГЭ, информатика 2027
Кодирование и декодирование
Условие Фано: ищем кратчайшее свободное кодовое слово.
Простыми словами
Телефонные номера экстренных служб устроены так, что ни один не является началом другого: набрали 112 — сразу звонок, ждать продолжения не нужно. В кодировании это называется условием Фано, и задание 4 целиком на нём построено.
Обычно даны двоичные коды нескольких букв, и нужно подобрать кратчайший код для ещё одной буквы так, чтобы сообщения по-прежнему расшифровывались однозначно.
Условие Фано
Ни одно кодовое слово не является началом другого. Тогда сообщение декодируется однозначно, читая слева направо.
Ни одно слово не является окончанием другого. Тогда сообщение однозначно читается справа налево.
Каждого из условий достаточно для однозначного декодирования. Если в задаче не сказано иначе, проверяют прямое условие.
А — 0, Б — 01, В — 10. Запись — это «А В» () или «Б А» ()? Код А является началом кода Б — условие Фано нарушено.
Двоичное дерево кодов
Коды удобно представить ветвями дерева: 0 — влево, 1 — вправо. Занятое слово закрывает всё своё поддерево и весь путь к нему. Свободное слово — узел, который не лежит на пути к занятому и не находится под занятым.
Разбор: кратчайший код для новой буквы
А — 01, Б — 000, В — 11, Г — 100. Найдите кратчайший код для Д (если их несколько — с наименьшим числовым значением).
- Длина 1: «0» — начало 01 и 000; «1» — начало 11 и 100. Не годятся.
- Длина 2: 00 — начало 000; 01 и 11 заняты; 10 — начало 100. Не годятся.
- Длина 3: 000 занят; 001 — не начало ни одного кода, и ни один код (0, 00) не является его началом. Годится.
- Ответ: 001. (Подошло бы и 101, но .)
Перебирайте слова по возрастанию длины, внутри одной длины — по возрастанию как чисел. Слово годится, если оно не начало ни одного занятого и ни одно занятое не является его началом.
Где теряют балл: проверяют только одну сторону условия («моё слово не начало чужого») и забывают вторую; при нескольких подходящих словах берут не наименьшее.
Если спрашивают наименьшую суммарную длину кодов, используйте дерево: свободные узлы ставьте как можно выше, но не на пути к занятым листьям.
Где эта тема разобрана подробно
Готовые работы по теме
Собраны заранее — одним нажатием: распечатать с ключом, раздать ученикам ссылкой или QR-кодом, поменять настройки. Номер набора постоянный: по этой ссылке всегда та же работа.
теория этой темы, 8 заданий по подтемам и ключ — файлом DOCX, который можно править под себя.
Прохождение онлайн
Имя ученика никуда не отправляется: он вводит только номер по списку, а таблицу «номер → фамилия» видите только вы.
Классы, выданные работы и результаты учеников по кодам — в журнале учителя: без регистрации, хранится только на этом компьютере.