Энтропия Шеннона

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

← Вернуться к оглавлению
Alterna · глава 27 · страница 27.3
Энтропия Шеннона
H = −Σ pᵢ·log₂pᵢ · Свойства · U-кривая · Кодирование.
Энтропия Шеннона
— универсальная мера неопределённости источника. Она обобщает формулу Хартли на случай неравновероятных событий и задаёт теоретический минимум длины кода.
ФГОС
ФОП
ЕГЭ №8,11
Связь с главой 26.
Теорема Шеннона о кодировании: средняя длина оптимального кода (алгоритм Хаффмана из
главы 26
) стремится к энтропии H снизу. H ≤ L̄ < H + 1.
01
Формула Шеннона
Для источника с N символами с вероятностями p₁, p₂, …, pₙ:
H = −Σ pᵢ · log₂(pᵢ) = Σ pᵢ · log₂(1/pᵢ)
Каждое слагаемое:
pᵢ · log₂(1/pᵢ)
— вклад символа с вероятностью pᵢ. Если pᵢ = 0, слагаемое равно 0 (принято по соглашению: 0·log₂0 = 0).
Пример вычисления
Три символа: p₁ = 0.5, p₂ = 0.3, p₃ = 0.2
−0.5·log₂(0.5) = 0.5·1 = 0.5
−0.3·log₂(0.3) ≈ 0.3·1.737 ≈ 0.521
−0.2·log₂(0.2) ≈ 0.2·2.322 ≈ 0.464
H ≈ 0.5 + 0.521 + 0.464 =
1.485 бит
02
Свойства энтропии
H ≥ 0
— энтропия всегда неотрицательна.
H = 0
— один из исходов имеет вероятность 1 (нет неопределённости).
H = log₂N
— максимум при равномерном распределении (все pᵢ = 1/N).
H монотонно убывает
при удалении от равномерного распределения.
H аддитивна:
для независимых источников H(X,Y) = H(X) + H(Y).
03
Калькулятор энтропии
📊
Вычислить H(p₁, p₂, ...)
Вероятности через пробел (например: 0.5 0.3 0.2)
Введите вероятности и нажмите «Рассчитать».
04
U-кривая: H(p) для двух событий
Для источника с двумя символами (p и 1−p):
H(p) = −p·log₂p − (1−p)·log₂(1−p)
График — симметричная колоколообразная кривая с максимумом
H = 1 бит при p = 0.5
и нулями при p = 0 и p = 1.
📈
U-кривая: H(p) при двух исходах
p =
p = 0.50
H = 1.000
05
Связь с кодированием
Теорема Шеннона о кодировании источника:
средняя длина оптимального кода L̄ удовлетворяет:
H ≤ L̄ < H + 1
Это означает, что нельзя сжать данные сильнее энтропии источника без потерь — H является нижней границей сжатия.
Пример: символы с разной частотой
Источник: А — 50%, Б — 25%, В — 12.5%, Г — 12.5%
H = -(0.5·log₂0.5 + 0.25·log₂0.25 + 0.125·log₂0.125 + 0.125·log₂0.125) = 0.5 + 0.5 + 0.375 + 0.375 =
1.75 бит
Код Хаффмана: А=0, Б=10, В=110, Г=111 → L̄ = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 =
1.75 бит
= H ✓
06
Игра: шарики и информация
🎱
Сколько шаров в урне? Достань несколько — узнай!
В урне шары разных цветов. Ты достаёшь шары
с возвращением
. Каждый доставитый шар даёт информацию по Шеннону. Накопи 95% информации о составе урны!
Нажми чтобы
достать шар
Извлечено шаров:
Накоплено информации:
0%
07
Построй код Хаффмана
🌳
Интерактивное дерево Хаффмана
Символы отсортированы по вероятности. На каждом шаге объединяй два
наименьших
узла — нажми на них. После завершения увидишь нарисованное дерево с кодами.
08
Рандомайзер задач на H
🎲
Тренажёр: вычисли энтропию источника
Генерирует случайные задачи на вычисление H по формуле Шеннона.
Нажми «Новая задача» для начала.
🎯
Мини-тест: 5 вопросов
XP: 0
🧩
Проверь себя
5 вопросов по энтропии Шеннона · 20 XP за каждый правильный ответ