ЕГЭ · Информатика · задание 111 балл · ≈6 мин

Задание 11 ЕГЭ: Идентификаторы: посимвольное кодирование и байты

При регистрации каждому объекту — сотруднику, билету, читателю — выдают идентификатор из n символов, взятых из алфавита мощности K. На один символ отводят минимальное ЦЕЛОЕ число бит i, при котором 2^i не меньше K: для 26 букв это 5 бит (32 покрывает 26), для 64 символов — 6 бит. Идентификатор целиком кодируется минимальным целым числом байт: n·i бит округляют вверх до кратного восьми. Часто на каждый объект добавляют p байт служебных данных (контрольная сумма, отдел, срок действия), и вопрос звучит так: сколько байт нужно для m объектов? Типовые потери: округляют биты на символ до ближайшего вместо округления вверх, округляют байты вниз, забывают служебные байты или умножают на m только идентификатор без прибавки.

Все задания Информатика

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

Посимвольное кодирование. Это задание с коротким ответом, который проверяется автоматически. Одна арифметическая ошибка — ноль баллов, поэтому скорость и аккуратность здесь важнее гениальности.

Формулы к заданию

i = ⌈ lo g_{2} K ⌉

Бит на символ: минимальное целое i, при котором 2^i не меньше K

L = ⌈ n \cdot i /8 ⌉

Байт на один идентификатор: n символов по i бит, округление вверх

S = m \cdot (L + p)

Всего байт: m идентификаторов плюс p байт служебных данных на каждый

Разбор типовых задач

Пример 1

На пропусках посетителей печатается идентификатор из 9 символов, каждый символ — заглавная латинская буква (26 вариантов). Под символ отводят минимально возможное целое число бит, а идентификатор кодируют минимально возможным целым числом байт; дополнительно каждый пропуск хранит 12 байт служебных данных. Сколько байт нужно для хранения данных о 200 пропусках?

Решение по шагам

Бит на символ: 2 в четвёртой — 16, этого мало; 2 в пятой — 32, уже покрывает 26. Значит i = 5.
$2^{5} = 32 \geq 26$
Бит на идентификатор: 9 символов по 5 бит.
$9 \cdot 5 = 45$
Округляем вверх до целого байта: 45 : 8 = 5,625 — нужно 6 байт.
$⌈ 45/8 ⌉ = 6$
На один пропуск со служебными данными: 6 + 12 = 18 байт.
На все 200 пропусков: 200 · 18.
$200 \cdot 18 = 3600$

Ответ: 3600

Пример 2

Идентификатор сотрудника состоит из 12 символов, алфавит содержит 64 символа (латиница обоих регистров, цифры и служебные знаки). Под символ отводят минимально возможное целое число бит, идентификатор кодируют минимально возможным целым числом байт, и на каждого сотрудника добавляют 7 байт сведений об отделе. Сколько байт займут данные о 150 сотрудниках?

Решение по шагам

Алфавит 64 — точная степень двойки, значит на символ ровно 6 бит, без округления.
$2^{6} = 64$
Бит на идентификатор: 12 · 6 = 72 бита — делится на 8 нацело, округление ничего не добавляет.
$12 \cdot 6 = 72$
Байт на идентификатор: 72 : 8 = 9.
С прибавкой на отдел: 9 + 7 = 16 байт на сотрудника.
На 150 сотрудников: 150 · 16.
$150 \cdot 16 = 2400$

Ответ: 2400

Тренажёр задания (числа меняются)

Клавиши 1–9 выбирают вариант, Enter — «Проверить»

Идентификатор сотрудника — 10 символов из алфавита мощностью 256 символов, на каждый символ отводится ровно 8 бит. Дополнительно на каждого сотрудника хранится 16 байт сведений. Сколько байт нужно для хранения данных о 265 сотрудниках?

Идентификатор состоит из 22 символов, на каждый отводится 7 бит; служебных данных нет. Сколько БИТ потребуется для хранения 142 таких идентификаторов?

В базе А на каждого из 230 сотрудников хранится идентификатор и 13 байт сведений, в базе Б — идентификатор той же длины и 8 байт сведений. На сколько байт база А больше базы Б?

Идентификатор из 18 символов кодируется по 5 бит на символ; на каждого из 38 владельцев добавляется 13 байт контроля. Сколько всего БИТ займут данные?

Идентификатор сотрудника — 22 символов из алфавита мощностью 256 символов, на каждый символ отводится ровно 8 бит. Дополнительно на каждого сотрудника хранится 14 байт сведений. Сколько байт нужно для хранения данных о 231 сотрудниках?

Идентификатор состоит из 13 символов, на каждый отводится 5 бит; служебных данных нет. Сколько БИТ потребуется для хранения 95 таких идентификаторов?

В базе А на каждого из 255 сотрудников хранится идентификатор и 20 байт сведений, в базе Б — идентификатор той же длины и 4 байт сведений. На сколько байт база А больше базы Б?

Идентификатор из 20 символов кодируется по 5 бит на символ; на каждого из 52 владельцев добавляется 8 байт контроля. Сколько всего БИТ займут данные?

Типичные ошибки

Берут i = log2 K без округления вверх: для алфавита из 26 символов верно 5 бит (32 покрывает 26), а не «примерно 4,7 бита».
Округляют число байт вниз или к ближайшему: идентификатор занимает минимальное целое число байт, только с округлением ВВЕРХ.
Забывают служебные байты или умножают на число объектов только идентификатор: прибавка p входит в размер на КАЖДЫЙ объект.

Стратегия на экзамене. Иди по цепочке: сначала биты на символ (минимальная степень двойки, покрывающая алфавит), затем биты на идентификатор (n умножить на i), затем байты на идентификатор (округление вверх до кратного восьми), затем плюс служебные байты и умножение на число объектов. Если алфавит — точная степень двойки (32, 64, 256), округление на первом шаге исчезает, а при 256 символах идентификатор из n символов занимает ровно n байт. Проверяй, в каких единицах спрошен ответ: биты и байты отличаются в 8 раз.

Повторить теорию по информатике

Разбор задания опирается на формулы и приёмы — если тема вспоминается с трудом, сначала пробегите уроки:

Формат задания 11 на экзамене

Балл за задание: 1. Ориентир по времени: ≈6 минут вместе с оформлением решения. Проверяемая тема: посимвольное кодирование. На тренировке лимитов нет — сначала точность, скорость придёт после 10–15 решённых задач. Планируйте экзамен так, чтобы не застревать: если решение не идёт — зафиксируйте промежуточный результат, переходите дальше и возвращайтесь в конце, потому что остальные задания дадут больше суммарных баллов.

Частые вопросы про задание 11

Сколько бит нужно на символ алфавита из K символов?

Минимальное целое i, при котором 2^i не меньше K: для 26 букв это 5 бит, для 64 символов — 6, для 256 — 8.

Как перевести биты идентификатора в байты?

Раздели n·i на 8 и округли ВВЕРХ до целого: 45 бит — это 6 байт, а 72 бита — ровно 9 байт.

Зачем в задаче про идентификаторы дополнительные байты?

Кроме самого идентификатора на каждый объект хранят служебные данные (контроль, отдел, срок): их прибавляют к байтам идентификатора и только потом умножают на число объектов.