Решение: Мощность алфавита серийного номера
На предприятии каждой изготовленной детали присваивается серийный номер, состоящий из 248 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 75 600 серийных номеров требуется более 16 Мбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров.
Решение по шагам
6 шаговВычислим объём памяти, соответствующий 16 Мбайт:
$$16 \cdot 2^{20} = 16777216\ \text{байт}$$На один серийный номер должно приходиться более:
$$\frac{16777216}{75600} \approx 221{,}92\ \text{байт}$$Так как объём каждого номера задаётся целым числом байт, необходимо не менее $222$ байт на номер.
При кодировании одним символом $k$ битами номер занимает:
$$\left\lceil\frac{248k}{8}\right\rceil = 31k\ \text{байт}$$При $k=7$ получаем $31 \cdot 7=217$ байт, что недостаточно. При $k=8$ получаем $31 \cdot 8=248$ байт, поэтому требуется 8 бит на символ.
Чтобы для кодирования символов требовалось 8 бит, мощность алфавита должна быть больше $2^7$, но не превышать $2^8$. Минимальная возможная мощность:
$$2^7+1=129$$Где здесь ошибаются
Использовать 16 Мбайт как $16 \cdot 10^6$ байт вместо $16 \cdot 2^{20}$ байт.
Забыть округление объёма одного серийного номера до целого числа байт.
Ответить $128$, хотя для 128 символов достаточно 7 бит; 8 бит требуют алфавиты мощности от 129 символов.