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

Введение в задание 11

Задание 11 ЕГЭ по информатике проверяет умение определять объём памяти, необходимый для хранения паролей, идентификаторов, серийных номеров и других символьных последовательностей.

В большинстве задач используется равномерное кодирование: каждый символ кодируется одинаковым и минимально возможным количеством бит.

Как устроена задача

Обычно решение состоит из трёх основных действий:

1. Определить количество бит на один символ.
2. Найти объём одного пароля.
3. Найти объём всех паролей вместе с дополнительными сведениями.

Что такое алфавит

Рассмотрим шестизначный пароль. Предположим, что в нём можно использовать около 100 разных символов:

• цифры от 0 до 9;
• заглавные и строчные латинские буквы;
• знаки препинания;
• специальные символы клавиатуры.

Набор всех символов, которые разрешено использовать, называется алфавитом, а количество символов в нём — мощностью алфавита.

В нашем примере:

$$N = 100$$

где $N$ — мощность алфавита.

Сколько бит требуется на один символ

Каждый символ пароля кодируется одинаковым и минимально возможным количеством бит.

Чтобы определить это количество, используется уже знакомая по заданию 7 формула:

$$N = 2^i$$

Для алфавита из 100 символов нужно найти минимальное значение $i$, при котором выполняется условие:

$$2^i \geq 100$$

Сравним ближайшие степени двойки:

Получаем:

$$2^6 < 100 \leq 2^7$$

Следовательно, для кодирования одного символа требуется:

$$i = 7\text{ бит}$$

Важно: мы определяем не количество символов в одном бите, а количество бит, необходимое для кодирования одного символа.

Наглядная схема кодирования

Алфавит из 100 символов

↓ ищем ближайшую подходящую степень двойки

$2^7 = 128$ возможных кодов

↓ значит

Один символ занимает 7 бит

↓ пароль состоит из 6 символов

$6 \cdot 7 = 42$ бита

↓ переводим в байты

$42 : 8 = 5{,}25$ байта

↓ округляем вверх

Один пароль занимает 6 байт

Объём одного пароля

Объём пароля до округления вычисляется по формуле:

$$V = L \cdot i$$

В нашем примере пароль состоит из шести символов, каждый из которых занимает 7 бит:

$$V = 6 \cdot 7 = 42\text{ бита}$$

Таким образом, непосредственно для кодирования символов пароля требуется 42 бита.

Что означает «целое количество байт»

В условии задания часто встречается следующая фраза:

В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое количество байт.

Разберём эту формулировку по частям.

Сначала переведём 42 бита в байты:

$$\frac{42}{8} = 5{,}25\text{ байта}$$

Выделить 5,25 байта невозможно, поэтому результат необходимо округлить вверх:

$$V_{\text{пароля}} = 6\text{ байт}$$

Почему округляем вверх

Проверим, хватит ли пяти байтов:

$$5 \cdot 8 = 40\text{ бит}$$

Пяти байтов недостаточно, потому что пароль занимает 42 бита.

Проверим шесть байтов:

$$6 \cdot 8 = 48\text{ бит}$$

Шести байтов достаточно.

Следовательно, минимальный целый объём памяти равен:

$$V_{\text{пароля}} = 6\text{ байт}$$

Из 48 выделенных бит:

• 42 бита используются для кодирования символов пароля;
• 6 бит остаются неиспользованными.

Два разных округления

В задании встречаются два разных этапа определения целого значения.

Для нашего примера:

$$100 \leq 2^7 \Rightarrow i = 7\text{ бит}$$

$$V = 6 \cdot 7 = 42\text{ бита}$$

$$V_{\text{пароля}} = \frac{42}{8} = 5{,}25\text{ байта}$$

После округления вверх:

$$V_{\text{пароля}} = 6\text{ байт}$$

Что может попасться в задании

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

Основные величины связаны следующей схемой:

Шаг 1. Определить мощность алфавита

Если в условии перечислены разные группы символов, необходимо сложить их количество.

Например, если используются:

• 10 десятичных цифр;
• 26 латинских букв;
• 450 специальных символов,

то мощность алфавита равна:

$$N = 10 + 26 + 450 = 486$$

Если сказано, что используются прописные и строчные латинские буквы, их необходимо считать отдельно:

$$N = 26 + 26 = 52$$

Важно. Фраза «без учёта регистра» означает, что прописные и строчные буквы не различаются. В таком случае латинских букв будет 26, а не 52.

Шаг 2. Найти количество бит на один символ

Все символы кодируются одинаковым и минимально возможным количеством бит. Поэтому нужно найти наименьшее целое значение $i$, для которого выполняется условие:

$$2^i \geq N$$

Например, если в алфавите 52 символа:

$$2^5 = 32 < 52$$

$$2^6 = 64 \geq 52$$

Следовательно:

$$i = 6\text{ бит}$$

Для быстрого решения полезно помнить степени двойки:

Шаг 3. Найти объём одного пароля в битах

