Сжатие данных для экзамена ЕГЭ информатика

** изображение создано или обработано с помощью ИИ.

На ЕГЭ по информатике тема сжатия данных проверяется не через построение сложных алгоритмов, а через неравномерное кодирование и условие Фано (задание №4), а также через расчёт объёма сжатого файла (задание №7). Чтобы решить эти задачи за 2-3 минуты, достаточно понимать принцип префиксности и уметь переводить биты в байты.

Ниже — пошаговые схемы разбора типовых задач.

Кодирование данных ЕГЭ: что реально проверяют

** изображение создано или обработано с помощью ИИ.

В быту мы называем сжатием уменьшение размера файла (zip, rar). В информатике основа любого сжатия без потерь — это устранение избыточности.

Если какой-то символ встречается часто, ему выгоднее дать короткий код. Если редко — длинный.

Именно этот принцип лежит в основе неравномерного двоичного кодирования, которое проверяется в задании №4.

На экзамене вам не придётся считать степень сжатия или строить деревья Хаффмана. Ваша задача — работать с кодами символов так, чтобы сообщение можно было однозначно расшифровать.

Ключевое правило: чтобы код был эффективным (сжатым) и однозначным, он должен удовлетворять условию Фано.

Условие Фано: как быстро проверить коды на префиксность

** изображение создано или обработано с помощью ИИ.

Никакое кодовое слово не может быть началом другого такого же кодового слова. Пример: если буква А имеет код 0, то у буквы Б не может быть кода, начинающегося с 0 (например, 01 или 001 запрещены). Иначе при декодировании возникает неоднозначность — получив 0, невозможно определить, это сама буква А или начало кода буквы Б.

В заданиях ЕГЭ этот принцип используется так: самым частым символам назначают короткие коды. Но соблюдают условие, чтобы декодирование было однозначным.

Типовые формулировки задания №4:

1. Дана часть таблицы кодов. Требуется найти кратчайший возможный код для новой буквы при условии Фано.

1. Дана закодированная строка и известная таблица кодов. Нужно восстановить исходное сообщение.

Для проверки условия удобно построить бинарное дерево кодирования. Начало (корень) — пустая строка. От него отходят две ветви: 0 и 1. Если код уже занят (соответствует листу дерева), от этого листа нельзя проводить новые ветви. Иначе условие Фано будет нарушено.

Сжатие и кодирование данных ЕГЭ: пошаговый алгоритм решения

** изображение создано или обработано с помощью ИИ.

Для задания №4 (условие Фано) порядок действий следующий.

1. Выпишите все известные коды и проверьте их на префиксность — ни один код не должен быть началом другого.

1. Если нужно найти код для новой буквы, перебирайте возможные коды, начиная с самой короткой длины (1 бит: 0 и 1).

1. Если оба варианта длины 1 уже заняты или конфликтуют (то есть являются началом существующего кода, либо существующий код является их началом), переходите к длине 2 (00, 01, 10, 11).

1. Отбрасывайте те варианты, которые начинаются с уже существующих кодов или имеют существующий код в качестве своего начала.

1. Первый подходящий вариант будет ответом, так как требуется кратчайший возможный код.

Для задания №7 (вычисление объёма после сжатия) действуйте так.

1. Переведите исходный размер данных в биты (1 байт = 8 бит).

1. Примените процент сжатия или увеличения из условия. Например, если объём уменьшился на 20%, умножьте на 0,8; если увеличился на 15% — умножьте на 1,15.

1. Затем переведите полученный результат обратно в единицы, требуемые в ответе (Кбайт, Мбайт и т.д.).

Частая ошибка в этом задании — неправильный перевод единиц измерения. Рекомендуется записывать все промежуточные величины с единицами измерения и проверять каждый переход (байты — биты, байты — Кбайты и т.п.) на черновике.

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

** изображение создано или обработано с помощью ИИ.

Даже зная теорию, ученики часто теряют баллы из-за невнимательности. Вот топ-3 ошибки в задачах на кодирование и сжатие:

1. Нарушение условия Фано «в обратную сторону». Ученики проверяют, не начинается ли новый код со старого. Но забывают проверить наоборот: не является ли старый код началом нового.

Пример: есть код 10. Вы хотите присвоить новый код 1. Это нельзя, так как 1 является началом 10.

1. Поиск любого кода, а не кратчайшего. В условии часто сказано: «Найдите кратчайший код». Ученик находит подходящий код длины 3, хотя есть свободный код длины 2. Всегда начинайте перебор с минимальной длины.

1. Путаница в степенях при переводе объёма (Задание №7). 1 Кбайт = 1024 байт, а не 1000. В задании №7 из-за этого легко получить неверный ответ на порядок.

Рекомендуется выписывать все единицы измерения столбиком и сокращать их как в математике.

Немного практики и одна история из жизни

** изображение создано или обработано с помощью ИИ.

В ходе решения задач на сжатие данных возможна ситуация, когда после применения алгоритма закодированное сообщение оказывается длиннее исходного. Это не промах в расчётах.

Условие задачи (тип №4). Для кодирования букв А, Б, В используются двоичные коды: А — 0, Б — 10. Требуется найти кратчайший возможный код для буквы В, удовлетворяющий прямому условию.

Проверка кодов длины 1. Код 0 уже занят буквой А. Код 1 свободен, но создаёт конфликт: код буквы Б (10) начинается с 1. Следовательно, 1 использовать нельзя.

Проверка кодов длины 2. Коды 00 и 01 начинаются с 0 (код А) — не подходят. Код 10 занят буквой Б. Код 11 не начинается ни с 0, ни с 10, и ни один из существующих кодов (0, 10) не начинается с 11. Условие Фано выполнено. Ответ: 11.

Если хотите, отработайте 10 вариантов в интерактивном тренажёре по кодированию с автопроверкой.

Советы для подготовки к экзамену и тренировки навыков

** изображение создано или обработано с помощью ИИ.

Тема кодирования и эффективного сжатия данных в ЕГЭ требует не зубрёжки, а понимания логики.

1. Рисуйте деревья. Даже простое схематическое дерево помогает увидеть запрещённые ветви быстрее, чем перебор в уме.

1. Тренируйтесь на демоверсиях. Возьмите задание №4 и №7 из демоверсии ФИПИ 2025 и решите их за 2–3 минуты каждое.

1. Не усложняйте. Помните: на экзамене не будет задач на расчёт энтропии или построение кодов Хаффмана для больших текстов. Только логика префиксов и арифметика объёмов.

Подготовка к ЕГЭ — это марафон. Системный подход к каждой теме, даже такой небольшой, как кодирование, приносит свои плоды на экзамене. Проверьте готовность в нашей онлайн-школе.