Объём памяти для ЕГЭ по информатике (Задание 11)

Задания: N11.Объем памяти

1. Основные понятия

Задание 10 ЕГЭ по информатике проверяет умение определять объём памяти, необходимый для хранения паролей, идентификаторов, кодов и других текстовых данных. Ключевая особенность это использование равномерного кодирования, при котором каждый символ кодируется одинаковым количеством бит.

Типичные объекты в задачах:

• Пароли
• Идентификаторы
• Коды доступа
• Номера документов
• Шифры

2. Алгоритм решения задач задания 10

Пошаговый алгоритм

Шаг 1: Определяем количество символов в алфавите

Обозначим это количество за N.

Важно: Алфавит это это символы, которыми мы можем записать пароль, идентификатор и т.д.

Примеры алфавитов:

• Десятичные цифры: 0–9 → N = 10
• Латинские буквы (заглавные): A–Z → N = 26
• Латинские буквы (строчные): a–z → N = 26
• Латинские буквы (все): A–Z, a–z → N = 52
• Русские буквы (заглавные): А–Я → N = 33
• Комбинация цифр и букв: нужно сложить количества

Шаг 2: Определяем количество бит на символ

Находим минимальное количество бит i из соотношения:

$2^i \geq N$

где i это минимальная подходящая натуральная степень.

Важно:

• Кодирование в этих задачах равномерное, то есть предполагает одинаковое количество бит на каждый символ
• Если $2^i = N$, то i это точное значение
• Если $2^i > N$, то i это минимальное значение, при котором можно закодировать все символы

Шаг 3: Вычисляем размер пароля/идентификатора в битах

$I_{\text{один}} = L \times i$

где:

• I это объём информации одного пароля/идентификатора (в битах)
• L это длина пароля/идентификатора (количество символов)
• i это количество бит на символ

Пример: Пароль длиной 8 символов, алфавит из 26 букв:

• i = 5 бит ($2^5 = 32 \geq 26$)
• $I = 8 \times 5 = 40 \text{ бит}$

Шаг 4: Переводим размер в байты

Важно: Округление дробного числа всегда будет идти наверх (в большую сторону).

$I_{\text{байт}} = \left\lceil \frac{I_{\text{бит}}}{8} \right\rceil$

где $\left\lceil x \right\rceil$ округление вверх (ceiling function).

Примеры: 40 бит это 5 байт Правило: Если при делении на 8 получается дробное число, всегда округляем вверх до целого байта.

Шаг 5: Вычисляем объём для всех объектов

$I_{\text{все}} = I_{\text{один}} \times K$

где:

• I_все это объём памяти для всех паролей/идентификаторов (в байтах)
• I_один это объём одного пароля/идентификатора (в байтах)
• K это количество паролей/идентификаторов

Шаг 6: Переводим в требуемые единицы

Если нужно перевести в Кбайт, Мбайт и т.д.:

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

$I_{\text{МБ}} = \frac{I_{\text{КБ}}}{1024}$

Важно: 1 КБ = 1024 байт (не 1000!)

3. Разбор типичной задачи

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

Условие:

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 60 символов и содержащий только десятичные цифры и символы из 250-символьного специального алфавита.

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

Определите объём памяти (в Кбайт), необходимый для хранения 65536 идентификаторов. В ответе запишите только целое число это количество Кбайт.

Решение по алгоритму:

Шаг 1: Определяем количество символов в алфавите

Алфавит состоит из:

• Десятичные цифры: 0–9 → 10 символов
• Специальный алфавит: 250 символов

$N = 10 + 250 = 260 \text{ символов}$

Шаг 2: Определяем количество бит на символ

Находим минимальное i такое, что $2^i \geq 260$:

$2^7 = 128 < 260$ $2^8 = 256 < 260$ $2^9 = 512 \geq 260$

Ответ: i = 9 бит на символ

Шаг 3: Вычисляем размер одного идентификатора в битах

Длина идентификатора: L = 60 символов

$I_{\text{один (бит)}} = L \times i = 60 \times 9 = 540 \text{ бит}$

Шаг 4: Переводим размер в байты

$I_{\text{один (байт)}} = \left\lceil \frac{540}{8} \right\rceil = \left\lceil 67,5 \right\rceil = 68 \text{ байт}$

Проверка: 68 × 8 = 544 бит (достаточно для 540 бит)

Шаг 5: Вычисляем объём для всех идентификаторов

Количество идентификаторов: K = 65536

$I_{\text{все (байт)}} = I_{\text{один}} \times K = 68 \times 65536 = 4456448 \text{ байт}$

Шаг 6: Переводим в Кбайт

$I_{\text{КБ}} = \frac{4456448}{1024} = 4352 \text{ Кбайт}$

Ответ: 4352 Кбайт

4. Типичные задачи и их особенности

4.1. Задачи с паролями

Особенности:

• Обычно задаётся длина пароля
• Алфавит может включать цифры, буквы, специальные символы
• Нужно найти объём для одного или нескольких паролей

Пример: Пароль состоит из 12 символов, использует цифры 0–9 и заглавные латинские буквы A–Z. Сколько байт нужно для хранения одного пароля?

Решение:

• N = 10 + 26 = 36 символов
• $2^5 = 32 < 36$, $2^6 = 64 \geq 36$ → i = 6 бит
• $I = 12 \times 6 = 72 \text{ бит}$
• $I = \left\lceil \frac{72}{8} \right\rceil = 9 \text{ байт}$

4.2. Задачи с идентификаторами

Особенности:

• Могут быть длинными (50–100 символов)
• Алфавит может быть большим (200–300 символов)
• Обычно нужно найти объём для большого количества идентификаторов

