Измерение информации: алфавитный подход и log2

Фундамент всего раздела кодирования: как из мощности алфавита получить объём данных.

Алфавитный подход: количество информации в сообщении зависит только от мощности алфавита и длины сообщения, а не от смысла. Один символ алфавита из N знаков несёт i бит, где 2ⁱ = N.

Бит, байт и степени двойки

Информация в компьютере измеряется в битах. Бит — это выбор из двух вариантов (0 или 1). Байт = 8 бит. Дальше идут двоичные приставки, и это первое, что нужно довести до автоматизма: в информатике 1 Кбайт — это не 1000, а 1024 байта.

Единица	Сколько байт	Степень двойки
1 байт	8 бит	2³ бит
1 Кбайт	1024 байта	2¹⁰
1 Мбайт	1024 Кбайт	2²⁰
1 Гбайт	1024 Мбайт	2³⁰

Большинство ошибок в заданиях 7 и 11 — это путаница с переводами единиц. Привыкайте всё держать в степенях двойки: тогда деление на 1024 — это просто вычитание 10 из показателя степени.

Главная формула: i = log2(N)

Пусть алфавит содержит N различных символов. Чтобы закодировать один символ, нужно i бит, причём:

N = 2^i        =>        i = log2(N)

Примеры, которые стоит знать наизусть:

Алфавит из 2 символов → 1 бит на символ (2¹=2).
Из 8 символов → 3 бита (2³=8).
Из 32 символов → 5 бит (2⁵=32).
Из 256 символов → 8 бит = 1 байт.

Если N не степень двойки (например 6 цветов), то i округляют вверх до целого: для 6 вариантов нужно 3 бита, потому что 2 бита дают только 4 комбинации, а 3 — целых 8 (с запасом). Это ловушка: log₂6 ≈ 2,58, но память выделяется целыми битами, поэтому 3.

Объём сообщения

Если сообщение состоит из K символов, а каждый символ несёт i бит, то весь объём:

I = K · i   (бит)

Разберём типовой пример. Алфавит племени содержит 32 символа. Сообщение состоит из 80 символов. Сколько байт информации оно несёт?

import math

N = 32                      # мощность алфавита
K = 80                      # длина сообщения в символах
i = math.log2(N)            # бит на один символ
I_bit = K * i               # объём в битах
I_byte = I_bit / 8          # объём в байтах

print("бит на символ:", int(i))
print("объём, бит:", int(I_bit))
print("объём, байт:", int(I_byte))

Вывод:

бит на символ: 5
объём, бит: 400
объём, байт: 50

Обратная задача: найти N или K

Часто известен объём, а найти нужно мощность алфавита или длину. Если сообщение из 20 символов заняло 100 бит, то на символ приходится 100/20 = 5 бит, значит алфавит — 2⁵ = 32 символа.

# Сообщение из 20 символов заняло 100 бит. Найти мощность алфавита.
I_bit = 100
K = 20
i = I_bit // K              # бит на символ
N = 2 ** i                  # мощность алфавита
print("бит на символ:", i)
print("мощность алфавита N:", N)

Вывод:

бит на символ: 5
мощность алфавита N: 32

Комбинаторный взгляд: пароли и номера

Тот же алфавитный подход отвечает на вопрос «сколько различных сообщений длины K можно составить из алфавита в N символов». Ответ — N^K. Это основа задания 8 (комбинаторика) и часто всплывает в задании 11. Разберём: «Пароль состоит из 6 символов; каждый символ — заглавная латинская буква (26) или цифра (10). Сколько существует разных паролей и сколько бит нужно для хранения номера пароля?»

import math

N = 26 + 10          # мощность алфавита: буквы + цифры
K = 6                # длина пароля
total = N ** K       # сколько всего паролей
bits_per_symbol = math.ceil(math.log2(N))   # бит на символ, округляя вверх
bits_total = K * bits_per_symbol

print("всего паролей:", total)
print("бит на символ:", bits_per_symbol)
print("бит на весь пароль:", bits_total)
print("байт на пароль (округляя вверх):", math.ceil(bits_total / 8))

Вывод:

всего паролей: 2176782336
бит на символ: 6
бит на весь пароль: 36
байт на пароль (округляя вверх): 5

Обратите внимание: на 36 символов нужно 6 бит (2⁵=32 мало, 2⁶=64 хватает), и на каждый символ память выделяется одинаковая — по 6 бит, даже если конкретный символ можно было бы закодировать короче. В таких задачах всегда берут максимальную длину кода для всех символов.

Типичные ловушки

Округление вверх. Если N не степень двойки, i округляют вверх до целого числа бит. log₂6 = 2,58 → берём 3 бита.
1 Кбайт = 1024 байта, а не 1000. Деление на 1000 вместо 1024 — частая потеря балла.
Бит и байт. Не забывайте делить на 8 при переходе от бит к байтам.
Что считать алфавитом. Если в задании сказано «использованы заглавные латинские буквы и цифры», N = 26 + 10 = 36, а не 26.
N^K против K·i. «Сколько разных сообщений» — это N^K; «сколько памяти под одно сообщение» — это K·i. Не путайте две формулы.

Итог

Один символ алфавита из N знаков несёт i = log₂N бит; если N не степень двойки — округляем вверх.
Объём сообщения I = K · i бит; для байтов делим на 8.
Все переводы единиц держите в степенях двойки: 1 Кбайт = 2¹⁰ байт.