Задание 11Формула Хартли

Формула Хартли

Обновлено 15 октября 2026 г.

Количество информации и формула Хартли

Компьютер хранит информацию в двоичном виде — с помощью нулей и единиц. Один двоичный разряд называется битом. С помощью одного бита можно записать два различных значения:

0,\ 1.

С помощью двух бит можно записать уже четыре различные комбинации:

00,\ 01,\ 10,\ 11.

Каждый дополнительный бит увеличивает количество возможных комбинаций в два раза. Поэтому с помощью $i$ бит можно закодировать:

N = 2^i

различных значений.

Алфавит и мощность алфавита

Алфавитом называют набор символов, которые могут использоваться для записи сообщения. Количество различных символов в алфавите называется его мощностью и обозначается $N$ .

Например, алфавит из десятичных цифр имеет мощность 10. Если разрешены десятичные цифры и 26 строчных латинских букв, мощность алфавита:

N = 10 + 26 = 36.

Если прописные и строчные буквы считаются различными символами, учитываем их отдельно:

N = 10 + 26 + 26 = 62.

Формула Хартли

Количество информации, приходящееся на один символ алфавита из $N$ равновероятных символов, определяется формулой Хартли:

i = \log_2 N.

Например, для алфавита из 32 символов:

i = \log_2 32 = 5 \text{ бит}.

В заданиях ЕГЭ обычно используется посимвольное кодирование: каждому символу соответствует двоичный код одинаковой длины. При этом длина кода должна быть целым числом бит.

Если мощность алфавита не является степенью двойки, результат округляют вверх:

i = \lceil \log_2 N \rceil.

Обозначение $\lceil x \rceil$ означает округление числа вверх до ближайшего целого.

Например, для 36 символов пяти бит недостаточно: они дают только 32 различные комбинации. Шесть бит дают 64 комбинации, поэтому их достаточно:

2^5 < 36 \leq 2^6,\qquad i = 6.

Использовать все 64 комбинации необязательно. Часть из них может оставаться свободной.

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

Если сообщение содержит $l$ символов, каждый из которых кодируется $i$ битами, его информационный объём:

I = l \cdot i \text{ бит}.

Например, для пароля из 15 символов алфавита мощностью 36:

I = 15 \cdot 6 = 90 \text{ бит}.

В заданиях объём памяти обычно измеряется в байтах, Кбайтах или Мбайтах:

1 \text{ байт} = 8 \text{ бит},

1 \text{ Кбайт} = 1024 \text{ байта},

1 \text{ Мбайт} = 1024 \text{ Кбайта} = 1024^2 \text{ байт}.

Если для хранения каждого пароля выделяется минимальное целое число байт, его объём в байтах тоже округляют вверх:

B = \left\lceil \frac{l \cdot i}{8} \right\rceil.

Для рассмотренного пароля:

B = \left\lceil \frac{90}{8} \right\rceil = 12 \text{ байт}.

Одиннадцать байт содержат только 88 бит, поэтому их недостаточно.

Хранение нескольких сообщений

Если один пароль занимает $B$ байт, то для хранения $k$ таких паролей потребуется:

V = k \cdot B.

Например, для 100 паролей по 12 байт:

V = 100 \cdot 12 = 1200 \text{ байт}.

Важно соблюдать порядок действий: сначала округляем объём одного пароля до целого числа байт, затем умножаем на количество паролей. Это связано с тем, что память выделяется отдельно для каждого пароля.

Если вместе с паролем хранятся дополнительные сведения объёмом $D$ байт на пользователя, общий объём:

V = k(B + D).

Отсюда объём дополнительных сведений об одном пользователе:

D = \frac{V}{k} - B.

Обратные задачи

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

При составлении неравенства обращаем внимание на условие:

\begin{array}{c|c} \text{Формулировка} & \text{Знак} \\ \hline \text{не более} & \leq \\ \text{менее} & < \\ \text{не менее} & \geq \\ \text{более} & > \end{array}

