Решать задания
Информатика · тема 3 из 13 · ОГЭ № 1, 2 · ЕГЭ № 4, 7, 11

Кодирование информации и условие Фано

Сколько бит занимает текст, картинка, звук или пароль и как построить неравномерный код, который однозначно декодируется, — ОГЭ-1, ОГЭ-2, ЕГЭ-4, ЕГЭ-7, ЕГЭ-11.

25 мин чтенияОГЭЕГЭ21 задание

Коротко

главное за 30 секунд
  1. Формула Хартли: N = 2i; на символ из N-буквенного алфавита нужно i = ⌈log2N⌉ бит
  2. Текст: I = K · i; изображение: I = W · H · i; звук: I = f · i · k · t
  3. 1 байт = 8 бит, 1 Кбайт = 1024 байт = 213 бит, 1 Мбайт = 1024 Кбайт
  4. Условие Фано: ни одно кодовое слово не является началом другого — тогда сообщение декодируется однозначно
  5. Пароли (ЕГЭ-11): бит на символ — минимум, байт на пароль — округление вверх

Бит, байт и формула Хартли

Бит — наименьшая единица информации: одна двоичная цифра, 0 или 1. Цепочкой из $i$ бит можно закодировать $2^i$ разных значений.

Формула Хартли. $N = 2^i$, где $N$ — мощность алфавита (сколько разных символов, цветов, уровней), $i$ — число бит на один символ.
Если $N$ не степень двойки, округляем вверх: $i = \lceil \log_2 N \rceil$.
ЕдиницаСколько
1 байт8 бит = $2^3$ бит
1 Кбайт1024 байт = $2^{10}$ байт = $2^{13}$ бит
1 Мбайт1024 Кбайт = $2^{20}$ байт
1 Гбайт1024 Мбайт = $2^{30}$ байт

Пример. Алфавит из 33 букв. $2^5 = 32 \lt 33 \le 64 = 2^6$, значит на букву нужно 6 бит: пяти бит хватает только на 32 символа.

В задачах ФИПИ «Кбайт» — это 1024 байт, а не 1000. Пересчитывайте через степени двойки: $1\text{ Кбайт} = 2^{13}$ бит — тогда числа сокращаются почти всегда.
Проверь себя. Сколько бит нужно на один символ при равномерном кодировании алфавита из 50 символов?

Ответ: 6

1 бит× 81 байт× 10241 Кбайт× 10241 Мбайт× 10241 Гбайт1 Кбайт = 2¹⁰ байт = 1024 байта = 8192 бита
Рис. 1. Единицы измерения информации: 1 байт = 8 бит, дальше каждая единица больше предыдущей в 1024 раза

Объём текста (ОГЭ-1)

$I = K \cdot i$, где $K$ — число символов (включая пробелы и знаки препинания), $i$ — бит на символ.
Кодировки: КОИ-8, Windows-1251 — 8 бит (1 байт) на символ; UTF-16 (одна из кодировок Unicode) — 16 бит (2 байта).

Пример. Реферат: 8 страниц, на странице 40 строк по 64 символа, кодировка — 16 бит на символ.

$I = 8 \cdot 40 \cdot 64 \cdot 2\text{ байт} = 40\,960\text{ байт} = 40\text{ Кбайт}$.

ОГЭ-1 обычно устроено так: дано предложение-перечисление, из него вычеркнули одно слово вместе с лишней запятой и пробелом, и размер уменьшился на X байт. Нужно найти слово.

Схема. Кодировка 16 бит = 2 байта на символ. Предложение уменьшилось на 20 байт → удалено 10 символов. Из них 2 — запятая и пробел, значит в слове 8 букв.

Не забывайте про запятую и пробел! Удаляется слово плюс два символа. И следите за единицами: «на 16 байт» при 16-битной кодировке — это 8 символов, а не 16.

Изображение и звук (ЕГЭ-7)

Растровое изображение: $I = W \cdot H \cdot i$, где $W \times H$ — размер в пикселях, $i$ — глубина цвета, число цветов в палитре $N = 2^i$.
Звук: $I = f \cdot i \cdot k \cdot t$, где $f$ — частота дискретизации (Гц), $i$ — разрешение (бит), $k$ — число каналов (моно 1, стерео 2, квадро 4), $t$ — время (с).

