Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

ЕГЭ по информатике - Задание 5 (Условие Фано)



Привет! Сегодня узнаем, как решать пятое задание из ЕГЭ по информатике.


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


Задача (стандартная)

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу.


Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование


Решение:

Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.


Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).


От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.


Получается структура похожая на дерево!


В конце каждой ветки можно располагать букву, которую мы хотим закодировать, но если мы расположили букву, от этой ветки больше нельзя делать новых ответвлений.


Такой подход позволяет однозначно декодировать сообщение, состоящее из этих букв.


ЕГЭ по информатике - задание 5 (Дерево Фано)

Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.


Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.


ЕГЭ по информатике - задание 5 (Дерево Фано решение)

Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.


Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствует наименьшему возможному двоичному числу. Как расположить буквы D и F в данной задаче не принципиально.


ЕГЭ по информатике - задание 5 (Дерево Фано окончательное решение)


Ответ: 1000.

Ещё один важный тип задания 5 из ЕГЭ по информатике.


Задача (стандартная)

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, К — 010, Л — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?


Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.


Решение:

Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоим как можно меньшую длину!


Отметим на дереве Фано уже известные буквы (Б, К, Л).


ЕГЭ по информатике - задание 5 (стандартная задача Дерево Фано)


У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?


1 вариант

Если продолжить линию 1-0, то получится такая картина :



ЕГЭ по информатике - задание 5 (тренировочная задача Дерево Фано)

Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.


Посчитаем общую длину слова АБСЦИССА.


ЕГЭ по информатике - задание 5 (тренировочная задача подсчёт длины)

3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.


2 вариант

Продлим линию 1-1-0 (можно и 0-1-1, не принципиально, т.к. эти ветки имеют одинаковую длину.), то получится:

ЕГЭ по информатике - задание 5 (тренировочная задача дерево фано 2)


С мы присваиваем 1-0, т.к. это буква повторяется в сообщении самое большое количество раз, значит, ей присваиваем самый маленький код, чтобы всё сообщение имело наименьшую длину.


Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.


Подсчитаем общее количество символов в сообщении.


ЕГЭ по информатике - задание 5 (тренировочная задача подсчёт длины 2)

3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22


Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.


Ответ: 22.

Задача (не сложная)

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-10, Б-11, В-110, Г-0. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в восьмеричный вид.


Решение:

В этой задаче ничего не сказано про условие Фано. Здесь уже все буквы закодированы, осталось написать сам код.


Задача сводится к переводу из двоичной системы в восьмеричную систему, как в первой задаче из ЕГЭ по информатике. На эту тему был урок на моём сайте.


ЕГЭ по информатике - задание 5 (кодирование сообщения)


Ответ: 151646.

На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.






12-05-2020 в 20:57:20





Похожая статья:

ЕГЭ по информатике - Задание 12 (Неудержимые нули!)

На этом уроке будем проходить, как решать 12 задание из ЕГЭ по информа...

Категория: ЕГЭ  Подкатегория: -
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



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





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy