Условие Фано

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 26
Условие Фано
Двоичное кодирование · Алгоритм Хаффмана · Декодирование
Глава 26 посвящена
префиксным кодам
— кодам, которые декодируются однозначно без разделителей. Изучаем условие Фано, кодовое дерево, алгоритм Хаффмана и практику.
ФГОС
ФОП
ОГЭ №2,4
ЕГЭ №4
📚
Теория
26.1
Условие Фано
Префиксные коды, определение, дерево кода, неравенство Крафта
26.2
Двоичное кодирование
Алгоритм Хаффмана, равномерные и неравномерные коды, оптимальность
26.3
Декодирование
Пошаговый декодер, ошибки дешифровки, однозначность
🎯
Практика
26.4
Практикум ОГЭ/ЕГЭ
50+ заданий с фильтрами, разборами и статистикой
26.5
Экзамен-полигон
Квест 800 XP · Тест 8 мин · Развёрнутая задача
🔗
Связь с другими главами
Предыдущая глава
Глава 25 · Деревья
— бинарные деревья, обход, двоичное дерево — фундамент для дерева кода.
Следующая глава
Глава 27 · Энтропия
— количественная мера информации, связь с оптимальным кодированием.
📝
Ключевые формулы
Понятие
Формула
Описание
Условие Фано
Ни одно кодовое слово не префикс другого
Однозначное декодирование
Неравенство Крафта
∑ 2
−Li
≤ 1
Условие существования префиксного кода
Хаффман
min-heap → дерево → коды
Жадный алгоритм оптимального кодирования
Средняя длина
L = Σ pᵢ × lᵢ
Взвешенная сумма длин по частотам
Энтропия
H = −Σ pᵢ log₂(pᵢ)
Минимальная возможная средняя длина