Пример: Идентификатор длиной 80 символов использует алфавит из 180 символов. Сколько Кбайт нужно для хранения 8192 идентификаторов?

Решение:

• N = 180 символов
• $2^7 = 128 < 180$, $2^8 = 256 \geq 180$ → i = 8 бит
• $I_{\text{один}} = 80 \times 8 = 640 \text{ бит} = 80 \text{ байт}$
• $I_{\text{все}} = 80 \times 8192 = 655360 \text{ байт} = 640 \text{ Кбайт}$

4.3. Задачи с кодами доступа

Особенности:

• Могут использовать только цифры
• Длина обычно небольшая (4–8 символов)
• Нужно найти объём для одного или нескольких кодов

Пример: Код доступа состоит из 6 цифр. Сколько байт нужно для хранения одного кода?

Решение:

• N = 10 символов (цифры 0–9)
• $2^3 = 8 < 10$, $2^4 = 16 \geq 10$ → i = 4 бита
• $I = 6 \times 4 = 24 \text{ бит}$
• $I = \left\lceil \frac{24}{8} \right\rceil = 3 \text{ байт}$

5. Типичные алфавиты и их размеры

6. Степени двойки для быстрого решения

Правило: Если N символов в алфавите, находим минимальное i такое, что $2^i \geq N$.

7. Типичные ошибки и как их избежать

Ошибка 1: Неправильное определение размера алфавита

Проблема: Забывают сложить все типы символов или считают неправильно.

Как избежать:

• Внимательно читать условие
• Выписывать все типы символов отдельно
• Складывать количества: N = N₁ + N₂ + ...

Пример ошибки: "Цифры и буквы A–Z" → считают только 26, забывая про 10 цифр.

Ошибка 2: Неправильное определение количества бит

Проблема: Берут меньшее значение степени двойки.

Как избежать:

• Всегда проверять: $2^i \geq N$
• Если $2^i < N$, нужно взять $2^{i+1}$

Пример ошибки: N = 20, берут $2^4 = 16$ (недостаточно!), нужно $2^5 = 32$.

Ошибка 3: Неправильное округление в байты

Проблема: Округляют вниз или используют обычное округление.

Как избежать:

• Всегда округлять вверх при переводе бит в байты
• Использовать формулу: $\left\lceil \frac{\text{бит}}{8} \right\rceil$

Пример ошибки: 41 бит → 5 байт (неправильно!), правильно: 6 байт.

Ошибка 4: Неправильный перевод единиц измерения

Проблема: Используют 1000 вместо 1024.

Как избежать:

• Запомнить: 1 КБ = 1024 байт (не 1000!)
• 1 МБ = 1024 КБ = 1048576 байт

Ошибка 5: Забывают про "минимально возможное"

Проблема: Не учитывают требование минимальности при выборе количества бит.

Как избежать:

• Всегда искать минимальное i такое, что $2^i \geq N$
• Не брать большее значение "с запасом"

8. Алгоритм решения (краткая версия)

1. Определить N это количество символов в алфавите
2. Найти i это минимальное количество бит: $2^i \geq N$
3. Вычислить I_бит это размер в битах: $I = L \times i$
4. Перевести в байты это округлить вверх: $I_{\text{байт}} = \left\lceil \frac{I_{\text{бит}}}{8} \right\rceil$
5. Умножить на количество объектов (если нужно)
6. Перевести в требуемые единицы (КБ, МБ и т.д.)

9. Дополнительные примеры

Пример 1: Пароль с цифрами и буквами

Условие: Пароль состоит из 10 символов, использует цифры 0–9, заглавные латинские буквы A–Z и строчные латинские буквы a–z. Сколько байт нужно для хранения одного пароля?

Решение:

1. N = 10 + 26 + 26 = 62 символа
2. $2^5 = 32 < 62$, $2^6 = 64 \geq 62$ → i = 6 бит
3. $I = 10 \times 6 = 60 \text{ бит}$
4. $I = \left\lceil \frac{60}{8} \right\rceil = \left\lceil 7,5 \right\rceil = 8 \text{ байт}$

Ответ: 8 байт

Пример 2: Идентификатор с большим алфавитом

Условие: Идентификатор длиной 50 символов использует алфавит из 200 символов. Сколько Кбайт нужно для хранения 4096 идентификаторов?

Решение:

1. N = 200 символов
2. $2^7 = 128 < 200$, $2^8 = 256 \geq 200$ → i = 8 бит
3. $I_{\text{один}} = 50 \times 8 = 400 \text{ бит} = 50 \text{ байт}$
4. $I_{\text{все}} = 50 \times 4096 = 204800 \text{ байт}$
5. $I_{\text{КБ}} = \frac{204800}{1024} = 200 \text{ Кбайт}$

Ответ: 200 Кбайт

Пример 3: Код из только цифр

Условие: Код доступа состоит из 8 цифр. Сколько байт нужно для хранения 1000 таких кодов?

Решение:

1. N = 10 символов (цифры 0–9)
2. $2^3 = 8 < 10$, $2^4 = 16 \geq 10$ → i = 4 бита
3. $I_{\text{один}} = 8 \times 4 = 32 \text{ бит} = 4 \text{ байт}$
4. $I_{\text{все}} = 4 \times 1000 = 4000 \text{ байт}$

Ответ: 4000 байт

10. Типичные формулировки в ЕГЭ

Составлено: Лилия С.
Источники: КИМ ЕГЭ 2026, открытый банк ФИПИ, спецификация ЕГЭ по информатике, яндекс учебник

Удачи на экзамене! 🎓