Задание 4. Двоичное кодирование и условие Фано: ЕГЭ по информатике

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

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

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

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

Кодирование: процесс преобразования информации в последовательность символов (кодов).
Декодирование: обратный процесс восстановления исходного сообщения по кодовой последовательности.
Равномерный код: код, в котором все кодовые слова имеют одинаковую длину.
Неравномерный код: код, в котором кодовые слова имеют разную длину.
Префикс: начальная часть слова; слово A является префиксом слова B, если B начинается с A.
Суффикс: конечная часть слова; слово A является суффиксом слова B, если B заканчивается на A.
Условие Фано (прямое): ни одно кодовое слово не является префиксом другого кодового слова.
Обратное условие Фано: ни одно кодовое слово не является суффиксом другого кодового слова.

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

Путают прямое и обратное условие Фано: проверяют, что слово не является суффиксом, когда требуется проверка на префикс, и наоборот. Это приводит к неверному выбору кодового слова.
Забывают, что при добавлении нового кодового слова нужно проверять его на конфликт не только с уже известными словами, но и с теми, которые могут быть получены как префиксы/суффиксы.
Выбирают кодовое слово, которое является префиксом уже существующего, но не замечают этого, потому что сравнивают только с более короткими словами.
При поиске кратчайшего кодового слова перебирают не все возможные длины, а останавливаются на первой найденной, не проверяя, нет ли более короткого варианта с меньшим числовым значением.

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

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

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

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

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

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