ЕГЭ Информатика 2026

№4 Кодирование Фано

Теория

1. Основные понятия

1.1. Кодирование и декодирование

Кодирование это процесс преобразования информации из одной формы представления в другую.

Декодирование это процесс восстановления исходной информации из закодированного сообщения.

Однозначное декодирование это свойство кода, при котором любое закодированное сообщение может быть расшифровано единственным способом.

1.2. Равномерные и неравномерные коды

Pasted image

Равномерный код: код, в котором все кодовые слова имеют одинаковую длину.

Пример: Код ASCII где все символы кодируются 8 битами.

Неравномерный код: код, в котором кодовые слова могут иметь разную длину.

Пример: Код Морзе где разные символы имеют разную длину (точка это короткий сигнал, тире это длинный).

Преимущество неравномерных кодов: более частые символы можно кодировать более короткими кодовыми словами, что уменьшает общий объём сообщения.

2. Условие Фано

2.1. Прямое условие Фано

Формулировка: Никакое кодовое слово не является началом (префиксом) другого кодового слова.

Другое название: Префиксный код.

Пример правильного кода (удовлетворяет прямому условию Фано): А: 0 Б: 10 В: 110 Г: 111

Проверка: ни одно кодовое слово не является началом другого.

Пример неправильного кода (не удовлетворяет прямому условию Фано): А: 0 Б: 01 В: 10

Проблема: кодовое слово "0" (для А) является началом кодового слова "01" (для Б).

2.2. Обратное условие Фано

Формулировка: Никакое кодовое слово не является окончанием (суффиксом) другого кодового слова.

Пример правильного кода (удовлетворяет обратному условию Фано): А: 0 Б: 10 В: 110 Г: 1110

Проверка: ни одно кодовое слово не является окончанием другого.

2.3. Почему условие Фано важно?

Теорема: Код допускает однозначное декодирование тогда и только тогда, когда он удовлетворяет прямому или обратному условию Фано.

Практическое значение: При прямом условии Фано декодирование происходит слева направо (можно читать сообщение с начала) При обратном условии Фано декодирование происходит справа налево (можно читать сообщение с конца)

3. Построение кодовых деревьев

3.1. Бинарное дерево кодирования

Структура: 0. Корень дерева это пустая строка

  1. Левый ребёнок: добавляем 0
  2. Правый ребёнок: добавляем 1
  3. Листья дерева это кодовые слова

Пример построения дерева для кода: А: 0 Б: 10 В: 110 Г: 111

        (корень)
       /        \
      0          1
     /          / \
    А          0   1
              /   / \
             Б   0   1
                /   / \
               В   0   1
                  /     \
                 Г      (свободно)

3.2. Проверка условия Фано через дерево

Прямое условие Фано: Все кодовые слова находятся в листьях дерева (ни одно кодовое слово не является внутренней вершиной).

Если кодовое слово находится во внутренней вершине: оно является префиксом другого кодового слова, условие Фано нарушено.

4. Типичные задачи ЕГЭ (Задание 4)

4.1. Найти минимальную суммарную длину кодовых слов

Тип задачи: Даны некоторые кодовые слова, нужно найти минимальную суммарную длину всех кодовых слов при условии Фано.

Алгоритм решения:

  1. Построить дерево кодирования с заданными кодовыми словами
  2. Определить свободные вершины (где можно разместить оставшиеся кодовые слова)
  3. Для оставшихся букв выбрать кратчайшие возможные кодовые слова
  4. Вычислить суммарную длину всех кодовых слов

Пример: Для кодирования последовательности из букв И, К, Л, М, Н используется неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

Решение:

  1. Строим дерево: Н: 0 (занята левая ветвь от корня) К: 10 (занята правая ветвь от корня, затем левая)

  2. Свободные вершины: 11 (правая ветвь от корня, затем правая) 110, 111 (потомки вершины 11)

  3. Размещаем оставшиеся буквы (И, Л, М): И: 11 (кратчайшее) Л: 110 М: 111

  4. Суммарная длина: Н: 1 бит К: 2 бита И: 2 бита Л: 3 бита М: 3 бита Итого: 1 + 2 + 2 + 3 + 3 = 11 бит

4.2. Найти кратчайшее кодовое слово для буквы

Тип задачи: Даны кодовые слова для некоторых букв, нужно найти кратчайшее кодовое слово для оставшейся буквы.

Алгоритм решения:

  1. Построить дерево с заданными кодовыми словами
  2. Найти свободную вершину минимальной глубины
  3. Это и будет кратчайшее кодовое слово