Если найдено количество бит на символ, важно правильно определить мощность алфавита. Для кодирования символов требуется ровно $i$ бит при условии:

2^{i-1} < N \leq 2^i.

Поэтому при $i \geq 1$ максимальная и минимальная мощности такого алфавита:

N_{\max} = 2^i,\qquad N_{\min} = 2^{i-1} + 1.

Например, ровно 6 бит на символ требуется для алфавитов мощностью от 33 до 64.

Разбор задачи ЕГЭ

Каждой детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы и символы из 458-символьного специального алфавита. Все символы кодируются одинаковым и минимально возможным количеством бит. Для каждого номера выделяется минимальное целое число байт. Для хранения 862 номеров отведено не более 276 Кбайт. Найдём максимально возможную длину номера.

Сначала определим мощность алфавита:

N = 10 + 52 + 458 = 520.

На один символ потребуется:

i = \lceil \log_2 520 \rceil = 10 \text{ бит},

так как $2^9 < 520 \leq 2^{10}$ .

Переведём доступный объём памяти в байты:

V = 276 \cdot 1024 = 282624 \text{ байта}.

Разделим его на количество номеров. Поскольку превышать доступную память нельзя, округлим вниз:

B = \left\lfloor \frac{282624}{862} \right\rfloor = 327 \text{ байт}.

Обозначение $\lfloor x \rfloor$ означает округление числа вниз до ближайшего целого.

Таким образом, один номер может занимать не более 327 байт. Переведём этот объём в биты:

327 \cdot 8 = 2616 \text{ бит}.

Каждый символ занимает 10 бит. Следовательно, максимальная длина номера:

l_{\max} = \left\lfloor \frac{2616}{10} \right\rfloor = 261.

Решение на Python

Эту же задачу можно решить на Python, если знать две функции из библиотеки math:

ceil(x) — округляет число вверх до ближайшего целого. Например, ceil(3.2) = 4.

log2(x) — вычисляет двоичный логарифм числа. Например, log2(32) = 5, поскольку 2⁵=32.

Для использования этих функций их нужно импортировать:

from math import ceil, log2

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

i = ceil(log2(10 + 52 + 458))

Здесь сначала складываются мощности всех частей алфавита, затем вычисляется двоичный логарифм, а результат округляется вверх. Получаем i = 10 бит на символ.

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

Для этого используем цикл:

for l in range(1,10000):

Переменная l последовательно принимает значения от 1 до 9999. Для этой задачи такого диапазона достаточно: даже 1000 символов по 10 бит уже не поместятся в доступную память при указанном количестве номеров.

Для каждой длины вычисляем объём одного серийного номера в байтах:

b = ceil(l * i / 8)

Произведение l * i даёт количество бит в номере. Деление на 8 переводит биты в байты, а ceil округляет результат вверх, поскольку каждому номеру выделяется целое число байт.

Теперь проверяем, помещаются ли все номера в доступную память:

if b * 862 <= 276 * 1024:

Слева находится объём 862 номеров в байтах, справа — доступные 276 Кбайт, переведённые в байты. Знак <= соответствует словам «не более» в условии.

Если условие выполняется, сохраняем текущую длину:

maxl = l

Перебор идёт по возрастанию. Каждая следующая подходящая длина заменяет предыдущую, поэтому после завершения цикла в maxl останется максимально возможная длина.

Таким образом, получим:

from math import ceil, log2
i = ceil(log2(10 + 52 + 458))
for l in range(1,10000):
    b = ceil(l * i / 8)
    if b * 862 <= 276 * 1024:
        maxl = l
print(maxl)

Программа выводит 261. Аналогично можно решать задачи с неизвестной мощностью алфавита: тогда перебираем a, внутри цикла вычисляем i = ceil(log2(a)), а длину номера берём из условия. Если требуется минимальное значение, выводим первое подходящее и останавливаем цикл через break; если максимальное — сохраняем последнее подходящее значение, как в этой задаче.