Задание 11 ЕГЭ по информатике: объём паролей и идентификаторов — разбор и примеры

В задании 11 описывается система, которая хранит пароли, идентификаторы, автомобильные номера или серийные коды. Каждый символ кодируется одинаковым минимально возможным числом бит, а каждая запись целиком занимает целое число байт. Требуется найти объём памяти для заданного количества записей — или, наоборот, по объёму восстановить неизвестный параметр: длину кода, размер алфавита, объём дополнительных сведений. Задача решается за несколько строк вычислений, если не перепутать порядок округлений.

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

• знание формулы Хартли: чтобы закодировать N различных символов, нужно i бит, где i — наименьшее целое с условием 2**i >= N;
• умение переводить биты в байты и округлять вверх до целого числа байт;
• понимание, что округление делается для одной записи, а не для всей базы целиком;
• аккуратность с единицами: 1 байт = 8 бит, 1 Кбайт = 1024 байт.

Типичные формулировки

1. Прямая задача: «Пароль состоит из 14 символов, алфавит — 26 заглавных латинских букв и 10 цифр. Сколько байт нужно для хранения 300 паролей?»
2. Пароль плюс дополнительные сведения: «Для каждого пользователя хранятся пароль и дополнительные сведения, занимающие одинаковое целое число байт».
3. Обратная задача на дополнительные сведения: «Для хранения сведений о 50 пользователях потребовалось 1500 байт. Сколько байт отведено на дополнительные сведения об одном пользователе?»
4. Обратная задача на алфавит или длину: «Какое наибольшее количество символов может содержать алфавит / какова наибольшая длина пароля?»

Пошаговый метод

1. Найдите мощность алфавита N. Сложите все группы символов: заглавные и строчные буквы, цифры, специальные знаки. Внимательно прочитайте, какие буквы разрешены: русских букв 33, латинских — 26.
2. Найдите бит на символ i: наименьшее целое, при котором 2**i >= N. Полезно помнить степени двойки: 16, 32, 64, 128, 256.
3. Найдите объём одной записи в битах: длина × i.
4. Округлите до целого числа байт вверх: биты делим на 8 и берём потолок.
5. Добавьте дополнительные сведения (если они есть) — они уже в байтах.
6. Умножьте на количество записей и при необходимости переведите в Кбайты.

Для обратной задачи идите по тем же шагам назад: общий объём ÷ число записей = байт на запись; затем найдите допустимые значения параметра перебором или неравенством.

Разбор примера 1 (прямая задача)

Система выдаёт каждому участнику олимпиады идентификатор длиной 12 символов. В идентификаторе используются 26 заглавных латинских букв, 10 десятичных цифр и 2 специальных символа. Каждый символ кодируется одинаковым минимально возможным числом бит, а идентификатор — минимально возможным целым числом байт. Кроме идентификатора, для каждого участника хранится 15 байт дополнительных сведений. Сколько байт нужно для хранения данных о 500 участниках?

Шаг 1. Мощность алфавита: N = 26 + 10 + 2 = 38.

Шаг 2. 2**5 = 32 < 38, а 2**6 = 64 >= 38, значит, i = 6 бит на символ.

Шаг 3. Один идентификатор: 12 × 6 = 72 бита.

Шаг 4. 72 / 8 = 9 байт (делится нацело, округлять не нужно).

Шаг 5. Одна запись: 9 + 15 = 24 байта.

Шаг 6. 500 записей: 24 × 500 = 12 000 байт.

Ответ: 12000.

Разбор примера 2 (обратная задача)

Каждая запись системы содержит только код длиной 15 символов. Все символы кодируются одинаковым минимально возможным числом бит, а каждый код — минимальным целым числом байт. 2048 записей занимают 16 Кбайт. Какое наибольшее количество различных символов может быть в алфавите?

Шаг 1. 16 Кбайт = 16 × 1024 = 16 384 байт. На одну запись: 16 384 / 2048 = 8 байт = 64 бита.

Шаг 2. Код из 15 символов должен поместиться в 64 бита: 15 × i ≤ 64, отсюда i ≤ 4 (при i = 5 получилось бы 75 бит, то есть 10 байт — больше восьми).

Шаг 3. При i = 4 можно закодировать не более 2**4 = 16 символов.

Ответ: 16.

Обратите внимание: важно именно «8 байт на запись», а не «64 бита на запись» как точная величина. При i = 4 код занимает 60 бит, что округляется до тех же 8 байт.

Код на Python

На экзамене расчёт проще всего проверить короткой программой. Функция ceil из модуля math выполняет округление вверх, а log2 — логарифм по основанию 2. Надёжнее, впрочем, вычислять бит на символ через (N - 1).bit_length() — без вещественных чисел.

from math import ceil

def bits_per_symbol(n):
    return (n - 1).bit_length()  # наименьшее i, при котором 2**i >= n

# пример 1: прямая задача
i = bits_per_symbol(26 + 10 + 2)
id_bytes = ceil(12 * i / 8)
print((id_bytes + 15) * 500)  # 12000

# пример 2: обратная задача перебором
best = 0
for n in range(2, 5000):
    if ceil(15 * bits_per_symbol(n) / 8) * 2048 <= 16 * 1024:
        best = n
print(best)  # 16

Перебор в обратной задаче удобен тем, что не нужно аккуратно решать неравенства: программа сама проверит все варианты, а вы возьмёте наибольший или наименьший подходящий.

Частые ошибки

• Округляют общий объём, а не одну запись. 500 записей по 72 бита — это не «36 000 бит = 4500 байт», потому что каждая запись занимает целое число байт отдельно.
• Берут не тот алфавит: забывают строчные буквы или специальные символы, считают русский алфавит из 32 букв вместо 33 (если буква ё разрешена).
• Ошибаются в формуле Хартли: для N = 32 достаточно 5 бит, а не 6; для N = 33 уже нужно 6.
• Путают Кбайт и тысячу байт: в задачах ЕГЭ 1 Кбайт = 1024 байт.
• Записывают ответ в неверных единицах: если спрашивают байты, а получили Кбайты, ответ будет неверным.
• В обратной задаче берут ближайшее, а не наибольшее значение — внимательно читайте, что ищется.

Потренируйтесь

Решите несколько прямых и обратных задач: задания № 11 в банке. Перед каждой задачей проговаривайте порядок: алфавит → бит на символ → байт на запись → объём. Теория о кодировании текста, изображений и звука — в статье «Количество информации», а следующее задание экзамена — задание 12: исполнитель Редактор.