ЕГЭ по информатике 2021: Разбор задания 4 (кодирование)

Кодирование и декодирование информации — ключевые понятия четвёртого задания ЕГЭ по информатике. Рассмотрим типы задач и методы их решения.

Теория кодирования

Кодирование — перевод информации с одного языка на другой. Декодирование — обратный процесс. Пример: перевод текста с английского на русский (кодирование) и обратно (декодирование).

Существует равномерное и неравномерное кодирование. При равномерном кодировании все символы кодируются кодами одинаковой длины (например, каждый символ русского алфавита — 8 битами). Неравномерное кодирование использует коды разной длины, что усложняет декодирование.

Однозначное декодирование и условие Фано

Для однозначного декодирования необходимо выполнение условия Фано или обратного условия Фано:

  • Условие Фано: ни одно кодовое слово не может быть началом другого кодового слова.
  • Обратное условие Фано: ни одно кодовое слово не может быть окончанием другого кодового слова.

Для однозначного декодирования достаточно выполнения одного из этих условий.

Решение задач с помощью бинарных деревьев

Эффективный метод решения задач 4 типа ЕГЭ — использование бинарных деревьев. Бинарное дерево строится, начиная с 0 или 1, и ветвится на 0 и 1 на каждом уровне. При построении дерева учитывается условие Фано.

Пример:

Символы A, B, C, D кодируются: A = 1, B = 010, C = 000. Найдём код для D, соблюдая условие Фано.

Построим бинарное дерево:

  • Начинаем с A (1). Последующие кодовые слова не могут начинаться с 1.
  • B (010) располагается на следующей ветке. Дальнейшее ветвление под B невозможно, чтобы не нарушить условие Фано.
  • C (000) располагается на своей ветке.
  • Для D остаются варианты 011 и 001. Наименьший — 001. Код для D — 001.

Разбор задач ЕГЭ

Задача 1:

Передаются сообщения, содержащие только буквы A, B, C, D. Используется двоичный код, допускающий однозначное декодирование. Кодовые слова: A = 111, B = 0, C = 110. Найдите кратчайшее кодовое слово для D.

Решение: Построение бинарного дерева показывает, что кратчайший код для D — 10.

Задача 2:

Четыре буквы: П, О, С, Т. Код допускает однозначное декодирование. T = 111, O = 0, П = 10. Найдите код для С.

Решение: Построение бинарного дерева показывает, что кратчайший код для С — 101.

Задача 3:

Используется неравномерный двоичный код, удовлетворяющий условию Фано. A = 11, B = 101, C = 0. Найдите кодовые слова для D, E, F.

Решение: Построение бинарного дерева с учётом условия Фано и всех букв (A, B, C, D, E, F) даёт один из возможных вариантов кодирования: F = 1000, E = 1001, D = 1010 или подобные.

Задача 4:

Передаются сообщения, содержащие буквы K, L, M, N. Используется неравномерный двоичный код, удовлетворяющий условию Фано. N = 0, K = 10. Найдите наименьшую возможную суммарную длину всех четырёх кодовых слов.

Решение: Построение бинарного дерева позволяет найти минимальную суммарную длину кодов — 9.

Задача 5:

Используется двоичный код, удовлетворяющий условию Фано. Известны кодовые слова для некоторых букв. Найдите наименьшее количество двоичных знаков для кодирования слова «КАТОК».

Решение: Необходимо построить бинарное дерево, учитывая условие Фано для всех букв, и минимизировать длину кодов для наиболее часто встречающихся букв в слове «КАТОК».

Задача 6:

Для кодирования слова БАОБАБ потребовалось 16 двоичных знаков. Известны кодовые слова для В, Г, Д, Е. Найдите кодовое слово для О.

Решение: Анализ длины кодового слова БАОБАБ и частоты символов позволяет найти единственный вариант кодирования, удовлетворяющий условию Фано, где О = 001.

Задача 7:

Для кодирования букв R, C, H, O, G используется двоичное представление чисел 0, 1, 2, 3, 4 с сохранением незначащего нуля. Закодируйте последовательность НОСОРОГ и запишите результат в восьмеричном коде.

Решение: Перевод букв в двоичный код, конкатенация и перевод в восьмеричный код даёт ответ.

Решение задач 4 типа ЕГЭ по информатике требует понимания принципов кодирования, декодирования и условия Фано. Применение бинарных деревьев упрощает процесс поиска кодовых слов и минимизации их длины. Важно учитывать все символы из заданного набора, даже если они не входят в кодируемое слово.

Что будем искать? Например,программа