Если пароль состоит из $L$ символов, а для кодирования одного символа используется $i$ бит, то информационный объём пароля равен:

$$V_{\text{пароля}} = L \cdot i$$

Например, для пароля длиной 10 символов при $i = 6$:

$$V_{\text{пароля}} = 10 \cdot 6 = 60\text{ бит}$$

Шаг 4. Перевести объём одной записи в байты

В базе данных для хранения каждого пароля отводится одинаковое и минимально возможное целое количество байт.

Поэтому полученное количество бит необходимо разделить на 8 и округлить вверх:

$$b = \left\lceil \frac{L \cdot i}{8} \right\rceil$$

Для пароля объёмом 60 бит получаем:

$$b = \left\lceil \frac{60}{8} \right\rceil = \left\lceil 7{,}5 \right\rceil = 8\text{ байт}$$

Следовательно, на один пароль необходимо выделить 8 байт.

Округлять нужно именно вверх. Если округлить $7{,}5$ до 7 байт, для хранения пароля не хватит памяти.

Шаг 5. Учесть количество записей

Если в базе хранится $K$ паролей или серийных номеров, общий объём памяти равен:

$$V = K \cdot b$$

Полная формула имеет вид:

$$V = K \cdot \left\lceil \frac{L \cdot i}{8} \right\rceil$$

Если ответ необходимо получить в Кбайтах, используем перевод:

$$V_{\text{Кбайт}} = \frac{V_{\text{байт}}}{1024}$$

Основные прототипы задания

Прототип 1. Найти общий объём памяти

В условии обычно известны:

• мощность алфавита $N$;
• длина пароля $L$;
• количество записей $K$.

Требуется найти общий объём памяти $V$.

Порядок решения:

1. Найти количество бит на символ $i$ из условия $2^i \geq N$.
2. Найти объём одного пароля в битах: $L \cdot i$.
3. Разделить полученный объём на 8.
4. Округлить количество байт вверх.
5. Умножить размер одной записи на количество записей.
6. При необходимости перевести результат в Кбайты.

Схема решения:

$$N \longrightarrow i \longrightarrow L \cdot i \longrightarrow \left\lceil \frac{L \cdot i}{8} \right\rceil \longrightarrow K \cdot b$$

Прототип 2. Найти длину пароля или серийного номера

В условии обычно известны:

• мощность алфавита $N$;
• количество записей $K$;
• ограничение на общий объём памяти $V$.

Требуется найти длину одной записи $L$.

Порядок решения:

1. Найти количество бит на символ $i$.
2. Перевести общий объём памяти в байты.
3. Определить допустимое количество байт на одну запись.
4. Использовать формулу:

$$b = \left\lceil \frac{L \cdot i}{8} \right\rceil$$

1. Найти подходящее целое значение $L$.
2. Проверить найденную длину и соседнее значение.

При решении необходимо внимательно прочитать формулировку ограничения:

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

Из-за округления до целого количества байт найденную длину обязательно нужно проверить подстановкой. Желательно также проверить соседнее значение.

Прототип 3. Найти мощность алфавита

В условии обычно известны:

• длина серийного номера $L$;
• количество записей $K$;
• общий объём памяти $V$.

Требуется определить мощность алфавита $N$.

Порядок решения:

1. Перевести общий объём памяти в байты.
2. Определить количество байт, выделяемое на одну запись.
3. Перевести размер одной записи в биты.
4. Определить количество бит на один символ $i$.
5. По найденному значению $i$ определить мощность алфавита $N$.

Главная сложность этого прототипа заключается в последнем действии.

Почему нельзя всегда использовать формулу $N = 2^i$

Формула

$$N = 2^i$$

показывает максимальное количество символов, которое можно закодировать с помощью $i$ бит.

Однако фактическая мощность алфавита может быть меньше этого значения.

Если на кодирование одного символа требуется 4 бита, то:

$$2^3 < N \leq 2^4$$

$$8 < N \leq 16$$

Следовательно, алфавит может содержать от 9 до 16 символов.

Если требуется найти максимальную мощность алфавита, используется формула:

$$N_{\max} = 2^i$$

Если требуется найти минимальную мощность алфавита, при которой уже необходимо $i$ бит, используется формула:

$$N_{\min} = 2^{i-1} + 1$$

Например, если для кодирования одного символа требуется 4 бита:

$$N_{\max} = 2^4 = 16$$

$$N_{\min} = 2^3 + 1 = 9$$

Частая ошибка: получить $i = 4$ и сразу записать в ответе 16. Это правильно только тогда, когда требуется максимальная мощность алфавита. Если требуется минимальная мощность, ответом будет 9.

Таблица возможных границ:

Как определить размер одной записи по общему объёму

Пусть на хранение $K$ записей отведено $V$ байт.

Если сказано, что общий объём составляет не более $V$ байт, максимальный размер одной записи равен:

$$b_{\max} = \left\lfloor \frac{V}{K} \right\rfloor$$

