Задание 11 ЕГЭ: пароли и объём памяти для хранения сведений о пользователях

Что проверяет задание

Задание 11 проверяет умение считать объём информации при посимвольном кодировании данных равной длины. Речь идёт о ситуации, когда в системе хранятся пароли пользователей вместе с дополнительными сведениями (именем, датой регистрации и прочим), и нужно определить, сколько байт памяти требуется для хранения записей о группе пользователей — или наоборот, восстановить неизвестную величину (длину пароля, объём доп. сведений, число пользователей) по данному итоговому объёму памяти.

По сути это задача на два взаимосвязанных навыка: перевод количества символов алфавита в число бит на символ и аккуратная работа с округлением при переводе битов в байты.

Как выглядит формулировка и сколько баллов

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

Задание относится к части с кратким ответом — нужно записать целое число. Оценивается в 1 балл, но ошибка в округлении обычно приводит к полностью неверному ответу, поэтому важна аккуратность на каждом шаге.

Что нужно знать

• Формула Хартли для определения числа бит на символ: если алфавит содержит $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. Прямой расчёт объёма памяти по алфавиту, длине пароля и доп. сведениям. Это основной метод: сначала находим $i$ по $N$, затем объём пароля в байтах с округлением вверх, складываем с $D$, умножаем на $K$. Мини-пример: алфавит из 6 символов, $2^2=4 < 6 \le 2^3=8$, значит $i=3$ бита. Пароль из 4 символов: $3 \cdot 4 = 12$ бит $= 1.5$ байта, округляем вверх — 2 байта на пароль.

Метод 2. Нахождение мощности алфавита через число бит. Если в условии не дан явный список символов, а сказано «использовано $i$ бит на символ», то максимальное число различных символов алфавита равно $N = 2^i$. Это используется, когда нужно проверить, хватает ли выделенных бит на данный алфавит. Мини-пример: если на символ отведено 4 бита, максимальное число символов в алфавите — $2^4 = 16$.

Метод 3. Обратная задача — поиск объёма дополнительных сведений $D$. Если известен суммарный объём памяти $M$ для $K$ пользователей, сначала находим объём на одного пользователя: $S = M / K$. Затем вычисляем объём пароля в байтах обычным способом (через $N$ и $L$) и находим $D = S - V_{байт}(пароль)$. Мини-пример: на 10 пользователей ушло 150 байт, значит $S=15$ байт на пользователя; если пароль занимает 5 байт, то $D = 15-5=10$ байт.

Метод 4. Обратная задача — поиск длины пароля $L$ или числа пользователей $K$. Аналогично методу 3, но неизвестной является другая величина. Из $S = V_{байт}(пароль) + D$ выражаем $V_{байт}(пароль) = S - D$, переводим в биты умножением на 8 и делим на $i$, получая $L$. Либо из $M = S \cdot K$ находим $K = M/S$. Важно помнить, что при обратном ходе округление «туда-обратно» может дать неоднозначность — нужно проверять, что найденное значение целое и физически осмысленное (например, $L$ не может быть дробным).

Метод 5. Проверка правдоподобия ответа через прикидку границ. Перед финальным ответом полезно оценить порядок величины: например, для 50 пользователей и записи в 20 байт итог должен быть около 1000, а не 100 или 10000. Такая прикидка помогает заметить арифметическую ошибку или пропущенное округление.

Алгоритм решения по шагам

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

Разбор примеров

Пример 1. Условие: пароль из 15 символов, алфавит из 12 символов; на доп. сведения отведено 12 байт на пользователя. Найти объём памяти для 50 пользователей.

Шаг 1. Мощность алфавита $N=12$.

Шаг 2. Находим $i$: $2^3=8<12$, $2^4=16\ge 12$, значит $i=4$ бита на символ.

Шаг 3. Объём пароля в битах: $i \cdot L = 4 \cdot 15 = 60$ бит.

Шаг 4. Переводим в байты: $60/8=7.5$ байт. Так как требуется целое число байт, округляем вверх: $8$ байт на пароль.

Шаг 5. Прибавляем доп. сведения: $S = 8+12=20$ байт на одного пользователя.

Шаг 6. Для 50 пользователей: $M = 20 \cdot 50 = 1000$ байт.

Ответ: 1000 — совпадает с эталонным.