Пример: По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова: A 1, B 010, C 000. Укажите кратчайшее кодовое слово для буквы E.

Решение:

  1. Строим дерево: A: 1 B: 010 C: 000

  2. Свободные вершины: 00 (префикс C, но не занята как кодовое слово) 01 (префикс B, но не занята) 011 001 0110, 0111 0010, 0011

  3. Кратчайшая свободная вершина: 00 (2 бита)

  4. Но нужно проверить, не нарушает ли это условие Фано: 00 не является началом 1, 010, 000 ✓ 1, 010, 000 не являются началом 00 ✓

  5. Ответ: 00

4.3. Определить количество бит для кодирования слова

Тип задачи: Даны кодовые слова для некоторых букв, нужно определить минимальное количество бит для кодирования заданного слова.

Алгоритм решения:

  1. Построить полное дерево кодирования (найти коды для всех букв)
  2. Для каждой буквы в слове найти её кодовое слово
  3. Сложить длины всех кодовых слов

Пример: По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А 010, Б 00, Г 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?

Решение:

  1. Строим дерево с заданными кодами: А: 010 Б: 00 Г: 101

  2. Находим коды для оставшихся букв (И, М, Р, Я), выбирая кратчайшие: И: 011 (кратчайшее свободное) М: 100 Р: 110 Я: 111

  3. Кодируем слово МАГИЯ: М: 100 (3 бита) А: 010 (3 бита) Г: 101 (3 бита) И: 011 (3 бита) Я: 111 (3 бита)

  4. Итого: 3 + 3 + 3 + 3 + 3 = 15 бит

4.4. Декодирование сообщения

Тип задачи: Дано закодированное сообщение и некоторые кодовые слова, нужно найти код для заданного слова.

Алгоритм решения:

  1. Декодировать известное сообщение, используя заданные кодовые слова
  2. Определить коды для всех букв
  3. Закодировать требуемое слово

Пример: Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Известно, что слово ДЕТИЩЕ кодируется как 100011100100001. Какой код соответствует слову ЩИТ?

Решение:

  1. Декодируем ДЕТИЩЕ = 100011100100001 Разбиваем на кодовые слова слева направо 1 это не может быть (неизвестно) 10 это не может быть 100 это возможно Д 011 это возможно Е 100 это возможно Т 100 это возможно И 001 это возможно Щ 00001 это возможно Е

  2. Определяем коды букв (нужно проверить все варианты разбиения)

  3. После определения всех кодов находим код для ЩИТ

Важно: Такие задачи требуют аккуратного перебора вариантов разбиения.

5. Алгоритм решения задач на кодирование

Шаг 1: Анализ условия

Определить тип условия Фано (прямое или обратное)
Выписать все заданные кодовые слова
Определить, что требуется найти

Шаг 2: Построение дерева

Начать с корня
Для каждого кодового слова пройти по дереву, добавляя 0 (влево) или 1 (вправо)
Отметить занятые вершины

Шаг 3: Поиск свободных вершин

Найти все свободные листья дерева
Выбрать кратчайшие для оставшихся букв

Шаг 4: Проверка условия Фано

Убедиться, что все кодовые слова в листьях
Проверить, что ни одно кодовое слово не является префиксом другого

Шаг 5: Вычисление ответа

Найти требуемую величину (суммарная длина, код буквы, длина сообщения)

6. Типичные ошибки и как их избежать

Ошибка 1: Неправильное построение дерева

Проблема: Путают левую и правую ветви (0 и 1).

Как избежать: Чётко определить: 0 это влево, 1 это вправо Проверять построенное дерево: путь от корня до листа должен соответствовать кодовому слову

Ошибка 2: Забывают проверить условие Фано

Проблема: Выбирают кодовое слово, которое нарушает условие Фано.

Как избежать: Всегда проверять, что выбранное кодовое слово не является префиксом уже существующих Проверять, что существующие кодовые слова не являются префиксом выбранного

Ошибка 3: Не находят кратчайшее кодовое слово

Проблема: Выбирают не самое короткое свободное кодовое слово.

Как избежать: Систематически проверять все свободные вершины, начиная с минимальной глубины Использовать обход дерева по уровням (сначала проверять вершины глубины 1, затем 2, и т.д.)

Ошибка 4: Неправильный подсчёт суммарной длины

Проблема: Забывают про некоторые буквы или считают неправильно.

Как избежать: Составить таблицу: буква это кодовое слово это длина Сложить все длины явно

Ошибка 5: Путают прямое и обратное условие Фано

Проблема: Применяют алгоритм для прямого условия, когда нужно обратное.