Если сказано, что общий объём составляет не менее $V$ байт, минимальный размер одной записи равен:

$$b_{\min} = \left\lceil \frac{V}{K} \right\rceil$$

Если сказано, что общий объём составляет более $V$ байт, равенство не подходит. Необходимо найти первое целое количество байт, при котором:

$$K \cdot b > V$$

В таком случае:

$$b_{\min} = \left\lfloor \frac{V}{K} \right\rfloor + 1$$

После этого нужно найти такое значение $i$ или $L$, при котором размер одной записи удовлетворяет условию:

$$b = \left\lceil \frac{L \cdot i}{8} \right\rceil$$

Из-за округления байтов вверх найденное значение нужно проверить подстановкой.

Универсальная схема решения

1. Выписать известные величины: $N$, $i$, $L$, $K$ и $V$.
2. Перевести общий объём памяти в байты.
3. Если известна мощность алфавита, найти минимальное $i$ из условия $2^i \geq N$.
4. Если известен общий объём, определить допустимое количество байт на одну запись.
5. Использовать формулу:

$$b = \left\lceil \frac{L \cdot i}{8} \right\rceil$$

1. Найти неизвестную величину.
2. Проверить полученный результат и соседнее целое значение.
3. Если требуется мощность алфавита, определить, какую именно границу спрашивают.

Разбор заданий с реального ЕГЭ

Решение задания 11 с помощью Python

Некоторые задачи № 11 можно решить перебором. Программа последовательно проверяет возможные значения длины или мощности алфавита и выводит первое значение, которое удовлетворяет условию.

Код для нахождения минимальной длины

from math import *

for dlina in range(1, 1000):
    alf = 10 + 62
    i = ceil(log2(alf))
    V = ceil(dlina * i / 8)

    if V * 5_895_222 > 23 * 1024 * 1024:
        print(dlina)
        break

Этот код перебирает возможную длину пароля или серийного номера.

Как работает программа

1. Перебирается возможная длина:

for dlina in range(1, 1000):

Сначала программа проверит длину 1, затем 2, 3 и так далее.

1. Находится мощность алфавита:

alf = 10 + 62

В данном случае алфавит состоит из двух групп: 10 и 62 символов.

$$N = 10 + 62 = 72$$

1. Определяется минимальное количество бит на один символ:

i = ceil(log2(alf))

Функция log2(alf) вычисляет, в какую степень нужно возвести 2, чтобы получить мощность алфавита. Функция ceil() округляет результат вверх.

Таким образом, эта строка соответствует условию:

$$2^i \geq N$$

1. Находится размер одной записи в байтах:

V = ceil(dlina * i / 8)

Сначала длина умножается на количество бит на символ. Затем результат делится на 8 и округляется вверх до целого количества байт:

$$V = \left\lceil \frac{L \cdot i}{8} \right\rceil$$

1. Проверяется общий объём памяти:

if V * 5_895_222 > 23 * 1024 * 1024:

Размер одной записи умножается на количество записей. Полученное значение сравнивается с 23 Мбайт.

1. Выводится первая подходящая длина:

print(dlina)
break

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

Команда break останавливает перебор после нахождения ответа. Без неё программа выведет не только минимальную длину, но и все последующие подходящие значения.

Код для нахождения минимальной мощности алфавита

from math import *

for x in range(1, 1000):
    alf = x
    dlina = 172
    bit = ceil(log2(alf))
    V = ceil(dlina * bit / 8)

    if 356_984 * V >= 54 * 1024 ** 2:
        print(x)
        break

Этот код перебирает возможную мощность алфавита.

Как работает программа

1. Перебирается возможная мощность алфавита:

for x in range(1, 1000):

Программа последовательно проверяет алфавиты мощностью 1, 2, 3 и так далее.

1. Текущее значение записывается в переменную alf:

alf = x

1. Указывается известная длина номера:

dlina = 172

1. Находится минимальное количество бит на один символ:

bit = ceil(log2(alf))

1. Вычисляется размер одного номера в целых байтах:

V = ceil(dlina * bit / 8)

1. Проверяется общий объём всех номеров:

if 356_984 * V >= 54 * 1024 ** 2:

Левая часть — фактический объём всех записей. Правая часть — 54 Мбайт, переведённые в байты.

1. Выводится первая подходящая мощность алфавита:

print(x)
break

Первое найденное значение является минимальной мощностью алфавита.

Такой перебор особенно удобен в задачах на минимальную мощность алфавита. Программа проверяет сами значения $N$, поэтому не возникает ошибки, когда вместо минимальной мощности записывают максимальное значение $2^i$.

Чем отличаются два кода

Общий принцип у обоих решений одинаковый:

1. Перебрать возможное значение.
2. Найти количество бит на символ.
3. Найти целое количество байт на одну запись.
4. Вычислить общий объём памяти.
5. Проверить условие.
6. Вывести первое подходящее значение и остановить перебор.