Решение: Объём памяти идентификаторов
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 317 символов и содержащий только десятичные цифры и символы из 4090-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Определите объём памяти (в Мбайт), необходимый для хранения 262 144 идентификаторов.
Решение по шагам
4 шагаОпределим размер алфавита идентификаторов: к 4090 специальным символам добавляются 10 десятичных цифр.
$$N = 4090 + 10 = 4100$$Найдём минимальное одинаковое количество бит для кодирования одного символа. Так как $2^{12} = 4096 < 4100 \leq 8192 = 2^{13}$, требуется 13 бит.
$$i = \lceil \log_2 4100 \rceil = 13$$Объём одного идентификатора в битах равен $317 \cdot 13 = 4121$. Переведём в байты с округлением вверх.
$$b = \left\lceil \dfrac{4121}{8} \right\rceil = 516\ \text{байт}$$Для $262144 = 2^{18}$ идентификаторов потребуется $516 \cdot 262144$ байт. Так как $1\ \text{Мбайт} = 2^{20}$ байт, получаем $516 \cdot 2^{18} / 2^{20} = 129$ Мбайт.
$$V = \dfrac{516 \cdot 262144}{2^{20}} = 129\ \text{Мбайт}$$Где здесь ошибаются
Забывают добавить 10 десятичных цифр к размеру специального алфавита.
Ошибочно считают, что 12 бит достаточно для 4100 символов.
Не округляют объём одного идентификатора вверх до целого числа байт.