Задание 11: Вычисление количества информации

Типичная формулировка: «Пароль состоит из $L$ символов и содержит только символы из алфавита мощностью $N$. Для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт, символы кодируются одинаковым минимальным числом бит. Кроме пароля хранятся дополнительные сведения объёмом $D$ байт. Определите объём памяти для хранения сведений о $K$ пользователях» — либо обратная задача, где известен итоговый объём, а найти нужно одну из величин ($L$, $N$, $D$ или $K$).

…

• Формула Хартли для определения числа бит на символ: если алфавит содержит $N$ символов, то количество бит $i$, необходимое для кодирования одного символа, находится из условия $2^i \ge N$, при этом берётся наименьшее подходящее целое $i$.
• Если $N$ — степень двойки, то $i = \log_2 N$ точно. Если нет — $i$ округляется вверх: $i = \lceil \log_2 N \rceil$.
• Объём одного пароля в битах: $V_{бит} = i \cdot L$, где $L$ — длина пароля в символах.
• Перевод бит в байты: $1 \text{ байт} = 8 \text{ бит}$, значит $V_{байт} = V_{бит} / 8$.
• Если при делении на 8 получается не целое число, объём округляется вверх до целого числа байт — это ключевое требование условия задачи («минимально возможное целое число байт»).
• Полный объём сведений об одном пользователе: $S = V_{байт}(пароль) + D$, где $D$ — объём дополнительных сведений в байтах.
• Объём памяти для $K$ пользователей: $M = S \cdot K$.
• В обратных задачах те же формулы применяются «в обратную сторону»: из известного $M$ и $K$ находится $S$, а затем недостающая часть (например, $D$) через вычитание известной части.

1. Определить мощность алфавита $N$ — посчитать количество различных символов, перечисленных в условии.
2. Найти минимальное число бит на символ: подобрать наименьшее целое $i$, при котором $2^i \ge N$.
3. Вычислить объём одного пароля в битах: $i \cdot L$, где $L$ — длина пароля.
4. Перевести объём пароля в байты делением на 8; если результат не целый — округлить вверх до следующего целого.
5. Прибавить к объёму пароля объём дополнительных сведений $D$ (если он дан в условии) — получить объём записи об одном пользователе $S$.
6. Если требуется найти общий объём — умножить $S$ на число пользователей $K$.
7. Если в условии дана обратная ситуация (известен общий объём или объём на одного пользователя, а что-то нужно найти) — выразить искомую величину из соответствующей формулы и проверить целостность и физическую осмысленность результата. …