Задание 4. Кодирование и декодирование информации: ЕГЭ по информатике

Задание 4 ЕГЭ по информатике проверяет умение кодировать и декодировать информацию с использованием двоичного кода, удовлетворяющего условию Фано (или обратному условию Фано). В демоверсии требуется определить минимальное количество двоичных знаков для кодирования конкретного слова (например…

Что нужно знать

Условие Фано: никакое кодовое слово не является началом другого кодового слова (префиксный код).
Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова (суффиксный код). В задании обычно используется прямое условие Фано.
Для однозначного декодирования достаточно, чтобы код был префиксным (условие Фано) или суффиксным (обратное условие).
При построении кодовых слов для неизвестных букв нужно учитывать уже заданные коды: новое кодовое слово не должно быть префиксом или продолжением существующих.
Двоичное дерево кодирования: известные коды занимают некоторые листья, для новых кодов выбираются свободные ветви.
Минимизируется суммарная длина кодирования всего слова, а не отдельных букв. Поэтому буквы с большей частотой должны получать более короткие коды.

Термины и понятия

Условие Фано: свойство префиксного кода, при котором ни одно кодовое слово не является началом другого кодового слова.
Префиксный код: код, в котором ни одно кодовое слово не является префиксом другого.
Декодирование: процесс восстановления исходного сообщения по закодированному.
Кодовое слово: последовательность двоичных знаков, сопоставленная букве алфавита.
Двоичное дерево кодирования: граф, представляющий кодовые слова, где левый потомок соответствует биту 0, правый — биту 1.
Частота буквы: количество вхождений данной буквы в кодируемое слово.
Минимальная длина кодирования: наименьшая возможная суммарная длина кодовых слов для всех букв слова при заданных ограничениях.
Однозначность декодирования: возможность единственным образом восстановить исходное сообщение из закодированного.

Частые ошибки

Минимизация длины кода каждой буквы отдельно, без учёта частоты вхождения в слово. Например, выбирают для буквы К код длины 1, а для О — длины 2, хотя О встречается чаще.
Нарушение условия Фано при выборе кодовых слов: выбирают код, который является префиксом уже существующего.
Не учитывают, что кодовые слова для неизвестных букв должны быть совместимы не только друг с другом, но и с известными кодами.
Забывают проверить однозначность декодирования после выбора кодов.

Как пройти тему

В курсе «Информатика» тема «Задание 4. Кодирование и декодирование информации» занимает 5 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Задание 3. Поиск информации в реляционных базах данных
Следующая тема: Задание 5. Формальное исполнение алгоритма

Все темы: ЕГЭ по информатике