Задание 4 ЕГЭ по информатике

Что проверяет: Кодирование и условие Фано

Задание 4 ЕГЭ по информатике проверяет тему «кодирование и условие Фано». Ниже вы найдёте 1 вариант с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.

Ответ

Теория к заданию 4 ЕГЭ по информатике: кодирование и условие Фано

Нужно построить кодовые слова, удовлетворяющие условию Фано, и найти их минимальную суммарную длину.

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

Условие Фано: ни одно кодовое слово не совпадает с началом другого. Это обеспечивает однозначное декодирование.
Удобная модель: двоичное дерево. Кодовое слово соответствует пути от корня к листу, занятый узел закрывает всё поддерево.
Если заняты коды 10, 11, 010, 011, то свободны ветви 00, 0000 и так далее.
Минимальная суммарная длина достигается, когда самые короткие свободные коды отдаются первым буквам.
Количество свободных кодов длины k на свободной ветви равно 2 в степени оставшихся разрядов.

Условие Фано и неравномерное кодирование

Условие Фано: никакое кодовое слово не совпадает с началом другого кодового слова.
Обратное условие Фано: никакое кодовое слово не совпадает с окончанием другого.
Удобная модель: двоичное дерево. Кодовые слова должны стоять только в листьях, ни одно не может быть предком другого.
Неравенство Крафта: сумма 2^(−lᵢ) по всем кодовым словам не должна превышать 1. Это быстрый тест на существование кода.
Если заняты коды длины 1 и 2, у них «отнимаются» целые поддеревья: код длины 1 забирает половину всех слов.
Для минимальной суммарной длины давайте короткие коды частым буквам: на этом принципе построен код Хаффмана.
Считая суммарную длину сообщения, умножайте длину кода каждой буквы на число её вхождений.
Проверяйте построенный набор: расшифруйте пробную строку слева направо однозначно.

Как решать задание 4

Нарисуйте двоичное дерево и отметьте на нём известные кодовые слова.
Вычеркните все поддеревья, которые они закрывают.
Найдите самые короткие свободные узлы и назначайте их оставшимся буквам.
Сложите длины назначенных кодов.
Запишите суммарную длину числом.

Разбор примера

Для букв А, Б, В уже заданы коды 0, 10 и 110. Какой минимальной длины код можно дать букве Г, чтобы выполнялось условие Фано?

Строим двоичное дерево и отмечаем занятые вершины: 0, 10, 110.
Код 0 занимает всё левое поддерево, значит новый код не может начинаться с 0.
Код 10 занимает поддерево с началом 10, а код 110 занимает поддерево с началом 110.
Свободной остаётся ветка 111 и всё, что под ней.
Самый короткий свободный код равен 111, его длина 3.
Проверяем условие Фано: ни один из кодов 0, 10, 110 не начинается с 111, и 111 не начинается ни с одного из них.

Ответ111, длина 3

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

Назначают код, который начинается с уже занятого слова.
Считают длину только одного кодового слова вместо суммы.

Задание 4 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.