Как решать задание 11 ЕГЭ по информатике — кодирование и длина сообщений
Разбор задания 11 ЕГЭ по информатике: кодирование информации, формула ceil(log2(N)), разные алфавиты в одном номере, округление до байта. Разборы задач.
О чём задание
Задание 11 — про кодирование информации и подсчёт длины сообщения. По сути, это про одну формулу и пару арифметических операций, но именно здесь теряют баллы из-за невнимательности: забыли округлить, перепутали биты и байты, сложили вместо того чтобы умножить.
Задание базового уровня, стоит 1 первичный балл. Всего в экзамене 27 заданий на 235 минут, 29 первичных баллов (задания 1-25 — по 1 баллу, 26-27 — по 2 балла). Общий список изменений КЕГЭ смотри в разборе новшеств 2026 года.
Базовая формула
Ключевая идея: для кодирования N различных значений нужно минимум k бит, где:
$$2^k \ge N$$
То есть:
$$k = \lceil \log_2 N \rceil$$
Квадратные скобки сверху — это округление вверх (ceil). Разбираем на пальцах: один бит даёт 2 комбинации (0 и 1), два бита — 4 (00, 01, 10, 11), три бита — 8, и так далее. Количество возможных кодов удваивается с каждым добавленным битом.
Таблица базовых значений
| N (значений) | 2^k ≥ N | k (бит) |
|---|---|---|
| 2 | 2^1 = 2 | 1 |
| 4 | 2^2 = 4 | 2 |
| 5 | 2^3 = 8 | 3 |
| 8 | 2^3 = 8 | 3 |
| 10 | 2^4 = 16 | 4 |
| 16 | 2^4 = 16 | 4 |
| 26 | 2^5 = 32 | 5 |
| 30 | 2^5 = 32 | 5 |
| 33 | 2^6 = 64 | 6 |
| 64 | 2^6 = 64 | 6 |
| 100 | 2^7 = 128 | 7 |
| 128 | 2^7 = 128 | 7 |
| 256 | 2^8 = 256 | 8 |
| 1000 | 2^10 = 1024 | 10 |
Эту таблицу полезно держать в голове — на экзамене времени тратить на log2 не захочется. Особенно важны строчки с 10 (цифры), 26 (латинский алфавит), 33 (русский без ё), 32 (русский с упрощениями).
Почему именно ceil
Коды фиксированной длины не могут иметь «дробное» количество бит. Если у тебя 5 значений, 2 битов мало (кодирует только 4), а 3 бита достаточно (кодирует 8, из которых 3 останутся неиспользованными). Отсюда правило: берём минимальное целое k, при котором 2^k ≥ N.
Два типа номеров
В задании 11 чаще всего встречаются задачи про идентификаторы: автомобильные номера, табельные номера сотрудников, артикулы товаров. Номер состоит из нескольких разрядов, и каждый разряд — из своего «алфавита».
Один алфавит
Самый простой случай: номер длины L, каждый символ — из алфавита мощности M. Для одного символа нужно ceil(log2(M)) бит. Длина всего кода — L · ceil(log2(M)) бит.
Разные алфавиты
Сложнее: в номере есть, например, 3 буквы (26 вариантов) и 4 цифры (10 вариантов). Тогда:
- буквы: ceil(log2(26)) = 5 бит на символ, всего 3 · 5 = 15 бит
- цифры: ceil(log2(10)) = 4 бита на символ, всего 4 · 4 = 16 бит
- один номер: 15 + 16 = 31 бит
Важно: для каждой группы считается своя длина кода, потом складывается. Нельзя брать «среднее» или перемножать.
Объём сообщения
Если в условии спрашивают про все N номеров вместе (например, «сколько бит нужно для хранения списка из 150 номеров»), то считается так:
$$V = N \cdot L$$
где L — длина одного номера в битах. Если условие требует «целое число байт на один номер», то сначала округляешь L до ближайшего кратного 8 вверх, а потом умножаешь.
Округление до байта
Формула:
$$L_{\text{байт}} = \lceil L / 8 \rceil \cdot 8$$
Примеры:
| L (бит) | L (байт, округлено вверх) | L (бит, выровнено по байту) |
|---|---|---|
| 5 | 1 | 8 |
| 7 | 1 | 8 |
| 9 | 2 | 16 |
| 15 | 2 | 16 |
| 17 | 3 | 24 |
| 31 | 4 | 32 |
| 33 | 5 | 40 |
Если в условии написано «на хранение одного номера отводится целое число байт», не забудь выровнять. Пропускают это в трёх случаях из пяти.
Пример 1: автомобильные номера
В некотором государстве автомобильный номер состоит из 3 букв и 4 цифр. Используются заглавные буквы русского алфавита, кроме Ё (32 буквы), и все десятичные цифры. Каждый символ кодируется минимальным возможным количеством бит, одинаковым для всех букв и одинаковым для всех цифр. Номер целиком кодируется минимальным возможным целым числом байт. Сколько байт необходимо для хранения 60 номеров?
Решение
Шаг 1. Длина кода одной буквы. Алфавит — 32 буквы. 2^5 = 32 ≥ 32, значит ceil(log2(32)) = 5 бит.
Шаг 2. Длина кода одной цифры. Алфавит — 10 цифр. 2^4 = 16 ≥ 10, значит ceil(log2(10)) = 4 бита.
Шаг 3. Длина одного номера в битах. 3 · 5 + 4 · 4 = 15 + 16 = 31 бит.
Шаг 4. Округление до байт. 31 / 8 = 3.875, округляем вверх: 4 байта на номер.
Шаг 5. Объём для 60 номеров. 60 · 4 = 240 байт.
Ответ: 240.
Обрати внимание: 31 бит ≤ 32 бита (4 байта), поэтому округление добавляет ровно 1 «лишний» бит на каждый номер. Если бы номер был 33 бита — потребовалось бы уже 5 байт.
Пример 2: сотрудники с разными отделами
На предприятии 300 сотрудников. Каждому присваивается табельный номер вида «код отдела (буква) — номер сотрудника (цифры)». Всего отделов 12. Внутри каждого отдела свой счётчик сотрудников от 1 до максимума (до 40). Каждый символ кодируется минимальным возможным количеством бит, одинаковым для всех букв и одинаковым для всех цифровых позиций. Длина номера сотрудника — 2 цифры. Сколько бит нужно для кодирования всех 300 табельных номеров?
Решение
Шаг 1. Буква-код отдела. 12 отделов. 2^4 = 16 ≥ 12 → 4 бита.
Шаг 2. Цифра номера сотрудника. 10 цифр (позиционно). 2^4 = 16 ≥ 10 → 4 бита на цифру.
Шаг 3. Длина одного номера. 1 · 4 + 2 · 4 = 4 + 8 = 12 бит.
Шаг 4. В условии не требуется округлять до байт, складываем как есть: 300 · 12 = 3600 бит.
Ответ: 3600.
Ловушка. Здесь в условии не сказано «целое число байт», значит, округлять не нужно. Если бы было сказано «на один номер отводится целое число байт» — было бы: ceil(12 / 8) = 2 байта = 16 бит, и ответ стал бы 300 · 16 = 4800 бит (или 600 байт).
Пример 3: не перепутать сложение с умножением
Артикул товара состоит из 5 символов: каждый символ — либо цифра (10 вариантов), либо строчная буква латиницы (26 вариантов). Каждый символ кодируется минимальным одинаковым количеством бит. Сколько бит потребуется для одного артикула?
Решение
Шаг 1. На каждой позиции могут стоять и цифры, и буквы, значит, алфавит одного символа — 10 + 26 = 36 знаков.
Шаг 2. 2^5 = 32 < 36 < 64 = 2^6 → ceil(log2(36)) = 6 бит на символ.
Шаг 3. Длина артикула — 5 символов · 6 бит = 30 бит.
Ответ: 30.
Ловушка. Легко прочитать «5 символов, из них какие-то буквы, какие-то цифры» как номер с разными алфавитами по позициям. Но здесь на каждой позиции может быть любой из 36 символов, значит, алфавит один — 36 знаков.
Python-помощник
На КЕГЭ Python разрешён — можно быстро посчитать log2 и убедиться в округлении. Шаблон:
from math import ceil, log2
def bits(n: int) -> int:
"""Минимальное число бит для кодирования n значений."""
k = 0
while (1 << k) < n:
k += 1
return k
def to_bytes(bits_count: int) -> int:
return (bits_count + 7) // 8
# Пример 1: автомобильные номера
letter_bits = bits(32) # 5
digit_bits = bits(10) # 4
one_number = 3 * letter_bits + 4 * digit_bits # 31
one_number_bytes = to_bytes(one_number) # 4
total = 60 * one_number_bytes # 240
print(total) # 240
Использование целочисленного цикла while (1 << k) < n надёжнее, чем ceil(log2(n)): при n = 8 функция log2(8) == 3.0, и ceil(3.0) == 3 — верно. Но из-за ошибок плавающей точки (скажем, log2(1024) может дать 9.99999...) ceil иногда отдаёт неправильный результат. Цикл через сдвиги бит — бескомпромиссный.
Подробнее про полезные идиомы Python для экзамена — в статье Python-идиомы для ЕГЭ по информатике. Если колеблешься между Python и C++ — посмотри сравнение.
Типичные ошибки
Ошибка 1: забыл округлить до байта. Условие говорит «целое число байт на номер», а ты посчитал в битах и ответил. Потеря балла на ровном месте. Всегда подчёркивай в условии фразы про биты/байты.
Ошибка 2: перемножил вместо сложения разрядов. Длина кода — сумма длин разрядов, не произведение. Произведение используется, если спрашивают «сколько всего разных номеров» (это совсем другая задача — комбинаторика, не задание 11).
Ошибка 3: неправильно определил алфавит символа. Если на каждой позиции может стоять любой из 36 знаков — алфавит один, 36. Если в разных разрядах разные наборы — алфавитов несколько, считаем отдельно.
Ошибка 4: не округлил вверх. ceil(log2(10)) = 4, а не 3 и не 3.32. Даже если дробь ровно попадает на 0.1 сверху от целого — округлять вверх обязательно.
Ошибка 5: двойное округление. Округлил сначала длину одного символа до байта, потом общую длину ещё раз. Так делать нельзя — лишние байты накапливаются. Округляй там, где явно указано в условии (обычно — на уровне одного номера целиком).
Подборка других частых промахов — в статье про 5 ошибок на ЕГЭ.
Тайминг
Задание 11 — 3-5 минут на спокойном темпе. Если уложился в 2-3 минуты — прекрасно, освободил время для 24-го, 25-го или 27-го. Если задача тянется дольше 7 минут — значит, ты не там округляешь или не так читаешь условие: перечитай первую и последнюю строчку условия, ищи слова «бит», «байт», «целое число».
Номер находится в первой трети экзамена, решать его стоит в первый час — пока голова свежая, а дальше идут более трудоёмкие задания (10, 12, 13).
Как тренироваться
- Освой формулу наизусть. Запомни таблицу
2^k: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Без этого каждая задача превращается в арифметический марафон. - Реши 20 простых задач на одиночный алфавит — пока не начнёшь выдавать k мгновенно для любого N.
- Перейди к номерам с разными алфавитами — 30-40 задач, с перемешиванием «округлить до бит» и «округлить до байт».
- Прорешай подборку с ловушками — где одни условия про биты, другие про байты, третьи про количество разных номеров. Главная цель — не путаться в том, что именно спрашивают.
- Замеряй время. Финальный норматив — 3 минуты на задание. Если через месяц тренировок ты стабильно укладываешься — можно переходить к следующему номеру.
Если общий план подготовки ещё не готов, начни с плана на 3 месяца или с нуля. В TuteMe собраны банки задач отдельно на каждый тип задания 11 — с автопроверкой и пошаговым разбором ошибок.