11 задание ЕГЭ информатика

Информационный объём сообщения

1 балл ≈ 3 мин уровень П

Задание 11 – посимвольное кодирование паролей, номеров, идентификаторов: найти объём памяти, размер алфавита, длину записи. 1 балл.

Формулы

Каждый символ алфавита мощности N кодируется i битами: i – наименьшее целое с $2^{i} \geq N$ .
Запись из L символов: L · i бит. Если «каждая запись занимает целое минимальное число байт» – округляй вверх до байт: $⌈ L \cdot i / 8 ⌉$ .
Объём для K записей = K × (байт на запись) (+ доп. сведения, если есть).
Обратная задача (найти N или L): перебирай i от 1 вверх и проверяй условие.

Шаблон на Python

from math import ceil, log2

L, K = 15, 500
N = 36                       # 26 латинских букв + 10 цифр
i = ceil(log2(N))            # бит на символ
per = ceil(L * i / 8)        # байт на одну запись
print(i, per, per * K)       # 6, 12, 6000

Разобранный пример. Номер из 15 символов: заглавные латинские буквы и цифры (36 символов). i = 6 бит (2⁶ = 64 ≥ 36). Один номер: 15 · 6 = 90 бит, 90/8 = 11,25 → 12 байт. 500 номеров: 6000 байт.

Обратная задача. «Для хранения K записей требуется не менее X байт, найти минимальную мощность алфавита»: перебери i, найди наименьшее i, при котором K · ceil(L · i / 8) ≥ X, затем минимальная мощность для такого i: $2^{i - 1} + 1$ .

Ловушки: округлять до байт нужно каждую запись отдельно, а не весь объём; при подсчёте алфавита не забудь цифры, спецсимволы, строчные и заглавные; 1 Кбайт = 1024 байт, 1 Гбайт = 2³⁰ байт.

На экзамене

ceil – округление вверх, его используем дважды: для бит на символ и для байт на запись.
Минимальная мощность алфавита для i бит – 2ⁱ⁻¹ + 1, максимальная – 2ⁱ.
В обратных задачах перебор в Python надёжнее алгебры.

Разобранные задания 11 из открытого банка ФИПИ

Пример 1 · код ФИПИ 880C5C

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 246 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 703 569 серийных номеров доступно не более 77 Мбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Показать ответ и решение

Ответ: 8

На номер: $⌊ 77 \cdot 2^{20} / 703569 ⌋ = 114$ байт = 912 бит; на символ $⌊ 912 / 246 ⌋ = 3$ бита → алфавит до 8 символов.

Пример 2 · код ФИПИ 5637DD

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 23 символов.
В качестве символов используются буквы из 12-символьного алфавита. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование паролей, все символы кодируются одинаковым и минимально возможным количеством бит. Кроме собственно пароля в системе хранятся дополнительные сведения о каждом пользователе, для чего выделено целое число байт; это число одно и то же для всех пользователей.

Для хранения сведений о 297 пользователях потребовалось 13 068 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе?

В ответе запишите только целое число – количество байт.

Показать ответ и решение

Ответ: 32

12 символов → 4 бита; пароль $23 \cdot 4 = 92$ бита → 12 байт.

На пользователя $13 068 / 297 = 44$ байта, доп. сведения $44 - 12 = 32$ .

Пример 3 · код ФИПИ 25ACB1

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 7 символов и содержащий только десятичные цифры и символы из 26-символьного набора прописных латинских букв. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.

Для хранения сведений о 30 пользователях потребовалось 750 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число $-$ количество байт.

Показать ответ и решение

Ответ: 19

36 символов → 6 бит; $7 \cdot 6 = 42$ бита → 6 байт на пароль. На пользователя $750 / 30 = 25$ байт.

Дополнительные сведения: $25 - 6 = 19$ байт.

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

Сколько баллов даёт задание 11 ЕГЭ по информатике?

Максимум – 1 первичный балл. Норма времени на экзамене – около 3 мин. Уровень сложности – П.

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

Как подготовиться к заданию 11?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.