Задание 4 ЕГЭ по информатике: условие Фано и кодирование
Задание 4 ЕГЭ по информатике (КЕГЭ) проверяет умение работать с кодированием и декодированием информации: чаще всего — достроить неравномерный двоичный код так, чтобы он допускал однозначную расшифровку, то есть удовлетворял условию Фано. Это задание базового уровня, за него дают 1 первичный балл, файл к нему не прилагается, а проверяемый элемент содержания — 2.1 «Кодирование и декодирование информации». Ответ — число или короткое кодовое слово, состоящее из нулей и единиц. В статье — условие Фано и обратное условие Фано, неравенство Крафта как быстрый счётчик свободных мест, приём «дерево кодов» с рабочим Python-кодом для перебора кандидатов, разбор всех трёх типов задач линии и три реальных задания из открытого банка ФИПИ. Тренироваться можно на реальных заданиях 4 КЕГЭ онлайн — с мгновенной проверкой ответа.
Что проверяет задание 4 ЕГЭ по информатике
Раздел кодификатора — «Теоретические основы информатики», проверяемый элемент содержания 2.1 «Кодирование и декодирование информации». Задание не требует компьютера содержательно (специализированное ПО для него не нужно), хотя формально весь экзамен сдаётся за компьютером. По сути это задача на комбинаторику двоичных строк: дан частично заполненный код, нужно понять, какие кодовые слова ещё свободны и как выбрать среди них нужное.
Проверяемые умения (КЭС 2.1):
- понимать, что такое неравномерный двоичный код и чем он отличается от равномерного (все слова которого имеют одну длину);
- проверять условие Фано — «никакое кодовое слово не является началом другого» — и обратное условие Фано — «никакое кодовое слово не является окончанием другого»;
- находить кратчайшее свободное кодовое слово для новой буквы, не нарушающее условие Фано;
- декодировать сообщение по известным кодовым словам и считать суммарную длину закодированного текста;
- находить наименьшую возможную суммарную длину кодовых слов для нескольких ещё не закодированных букв.
Все цифры ниже приведены по действующей спецификации ФИПИ 2026 года. Проекты КИМ-2027 ФИПИ публикует в конце августа 2026 года, финальные версии — в ноябре; структура работы не менялась с 2025 года.
| Параметр | Значение |
|---|---|
| Максимальный балл | 1 первичный (промежуточных оценок нет: ответ либо совпал с эталоном, либо 0) |
| Уровень сложности | Базовый — одно из 11 заданий базового уровня во всей работе |
| Проверяемый элемент содержания | КЭС 2.1 «Кодирование и декодирование информации», раздел «Теоретические основы информатики» |
| Формат ответа | Число (в том числе двоичное кодовое слово, записанное как последовательность цифр 0 и 1, без пробелов) |
| Нужен ли файл | Нет, задание самодостаточно по условию |
| Специализированное ПО | Не требуется |
| Время | 2 минуты — примерное время выполнения задания по обобщённому плану варианта КИМ ЕГЭ (спецификация ФИПИ) |
| Связанные задания | Задание 8 (КЭС 2.2, измерение количества информации), задание 11 (КЭС 2.2, информационный объём сообщения) — тоже про кодирование, но без условия Фано |
Тренируйтесь на реальных заданиях
Задания КЕГЭ по информатике из открытого банка ФИПИ с мгновенной проверкой ответа. Решаем, ошибаемся, разбираем — бесплатно.
Как выглядит формулировка
Формулировка задания 4 варьируется по трём сценариям, но общий каркас один и тот же: набор букв, часть кодовых слов уже известна, и нужно либо достроить код, либо декодировать по нему сообщение. Вот реальные формулировки из открытого банка ФИПИ:
Тип 1 — найти кратчайшее свободное кодовое слово для буквы:
- «Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 00, 01, 100, 110. Для двух оставшихся букв – П и Р – кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код допускает однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.»
Тип 2 — декодировать сообщение и посчитать суммарную длину:
- «По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. […] Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?»
Тип 3 — минимальная суммарная длина кодовых слов:
- «По каналу связи передаются шифрованные сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е, Ж. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 00, 01, 100, 111 соответственно. Укажите минимальную сумму длин кодовых слов для букв Д, Е и Ж, при которой код будет удовлетворять условию Фано.»
Как записывается ответ. Ответ на задание 4 — это число. Если ищете кодовое слово (тип 1), число выглядит как последовательность нулей и единиц без пробелов и разделителей (например, «101») — она вводится как обычное число, а не как отдельные биты. Если ищете суммарную длину (типы 2 и 3), ответ — обычное натуральное число (например, «14»). В обоих случаях никаких единиц измерения, слов «бит» или «знаков» писать не нужно.
Теория: всё, что нужно для задания 4
Условие Фано и обратное условие Фано
Когда буквы кодируют словами разной длины (неравномерный двоичный код), сообщение записывается без пробелов между буквами — это сплошная строка нулей и единиц. Чтобы получатель мог однозначно разбить эту строку обратно на буквы, код должен быть префиксным.
Условие Фано (прямое):
никакое кодовое слово не является началом (префиксом) другого кодового слова. Если бы слово буквы А было, например, «10», а слово буквы Б — «101», то при чтении строки «101…» невозможно понять, кончилась буква А (и дальше начинается что-то новое на «1…») или это ещё не дочитанная буква Б.
Обратное условие Фано:
никакое кодовое слово не является окончанием (суффиксом) другого кодового слова. Оно защищает от неоднозначности при чтении строки справа налево и на практике проверяется зеркально: разворачиваете все слова задом наперёд и применяете обычное условие Фано к развёрнутым словам.
В задании 4 в подавляющем большинстве вариантов ФИПИ прямо пишет «удовлетворяющий условию Фано» или «согласно которому никакое кодовое слово не является началом другого» — это прямое условие, и весь дальнейший разбор в статье про него.
Важная тонкость. Условие Фано достаточно для однозначного декодирования, но не необходимо. Существуют непрефиксные коды, которые тем не менее декодируются однозначно (например, за счёт особого расположения нулей и единиц). Но в задании 4 ФИПИ явно требует выполнения именно условия Фано — искать более экзотические непрефиксные однозначные коды не нужно и вредно: это не то, что спрашивает задание.
Геометрически условие Фано означает: если представить все возможные двоичные строки как узлы бесконечного двоичного дерева (корень — пустая строка, каждый узел имеет двух потомков — «дописать 0» и «дописать 1»), то кодовые слова — это узлы, из которых нельзя пройти ни вверх (к предку), ни вниз (к потомку) и попасть в другое кодовое слово. Каждое занятое слово «выжигает» весь путь от корня до себя и всё поддерево под собой.
Неравенство Крафта — быстрый счётчик
Прежде чем перебирать вершины дерева руками, полезно быстро прикинуть, сколько «места» в коде вообще осталось. Для этого служит неравенство Крафта: если код с длинами слов удовлетворяет условию Фано, то
Смысл простой: слово длины «съедает» долю от всего дерева (это доля двоичных строк, которые начинаются с этого слова). Слова, удовлетворяющие условию Фано, никогда не пересекаются — значит, их доли можно просто сложить, и сумма не может превысить «единицу» (весь код целиком).
Как использовать на экзамене. Посчитайте сумму для уже известных слов — получите «занятый бюджет». Остаток — это свободный бюджет, который можно распределить между новыми словами.
Пример (реальное задание банка, id 44983): известны А — 00, Б — 01, В — 100, Г — 111. Бюджет:
Свободно . Нужны ещё три слова (для Д, Е, Ж). Проверим быстро: можно ли обойтись тремя словами длины 3? Тогда сумма была бы — это больше свободного бюджета 0,25, значит трёх слов длины 3 не хватит, не перебирая вообще ничего вручную. Придётся сделать хотя бы одно слово длиной 4. Набор длин 3, 4, 4 даёт — ровно весь остаток, и это действительно минимально возможная сумма длин: 3 + 4 + 4 = 11. Полный разбор этого задания — в примере 3 ниже.
Неравенство Крафта не заменяет построение дерева (оно не говорит, какие именно слова свободны), но за секунды отсекает заведомо невозможные комбинации длин — это экономит время именно там, где на экзамене его меньше всего.
Приём «дерево кодов» и Python-перебор кандидатов
Представьте все возможные двоичные строки как узлы полного двоичного дерева: корень — пустая строка, у узла два потомка — и . Каждое уже занятое кодовое слово отсекает целую ветвь дерева сразу в двух направлениях:
- все его предки (более короткие префиксы) становится нельзя занять другим словом — иначе занятое слово окажется продолжением нового, что запрещено условием Фано;
- всё его поддерево (более длинные продолжения) тоже нельзя занимать — иначе уже занятое слово само окажется префиксом нового.
Свободными остаются только те узлы, что не лежат ни на одном из этих двух путей ни для одного занятого слова. Отсюда сразу видно: сколько коротких слов ещё свободно (посчитать оставшиеся узлы на нужной глубине) и какой будет минимальная длина следующего свободного слова (спуститься по дереву до первого уровня, где найдётся хоть один свободный узел).
Вот рабочая реализация этого приёма на Python — она перебирает двоичные строки по возрастанию длины и проверяет условие Фано прямым сравнением с уже известными словами:
def is_prefix(a, b):
return b.startswith(a)
def is_free(word, known):
return all(
not is_prefix(k, word) and not is_prefix(word, k)
for k in known
)
def shortest_free_words(known, max_len=10):
from itertools import product
for length in range(1, max_len + 1):
candidates = [
"".join(bits)
for bits in product("01", repeat=length)
if is_free("".join(bits), known)
]
if candidates:
return length, sorted(candidates)
return None, []
known = ["00", "01", "100", "110"]
length, words = shortest_free_words(known)
print(length, words)Для примера выше (буквы К=00, Л=01, М=100, Н=110) программа печатает 3 ['101', '111'] — кратчайшая свободная длина равна 3, и таких слов ровно два, что отлично согласуется с двумя ещё не закодированными буквами (П и Р). Из них наименьшее по числовому значению — 101.
Когда нужно не одно слово, а сразу новых слов (и, возможно, часть из них придётся получить, разбивая одно свободное место на два более длинных), удобнее работать через кучу (min-heap): поддерживать список текущих свободных «слотов» дерева и каждый раз, когда слотов не хватает, разбивать самый короткий слот на двух потомков — это и есть жадный поиск минимальной суммарной длины:
import heapq
from itertools import product
def is_prefix(a, b):
return b.startswith(a)
def free_root_slots(known, max_scan_len=14):
slots = []
for length in range(1, max_scan_len + 1):
for bits in product("01", repeat=length):
w = "".join(bits)
if any(is_prefix(k, w) or is_prefix(w, k) for k in known):
continue
if any(is_prefix(s, w) for s in slots):
continue
slots.append(w)
return slots
def free_words_needed(known, n_needed):
heap = [(len(w), w) for w in free_root_slots(known)]
heapq.heapify(heap)
while len(heap) < n_needed:
length, word = heapq.heappop(heap)
heapq.heappush(heap, (length + 1, word + "0"))
heapq.heappush(heap, (length + 1, word + "1"))
chosen = heapq.nsmallest(n_needed, heap)
return sorted(w for _, w in chosen)
known = ["00", "01", "100", "111"]
words = free_words_needed(known, 3)
print(words, "сумма длин =", sum(len(w) for w in words))Эта программа печатает ['1010', '1011', '110'] сумма длин = 11 — то есть ровно тот ответ, что даёт задание про буквы Д, Е, Ж из блока про неравенство Крафта выше. Одна и та же функция free_words_needed закрывает все три типа задач линии: для типа 1 достаточно одного слова ( или 2, если букв не хватает); для типа 3 нужна сумма длин; для типа 2 (декодирование) список свободных слов, отсортированный по длине, используется как источник кандидатов для присвоения буквам — короче слово самой частой букве.
Второй тип: декодирование и суммарная длина сообщения
Второй тип задач звучит иначе: известны кодовые слова не для всех букв, а сообщение нужно закодировать минимально возможным числом двоичных знаков. Здесь работает жадный принцип, знакомый по коду Хаффмана: чем чаще буква встречается в сообщении, тем короче должно быть её кодовое слово.
Алгоритм:
- найдите все свободные кодовые слова для ещё не закодированных букв (метод «дерева кодов» выше) и отсортируйте их по возрастанию длины;
- посчитайте, сколько раз каждая ещё не закодированная буква встречается в сообщении;
- отдайте самое короткое свободное слово самой частой из этих букв, следующее по длине — следующей по частоте, и так далее;
- посчитайте суммарную длину: для каждой буквы сообщения (включая те, что были закодированы изначально) сложите длину её кодового слова, умноженную на число вхождений.
Пример (реальное задание банка, id 59116): известны Н — 1111, З — 110, нужно закодировать буквы А, К, Ч. Дерево кодов даёт три свободных слова возрастающей длины: 0 (1 знак), 10 (2 знака), 1110 (4 знака). В слове «КАЗАЧКА» буква А встречается 3 раза, К — 2 раза, а З и Ч — по одному:
from collections import Counter
known = {"Н": "1111", "З": "110"}
free = ["0", "10", "1110"]
word = "КАЗАЧКА"
counts = Counter(word)
unknown_by_freq = sorted(
[c for c in counts if c not in known],
key=lambda c: -counts[c],
)
for letter, code in zip(unknown_by_freq, free):
known[letter] = code
total = sum(len(known[c]) * n for c, n in counts.items())
print(known, total)Программа печатает суммарную длину 14: А получает 0 (3 × 1 = 3), К — 10 (2 × 2 = 4), а З (уже известное слово 110, длина 3) и Ч (получает 1110, длина 4) дают ещё 3 и 4. Итого . Полный разбор — в примере 2 ниже.
Третий тип: наименьшая суммарная длина всех кодовых слов
Здесь частоты букв не даны вообще — вопрос звучит как «укажите минимальную сумму длин кодовых слов для оставшихся букв». Задача превращается в чистую комбинаторику дерева: нужно разместить новых листьев так, чтобы сумма их глубин была минимальной.
Правило: если свободных слотов на дереве уже , берите самых коротких — ничего разбивать не нужно. Если свободных слотов меньше, чем нужно букв, разбивайте каждый раз самый короткий из имеющихся слотов на два более длинных (потому что разбить длинный слот всегда не выгоднее, чем короткий) — ровно это и делает функция free_words_needed из блока про дерево кодов выше.
Частая ловушка: на первый взгляд кажется, что если есть два свободных слова длины 3, а букв тоже три, ответ будет . Но неравенство Крафта может это запретить — как в примере с А=00, Б=01, В=100, Г=111: два свободных слова длины 3 (101 и 110) вместе с уже занятыми 00, 01, 100, 111 заполняют весь бюджет Крафта без остатка (), и тогда на третью букву просто не остаётся места — одно из двух коротких слов обязательно приходится «разбивать» на два более длинных.
Итоговое правило проверки: посчитайте неравенство Крафта для предполагаемого набора длин. Если сумма для всех слов (известных и новых) равна 1 или меньше — набор длин в принципе достижим; если он ещё и минимален по сумме — задача решена верно.
Алгоритм решения задания 4
- Определите тип задачи. «Укажите кратчайшее возможное кодовое слово» — тип 1. «Сколько знаков потребуется для кодирования слова…» — тип 2 (декодирование). «Укажите минимальную сумму длин» — тип 3.
- Выпишите известные кодовые слова. Держите их перед глазами — вся дальнейшая работа сводится к сравнению строк с этим списком.
- Найдите, с какой длины начинаются свободные слова. Идите по возрастанию длины 1, 2, 3, … и для каждой длины проверяйте, есть ли строка, которая не является ни началом, ни продолжением ни одного известного слова. Первая длина, где такая строка нашлась, — минимально возможная.
- Пересчитайте, сколько свободных слов этой длины. Если букв, которым нужен код, больше, чем свободных слов этой длины, часть букв получит слова на единицу длиннее — не пытайтесь «сэкономить» и втиснуть всех в минимальную длину, это нарушит условие Фано.
- Для типа 1 — среди свободных слов минимальной длины выберите то, что меньше как двоичное число (сравнивайте слева направо, как обычные числа).
- Для типа 2 — посчитайте частоту каждой ещё не закодированной буквы в сообщении и раздайте короткие свободные слова самым частым буквам; затем сложите произведения «длина слова × число вхождений» по всем буквам сообщения.
- Для типа 3 — если свободных слов хватает по количеству, суммируйте их длины напрямую; если не хватает, разбивайте самый короткий свободный слот на два более длинных, пока слов не станет достаточно, и суммируйте итоговые длины. Проверьте результат неравенством Крафта.
Доведите приём до автоматизма
Прорешайте 10–15 заданий на условие Фано подряд — и построение дерева кодов начнёт занимать меньше минуты. Задания КЕГЭ по информатике из банка ФИПИ с проверкой ответа — на Repet.ai.
Примеры с разбором
Пример 1. Кратчайшее кодовое слово для буквы (тип 1)
Условие (реальное задание из открытого банка ФИПИ):
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 00, 01, 100, 110. Для двух оставшихся букв – П и Р – кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код допускает однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение:
Известны слова К — 00, Л — 01, М — 100, Н — 110. Строим дерево: ветвь 0 занята целиком, потому что оба слова 00 и 01 используют все узлы этой ветви до глубины 2. В ветви 10 занято слово 100 — свободен только узел 101. В ветви 11 занято слово 110 — свободен только узел 111.
Слов длины 1 и 2 не осталось: 0 и 1 — префиксы занятых слов, 10 и 11 — тоже префиксы (100 и 110 продолжают их). Значит, кратчайшая возможная длина — 3, и на этой длине свободны ровно два узла: 101 и 111 — как раз для двух букв П и Р.
known = ["00", "01", "100", "110"]
length, words = shortest_free_words(known)
print(length, words)
# 3 ['101', '111']Из двух свободных слов длины 3 выбираем наименьшее как двоичное число: меньше .
Ответ: 101. Проверка здравым смыслом: слово 101 не совпадает по началу ни с одним из 00, 01, 100, 110, и ни одно из них не является его продолжением — условие Фано не нарушено, а второй свободный узел (111) остаётся для буквы Р.
Пример 2. Декодирование сообщения и суммарная длина (тип 2)
Условие (реальное задание из открытого банка ФИПИ):
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Решение:
Известны Н — 1111, З — 110. Оба слова начинаются с 1, значит вся ветвь 0 свободна целиком — можно взять слово 0 (1 знак). В ветви 1 свободна вершина 10 (2 знака). В ветви 11 слово 110 занято, а в ветви 111 занято 1111 — свободна вершина 1110 (4 знака). Получаем ровно три свободных слова — 0, 10, 1110 — для трёх букв А, К, Ч.
Считаем частоты в слове «КАЗАЧКА»: А — 3 раза, К — 2 раза, З — 1 раз, Ч — 1 раз. Самое короткое свободное слово отдаём самой частой букве:
known = {"Н": "1111", "З": "110"}
free = ["0", "10", "1110"]
counts = {"А": 3, "К": 2, "З": 1, "Ч": 1}
for letter, code in zip(["А", "К", "Ч"], free):
known[letter] = code
total = sum(len(known[c]) * n for c, n in counts.items())
print(total)
# 14| Буква | Слово | Длина | Раз | Знаков |
|---|---|---|---|---|
| А | 0 | 1 | 3 | 3 |
| К | 10 | 2 | 2 | 4 |
| З | 110 | 3 | 1 | 3 |
| Ч | 1110 | 4 | 1 | 4 |
Ответ: 14. Проверка: если бы вместо самой частой буквы А короткое слово 0 отдали редкой букве Ч, сумма выросла бы (Ч даёт 1 × 1 = 1, но А тогда пришлось бы дать слово длиннее, и 3 повторения умножат разницу на 3) — жадное правило «короче слово — чаще буква» здесь и даёт минимум.
Пример 3. Минимальная суммарная длина кодовых слов (тип 3)
Условие (реальное задание из открытого банка ФИПИ):
По каналу связи передаются шифрованные сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е, Ж. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 00, 01, 100, 111 соответственно. Укажите минимальную сумму длин кодовых слов для букв Д, Е и Ж, при которой код будет удовлетворять условию Фано.
Решение:
Известны А — 00, Б — 01, В — 100, Г — 111. Ветвь 0 занята целиком (00 и 01 — все узлы этой ветви на глубине 2). В ветви 10 занято 100 — свободен узел 101. В ветви 11 занято 111 — свободен узел 110.
Свободных слов длины 3 всего два (101 и 110), а букв — три. Неравенство Крафта показывает, что взять все три буквы длиной 3 нельзя: известные слова уже дают , и добавка трёх слов длины 3 потребовала бы ещё — сумма превысила бы 1. Значит, одно из двух свободных мест придётся разбить на два слова длины 4.
known = ["00", "01", "100", "111"]
words = free_words_needed(known, 3)
print(words, sum(len(w) for w in words))
# ['1010', '1011', '110'] 11Разбивать выгоднее самый короткий из двух слотов, но оба имеют одинаковую длину 3 — поэтому итог не зависит от выбора: взять 110 целиком, а 101 разбить на 1010 и 1011, либо наоборот. Сумма длин в обоих случаях.
Ответ: 11. Проверка неравенством Крафта: итоговый набор длин для всех семи букв — 2, 2 (А, Б), 3, 3, 3 (В, Г и одно из новых слов), 4, 4 (два оставшихся новых слова) — даёт — бюджет исчерпан ровно до единицы, меньшей суммы длин физически не существует.
Типичные ошибки и ловушки
Забыли проверить и предков, и потомков
Условие Фано нарушается в обе стороны: новое слово не может быть ни началом уже занятого слова, ни его продолжением. Проверяющие часто смотрят только «не начинается ли новое слово с уже занятого» и забывают проверить обратное — что уже занятое слово не является префиксом нового.
Выбрали свободное слово не минимальной длины
Условие Фано не нарушится, если взять слово подлиннее — но задание явно требует кратчайшее возможное. Всегда сначала проверяйте длины 1, потом 2, потом 3 и так далее — и останавливайтесь на первой длине, где нашлось свободное место.
Перепутали «наименьшее числовое значение» с «лексикографически меньшим»
Для двоичных строк одинаковой длины это совпадает (сравнение слева направо), но если по невнимательности сравнивать строки разной длины как числа напрямую, легко ошибиться. Сравнивайте только слова одинаковой (минимальной) длины.
Забыли, что букв может быть больше, чем свободных мест минимальной длины
Если букв, которым нужен код, больше числа свободных слов кратчайшей длины, часть букв обязана получить слова длиной на единицу больше. Присвоить всем буквам одинаково короткое слово в этом случае невозможно — дерево кодов не резиновое.
В типе 2 раздали короткие слова не по частоте
Минимальная суммарная длина сообщения достигается только тогда, когда самое короткое свободное слово получает самая частая буква. Если отдать короткое слово редкой букве, а частой — длинное, суммарное число знаков вырастет.
Забыли учесть уже известные буквы при подсчёте суммарной длины
В задачах на декодирование в сообщении часто встречаются и буквы с уже известными кодовыми словами (например, З в слове «КАЗАЧКА»). Их вклад в сумму — тоже длина слова, умноженная на число вхождений, и его нельзя пропускать.
В типе 3 не проверили неравенство Крафта
Соблазн взять одинаковую (минимальную из увиденных) длину для всех новых слов не всегда осуществим: если суммарный «бюджет» превышает 1, часть слов обязана быть длиннее. Быстрая проверка неравенством Крафта экономит время и страхует от неверного ответа.
Как задание 4 связано с остальным экзаменом
КЕГЭ содержит 27 заданий с кратким ответом (частей и развёрнутых ответов нет, максимальный первичный балл — 29). Задание 4 занимает в этой структуре скромное, но характерное место:
- оно входит в раздел «Теоретические основы информатики» — самый большой раздел кодификатора КЕГЭ, 11 заданий и 11 первичных баллов;
- рядом стоят другие задания про измерение и объём информации — задание 8 (КЭС 2.2, измерение количества информации через комбинаторику) и задание 11 (КЭС 2.2, информационный объём сообщения) — но в них нет условия Фано и дерева кодов, там считают степени двойки напрямую;
- приём «дерево кодов» и понимание префиксных кодов пригодятся и за пределами линии 4: та же идея неравномерного кодирования лежит в основе кода Хаффмана, который иногда всплывает в заданиях на программирование;
- задание 4 — одно из 11 заданий базового уровня, а значит, при равной сложности решения даёт тот же 1 балл, что и задания повышенного и высокого уровня — со всей комбинаторикой условия Фано оно остаётся одним из самых «дешёвых по времени» источников балла в работе.
План подготовки на 2 недели
Неделя 1 — условие Фано и дерево кодов
День 1–2: разберите определение условия Фано и обратного условия Фано, потренируйтесь строить дерево кодов на бумаге для 3–4 известных слов — рисуйте узлы и явно вычёркивайте предков и поддеревья занятых слов. День 3–4: решите 8–10 заданий типа 1 («укажите кратчайшее возможное кодовое слово»), каждый раз проверяя себя дважды: сначала по рисунку дерева, потом неравенством Крафта. День 5–7: напишите и запустите функцию shortest_free_words из этой статьи на своих примерах — программная проверка отучает от ошибок в сравнении строк.
Неделя 2 — декодирование и минимальная сумма
День 1–3: отработайте тип 2 — считайте частоты букв в сообщении и раздавайте короткие слова самым частым буквам; проверяйте на 5–6 заданиях из банка. День 4–5: разберите тип 3 — минимальная суммарная длина: сначала оцените неравенством Крафта, возможен ли «удобный» набор длин, потом стройте дерево и, если нужно, разбивайте самый короткий свободный слот. День 6–7: прорешайте все три типа вперемешку на время (не больше 2–3 минут на задание) и проверьте себя в тренажёре на заданиях из банка ФИПИ.
Проверьте себя на реальных заданиях
На Repet.ai собраны задания КЕГЭ по информатике из открытого банка ФИПИ. Решайте онлайн, проверяйте ответ мгновенно и разбирайте решение — бесплатно.
Часто задаваемые вопросы
Умение кодировать и декодировать информацию неравномерным двоичным кодом. Проверяемый элемент содержания — 2.1 «Кодирование и декодирование информации», раздел «Теоретические основы информатики». Чаще всего нужно достроить код так, чтобы он удовлетворял условию Фано, декодировать сообщение или найти минимальную суммарную длину кодовых слов.
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это гарантирует, что сплошную строку из нулей и единиц можно однозначно разбить обратно на буквы: встретив полное кодовое слово, получатель точно знает, что буква закончилась, а не является началом более длинного слова.
Прямое условие Фано запрещает кодовому слову быть началом (префиксом) другого. Обратное условие Фано запрещает слову быть окончанием (суффиксом) другого — оно проверяется так же, только слова предварительно разворачивают задом наперёд. В заданиях 4 КЕГЭ почти всегда используется именно прямое условие.
Нет. Условие Фано достаточно для однозначной расшифровки, но не необходимо: существуют непрефиксные коды, которые тоже декодируются однозначно за счёт другой структуры. Но в задании 4 ФИПИ прямо требует именно выполнения условия Фано, и искать более сложные альтернативы не нужно.
Постройте дерево кодов: каждое занятое слово блокирует все свои более короткие префиксы и всё своё поддерево более длинных продолжений. Проверяйте длины по возрастанию — 1, 2, 3 и так далее, — пока не найдётся хотя бы один узел, не заблокированный ни одним известным словом. Это и есть минимальная свободная длина.
Неравенство Крафта — сумма 2 в степени минус длина по всем кодовым словам не больше 1 — быстро проверяет, достижим ли предполагаемый набор длин, без построения полного дерева. Если сумма получившихся долей превышает 1, такой набор длин невозможен, и хотя бы одно слово придётся сделать длиннее.
Нужно посчитать частоту каждой ещё не закодированной буквы в сообщении и отдать самое короткое из свободных кодовых слов самой частой букве, следующее по длине — следующей по частоте, и так далее. Затем сложить произведения длины слова на число вхождений по всем буквам сообщения, включая уже известные.
Нет. Задание 4 самодостаточно по условию: все необходимые данные (известные кодовые слова, набор букв, при необходимости — кодируемое сообщение) даны в тексте вопроса. Специализированное программное обеспечение для решения не требуется, хотя весь экзамен КЕГЭ сдаётся за компьютером.
Готовы взять балл базового уровня без риска ошибиться?
Задание 4 решается по чёткому алгоритму: дерево кодов плюс неравенство Крафта как быстрая проверка. Отработайте все три типа задач на реальных заданиях из открытого банка ФИПИ с мгновенной проверкой ответа.