Как избежать: Внимательно читать условие задачи Прямое условие это декодирование слева направо Обратное условие это декодирование справа налево

7. Решение задач на Python (для проверки)

Пример: Построение дерева кодирования

class TreeNode:
    def __init__(self, code=''):
        self.code = code
        self.left = None  # 0
        self.right = None  # 1
        self.occupied = False  # Занята ли вершина кодовым словом

def build_tree(codes):
    """Строит дерево кодирования из словаря {буква: код}"""
    root = TreeNode()
    
    for letter, code in codes.items():
        node = root
        for bit in code:
            if bit == '0':
                if node.left is None:
                    node.left = TreeNode(node.code + '0')
                node = node.left
            else:  # bit == '1'
                if node.right is None:
                    node.right = TreeNode(node.code + '1')
                node = node.right
        node.occupied = True
    
    return root

def find_free_codes(node, free_codes, min_length=float('inf')):
    """Находит все свободные кодовые слова в дереве"""
    if node is None:
        return
    
    if not node.occupied and len(node.code) > 0:
        if len(node.code) <= min_length:
            free_codes.append(node.code)
    
    find_free_codes(node.left, free_codes, min_length)
    find_free_codes(node.right, free_codes, min_length)

# Пример использования
codes = {'Н': '0', 'К': '10'}
tree = build_tree(codes)

free_codes = []
find_free_codes(tree, free_codes)
print(f"Свободные коды: {sorted(free_codes, key=len)}")

Пример: Проверка условия Фано

def check_fano_condition(codes):
    """Проверяет, удовлетворяет ли код прямому условию Фано"""
    code_list = list(codes.values())
    
    for i, code1 in enumerate(code_list):
        for j, code2 in enumerate(code_list):
            if i != j:
                # Проверяем, не является ли code1 префиксом code2
                if code2.startswith(code1):
                    return False, f"Код '{code1}' является префиксом '{code2}'"
    
    return True, "Условие Фано выполнено"

# Пример
codes = {'А': '0', 'Б': '10', 'В': '110', 'Г': '111'}
is_valid, message = check_fano_condition(codes)
print(message)

8. Практические рекомендации

Для быстрого решения:

  1. Запомните: Прямое условие Фано это префиксный код это декодирование слева направо

  2. Используйте дерево для визуализации, это помогает избежать ошибок

  3. Систематически ищите свободные вершины, начните с глубины 1, затем 2, и т.д.

  4. Проверяйте условие Фано после выбора каждого нового кодового слова

Для сложных задач:

  1. Рисуйте дерево на бумаге, визуализация помогает
  2. Проверяйте все варианты разбиения при декодировании
  3. Используйте таблицу для подсчёта длин кодовых слов
  4. Для проверки можно написать простую программу на Python

9. Типичные формулировки в ЕГЭ

Формулировка Что это означает Метод решения
"Условие Фано" Прямое условие Фано (префиксный код) Построить дерево, проверить префиксы
"Прямое условие Фано" Никакое кодовое слово не является началом другого Декодирование слева направо
"Обратное условие Фано" Никакое кодовое слово не является окончанием другого Декодирование справа налево
"Однозначное декодирование" Каждое сообщение расшифровывается единственным способом Проверить условие Фано
"Наименьшая суммарная длина" Минимизировать сумму длин всех кодовых слов Выбрать кратчайшие коды для всех букв
"Кратчайшее кодовое слово" Найти свободную вершину минимальной глубины Обход дерева по уровням

10. Дополнительные примеры

Пример 1: Минимальная суммарная длина

Задача: Для кодирования букв А, Б, В, Г используется неравномерный двоичный код. Известно, что А это 0, Б это 10. Найдите минимальную суммарную длину кодов для всех четырёх букв.

Решение:

  1. Дерево: А это 0, Б это 10
  2. Свободные: 11
  3. Размещаем: В это 11, Г это 110 (или 111)
  4. Сумма: 1 + 2 + 2 + 3 = 8 бит

Пример 2: Декодирование с обратным условием Фано

Задача: Сообщение закодировано кодом, удовлетворяющим обратному условию Фано. Известно, что А это 0, Б это 10. Закодированное сообщение: 01010. Найдите исходное сообщение.

Решение: При обратном условии декодируем справа налево 01010 → читаем с конца: 0 это А, 10 это Б, 0 это А Ответ: АБА

Составлено: Лилия С.
Источники: КИМ ЕГЭ 2026, открытый банк ФИПИ, спецификация ЕГЭ по информатике, яндекс учебник

Удачи на экзамене! 🎓