Пример 2. Условие: пароль из 15 символов, алфавит из 12 символов (те же данные, что в примере 1); для хранения сведений о 20 пользователях потребовалось 400 байт. Нужно найти, сколько байт выделено на доп. сведения об одном пользователе.

Шаг 1–4 (как в примере 1): алфавит из 12 символов даёт $i=4$ бита, объём пароля $4 \cdot 15 = 60$ бит $= 7.5$ байта, округляем вверх — 8 байт на пароль.

Шаг 5. Находим объём на одного пользователя из общего объёма: $S = 400 / 20 = 20$ байт.

Шаг 6. Так как $S = V_{байт}(пароль) + D$, получаем $D = S - 8 = 20 - 8 = 12$ байт.

Ответ: 12 — совпадает с эталонным. Этот пример показывает применение метода 3: движение «от общего объёма назад» к искомой составляющей.

Пример 3. Условие: пароль из 6 символов, алфавит из 7 символов (Н, О, Р, С, Т, У, Х); на доп. сведения отведено 10 байт. Найти объём памяти для 100 пользователей.

Шаг 1. Мощность алфавита $N=7$.

Шаг 2. Находим $i$: $2^2=4<7$, $2^3=8\ge 7$, значит $i=3$ бита на символ.

Шаг 3. Объём пароля в битах: $i \cdot L = 3 \cdot 6 = 18$ бит.

Шаг 4. Переводим в байты: $18/8=2.25$ байта, округляем вверх — $3$ байта на пароль.

Шаг 5. Прибавляем доп. сведения: $S = 3 + 10 = 13$ байт на одного пользователя.

Шаг 6. Для 100 пользователей: $M = 13 \cdot 100 = 1300$ байт.

Ответ: 1300 — совпадает с эталонным.

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

Типичные ошибки и ловушки

• Округление бит на символ вниз вместо вверх. Если алфавит содержит 12 символов, $\log_2 12 \approx 3.58$, и часто ошибочно берут $i=3$ (округление до целой части), хотя нужно $i=4$, так как 3 бита дают только $2^3=8$ комбинаций — этого не хватит на 12 символов.
• Забытое округление объёма пароля в байтах. Если получилось дробное число байт (например, 7.5), нельзя оставить его дробным или округлить вниз — по условию задачи выделяется минимальное целое число байт, значит округление строго вверх.
• Округление объёма пароля в битах вместо байтов. Округлять нужно именно после перевода в байты, а не сам результат умножения $i \cdot L$, который всегда целый по построению.
• Путаница между объёмом на одного пользователя и общим объёмом. При решении обратных задач важно чётко разделять $S$ (на одного) и $M$ (на всех), иначе легко разделить или умножить на неверное число.
• Неверный подсчёт мощности алфавита. Если символы перечислены через запятую, нужно посчитать их количество внимательно — легко ошибиться на единицу, особенно если в списке встречаются похожие буквы разных алфавитов (кириллица/латиница).
• Забытые дополнительные сведения. В некоторых формулировках доп. сведения могут отсутствовать или, наоборот, быть заданы не в байтах, а в битах — нужно внимательно читать единицы измерения в условии.
• Ошибка на последнем шаге умножения. После нахождения объёма на одного пользователя легко забыть умножить на число пользователей или, наоборот, умножить дважды при работе с обратной задачей.

Как готовиться

Отработайте формулу $2^i \ge N$ до автоматизма: полезно заранее выучить степени двойки от $2^1$ до $2^{10}$, чтобы быстро определять минимальное $i$ для любого разумного размера алфавита без вычисления логарифма на бумаге. Решайте задачи в обе стороны — и на нахождение общего объёма по известным параметрам, и на восстановление одного из параметров по известному итоговому объёму, — чтобы одинаково уверенно применять формулы в прямом и обратном порядке. При разборе каждой новой задачи выписывайте отдельно все известные величины ($N$, $L$, $D$, $K$, $M$) и явно отмечайте, какая величина неизвестна — это снижает риск путаницы при подстановке в формулы. После получения ответа делайте быструю прикидку порядка величины: если для 50 пользователей с записью в 20 байт получился ответ в 100 байт или в 10000 байт, это явный сигнал ошибки. Также стоит решить несколько задач с разным типом «неизвестной» — где ищется не итоговый объём, а длина пароля, размер алфавита или число пользователей, — чтобы алгоритм решения был гибким, а не привязан к одному шаблону.