Задание 11. Объём информации

Задание 11 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 157 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 12 450 серийных номеров отведено не более 955 Кбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

В формуле $V$ – объём всей базы в байтах, $K$ – число записей, $L$ – длина одной записи в символах, $i$ – сколько бит отведено на один символ. Скобки – округление вверх: запись занимает целое число байт, поэтому биты на запись переводятся с избытком, а не ровно.

1. Переведите память в байты. 955 Кбайт – это $955 \cdot 1024 = 977920$ байт. Число 977 920 понадобится и дальше, так что лучше выписать его сразу.
2. Поделите на число номеров. $977920 / 12450 = 78{,}55$ лежит между 78 и 79. Памяти отведено «не более», значит на один номер приходится не больше 78 целых байт – дробь отбрасывается вниз.
3. Подберите бит на символ. Чем больше бит на символ, тем мощнее алфавит, поэтому нужен максимальный $i$, при котором запись ещё укладывается в 78 байт. Запись занимает целое число байт, то есть $\lceil 157 \cdot i / 8 \rceil$. При $i = 3$ байт на запись – 59, влезает; при $i = 4$ – уже 79, не влезает.
4. Ответьте на вопрос про алфавит. Спрашивают мощность алфавита, а не число бит на символ: $N = 2^{3} = 8$.

Ответ: 8.

В банке задание 11 встречается и в обратную сторону: алфавит задан условием, а длину записи надо найти.

Условие. На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры и символы из 17-символьного специального алфавита. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 7 564 230 серийных номеров требуется более 31 Мбайт памяти. Определите минимально возможную длину серийного номера.

1. Соберите алфавит. Десятичных цифр 10, специальных символов 17 – всего $10 + 17 = 27$. Ищем минимальное $i$, при котором $2^i \ge 27$: $2^{4} = 16$ мало, $2^{5} = 32$ хватает. Значит на символ уходит $i = 5$ бит.
2. Переведите память в байты. 31 Мбайт – это $31 \cdot 1024 \cdot 1024 = 32505856$ байт.

3. Поделите на число номеров. $32505856 / 7564230 = 4{,}30$ байт на один номер. Байт – число целое, значит на номер уходит либо 4, либо 5. Какое из двух – проверьте прямо по условию:

   • по 4 байта: вся база займёт $4 \cdot 7564230 = 30256920$ байт. Это меньше 31 Мбайт, то есть 32505856 байт. А в условии сказано «требуется более». Не подходит;
   • по 5 байт: $5 \cdot 7564230 = 37821150$ байт – это больше 32505856. Подходит.

   Значит на один номер уходит 5 байт.

4. Подберите длину. Запись из $L$ символов занимает $\lceil 5 \cdot L / 8 \rceil$ байт. При $L = 6$ выходит 4 – мало, нужно не меньше 5. При $L = 7$ – 5, и это первая длина, которая проходит.

Ответ: 7.

Сравните с примером 1: там «не более» отбросило дробь вниз и дало 78 байт на номер, здесь «более» округлило вверх и дало 5. Арифметика одна и та же – разошлось только направление, которое задаёт одно слово условия.

1. Округлили не в ту сторону. «Не более 955 Кбайт» отправляет дробь вниз: $977920 / 12450$ лежит между 78 и 79, и целых байт на номер – 78. «Требуется более 31 Мбайт» – вверх: $32505856 / 7564230$ лежит между 4 и 5, и байт на номер уже 5, а не 4. Прочитайте последнюю строку условия до того, как делить.
2. Ответили числом бит вместо мощности алфавита. Вопрос «мощность алфавита» просит $2^i$, а не $i$: в примере 1 верный ответ 8, а не 3. Там, где спрашивают «сколько бит на символ», всё наоборот.
3. Неверный перевод единиц. 1 байт = 8 бит, 1 Кбайт = 1024 байта, 1 Мбайт = 1024 Кбайт. Типичная подмена – деление на 1000: 955 Кбайт – это $955 \cdot 1024 = 977920$ байт, а не 955000.
4. Посчитали не весь алфавит. Условие перечисляет его по частям – цифры, латинские буквы, специальные символы, – и складывать нужно все. В примере 2 это $10 + 17 = 27$ символов. Цена ошибки: 26 латинских букв – 5 бит, а $26 + 10 = 36$ – уже 6.