Пример 1. Картинка 1024 × 768 пикселей, 256 цветов. $i = 8$ бит = 1 байт на пиксель. $I = 1024 \cdot 768$ байт $= 768$ Кбайт.

Пример 2. Под изображение 640 × 480 отведено 225 Кбайт. Бит на пиксель: $\dfrac{225 \cdot 2^{13}}{640 \cdot 480} = 6$, значит максимум $2^6 = 64$ цвета.

Задачи «перезаписали звук с другими параметрами» решайте через пропорции: объём прямо пропорционален каждому из множителей $f$, $i$, $k$, $t$. Стерео вместо моно — ×2, частота в 3 раза меньше — :3.
Если бит на пиксель получилось дробное, например 9,4, — округляем вниз (9 бит): 10 бит в отведённую память уже не поместятся. А вот при подсчёте бит на символ алфавита (формула Хартли) округляем вверх. Не путайте!
ширина w пикселейhI = w · h · ii — бит на пиксель, N = 2ⁱ цветовпример: 1024 × 768 пикселей, 8 бит= 6 291 456 бит = 768 Кбайт
Рис. 2. Объём растрового изображения I = w · h · i бит; палитра из N цветов требует i = log₂N бит на пиксель

Неравномерный код и условие Фано (ОГЭ-2, ЕГЭ-4)

В неравномерном коде у букв коды разной длины: частым буквам дают короткие коды — сообщение получается короче. Но декодировать его можно, только если код однозначен.

Условие Фано: никакое кодовое слово не является началом (префиксом) другого кодового слова. Тогда сообщение декодируется однозначно: читаем слева направо и отрезаем первый совпавший код.

Пример. Коды: А — 0, Б — 10, В — 110. Сообщение 0101100 читаем слева: 0 → А, 10 → Б, 110 → В, 0 → А. Ответ: АБВА.

Кодовое дерево. Каждый код — путь от корня: 0 — влево, 1 — вправо. Код Фано — это когда все буквы стоят в листьях дерева. Свободные ветки показывают, какие коды ещё можно выдать.

ЕГЭ-4. Известны коды А — 0, Б — 100, В — 101. Нужны коды ещё для трёх букв с наименьшей суммарной длиной.

Заняты ветки 0 и 10*. Свободна только ветка 11. Трём буквам в ней нужно три листа: 110, 1110, 1111. Сумма длин $3 + 4 + 4 = 11$.

Код 11 целиком одной букве отдать нельзя: тогда для двух других букв места не останется. Проверяйте, что свободных листьев хватает на все оставшиеся буквы. А если в задаче надо минимизировать длину слова, самые короткие коды отдавайте самым частым буквам этого слова.
010101АБВГветка влево — 0,вправо — 1буквы только в листьях
Рис. 3. Кодовое дерево: коды А = 0, Б = 10, В = 110, Г = 111 лежат в листьях, поэтому ни один не начало другого (условие Фано)

Пароли и номера (ЕГЭ-11)

Схема задания: пароль или номер из $L$ символов, алфавит из $N$ символов. Каждый символ кодируется одинаковым минимальным числом бит, а весь пароль — минимальным целым числом байт.

1) $i = \lceil \log_2 N \rceil$ бит на символ;
2) пароль: $L \cdot i$ бит → округлить вверх до целых байт;
3) умножить на число пользователей (и прибавить дополнительные сведения, если есть).

Пример. Пароль из 11 символов; алфавит — 26 латинских заглавных букв и 10 цифр, всего 36 символов. $i = 6$ бит ($2^5 = 32 \lt 36$). $11 \cdot 6 = 66$ бит → 9 байт (8 байт = 64 бита мало).

from math import ceil, log2
N, L = 36, 11
i = ceil(log2(N))          # 6 бит на символ
b = ceil(L * i / 8)        # 9 байт на пароль
print(i, b)
Байты округляются для каждого пароля отдельно, а не для всей базы целиком: пароли хранятся по отдельности, и «доли байта» от разных пользователей не складываются.
Практика

Закрепите тему: 21 задание для ОГЭ и ЕГЭ

От простых к сложным: базовый уровень — 8, повышенный — 8, высокий — 5. Мгновенная проверка, подсказки, подробные решения и тренажёр ошибок.

Решать задания по теме Флеш-карточки