Кодирование и декодирование информации. Проверяется умение кодировать и декодировать информацию. Условие Фано. Бинарные деревья.
Кодирование – это перевод информации с одного языка на другой. Декодирование – обратный перевод.
Например, ученик переводит текст учителю с английского языка на русский. Происходит процесс кодирования. Учитель проверяет и переводит наоборот с русского на английский. Соответственно происходит процесс декодирования.
Тема кодирования может быть рассмотрена по ссылке.
Равномерное и неравномерное кодирование
Кодирование может быть равномерным и неравномерным.
Равномерное кодирование — это когда все символы кодируются кодами одинаковой длины. Предположим, что мы берем какую-нибудь систему кодирования и в ней все символы русского алфавита кодируются восемью символами.
При неравномерном кодировании длина каждого символа будет разной.
Если используется неравномерное кодирование, то это очень усложняет процесс декодирования.
Условие Фано при кодировании и декодирование
Задание № 4 ЕГЭ полностью на кодирование каких-то символов.
Любое сообщение можно однозначно декодировать, что означает, что обязательно будет исполняться условие Фано. Это является важным в задании № 4.
Условие Фано: ни одно кодовое слово не может являться началом другого кодового слова. Аналогично условию Фано, если и обратное условие Фано.
Оно звучит также, только наоборот: ни одно кодовое слово не может являться окончанием другого кодового слова.
Если в задаче требуется однозначное декодирование, то для однозначного декодирования достаточно чтобы выполнялось условие ФАНО, либо обратное условие Фано.
Давайте разберем на примере условие Фано.
Пусть у нас будет четыре буквы, которым соответствует код:
А – 1
Б – 010
В – 000
Г – найти код
Мы знаем, что выполняется условие Фано.
Как же решаются такие задачи? Конечно, можно методом перебора, но это довольно долго. Самый удобный способ решения задания по информатике – это использование бинарных деревьев.
Они могут начинаться либо с нуля, либо с единицы. Их еще называют двоичными деревьями. В них есть только ноль и один.
Рассмотрим решение задания.
Буква А — 1
Если выполняется условие Фано 9однозначное декодирование), то получается, что все, что находится ниже буквы А не может являться кодами наших слов. Потому, что буква А = 1 будет являться началом этих кодовых слов. Мы сразу убрали довольно много вариантов.
Теперь смотрим на второе дерево, которое начинается с нуля.
Мы сразу можем выделить букву Б
И видим, что дальше мы это дерево строит не можем. Потому, что, если мы будем брать коды из цифр, которые будут располагаться дальше, то Б будет являться для этих слов началом кодового слова. В этом случае условие Фано будет не выполнено.
Смотрим дальше.
Видим, что на этом же дереве можно найти букву В
И дальше, соответственно, идти некуда.
Остается вопрос, а какой код можно взять для буквы Г?
Можно взять либо 011, либо 001
Это два варианта для буквы Г.
В задании, если будет несколько вариантов кодовых слов, то требуется указать именно наименьшее из них.
В нашем случае – это однозначно – 001, так как оно будет меньше, чем 011.
Ответ будет 001.
Решение задач № 4 ЕГЭ
(кодирование и декодирование информации)
Решим несколько видов задания № 4 ЕГЭ и ранних версий и демоверсии 2022 года.
Задание 1 (демоверсия 2022 года)
Л = 00
М= 01
Н = 11
П =
Р=
Условие Фано звучит следующим образом: ни одно кодовое слово не может являться началом другого кодового слова.
Это задание удобнее всего решать, используя бинарные деревья.
Бинарные деревья могут начинаться либо с нуля, либо с единицы. Соответственно, из каждого нуля или единицы может выходить еще ноль или единица. Таким образом, это визуально помогает нам определить, какое кодовое слово мы ищем. При этом соблюдается условие Фано.
Построим два маленьких дерева, которые начинаются с нуля и с единицы.
И м ы видим, что, если мы выбираем первое дерево, то код 01 принадлежит букве М и дальше мы идти не можем.
Остается второе бинарное дерево, которое начинается с 1. На втором бинарном дереве сразу же занята буква Н (11)
Достраиваем второе бинарное дерево со стороны ветки 10 и получаем два дополнительного кода: 100 и 101.
Так как для буквы П нужен код с наименьшим числовым значением, то определяем П как 100. Тогда для буквы Р будет определен код 101.
Разбор нескольких типов задач (№4) из предыдущих версий ЕГЭ
Разберем несколько типов заданий из предыдущих версий ЕГЭ.
Начнем с более простых заданий. Если в задании используется слово «декодирование», это уже значит, что нужно использовать условие Фано.
Задание 2
Найти D — 0
Опять применяем метод бинарных деревьев. Рассматриваем букву B – 0. Дальше не имеет смысла идти по данному бинарному дереву, так как условие Фано не сможет быть выполнено, т.к. 0 будет являться началом других недостающих кодовых слов.
Это простая задача, т.к. будет одно бинарное дерево, которое начинается с 1.
Выделяем те коды, которые уже заняты:
Отметили А и В, — дальше идти по данной ветке нет смысла. Что мы можем взять для буквы D? Это будет 10. Она подходит под условие Фано и является наименьшим, т.к. дальше мы можем взять 100,101.
Ответ: кодовое слово для буквы D – 10.
Задание 3
П- 100
О-0
С- ?
Т — 111
Строим бинарное дерево и отметим те буквы, которые уже существуют:
Для буквы С есть выбор, либо 101, либо 110.
Так как требуется код с наименьшим числовым значением, так что выбираем 101.
Ответ: 101
Задание 4
Данная задача немного сложнее, так как присутствует неравномерный двоичный код и условие Фано. В данной задаче значительно больше букв.
А -11
В — 101
С — 0
D —
E —
F —
Многие спрашивают, зачем нам находить буквы D и Е, если по условию нам надо найти только букву F ? Да, возможно и не надо, однако нам нужно применить условие Фано ко всему нашему набору при поиске необходимой буквы, т.к. все буквы должны удовлетворять условию Фано, а не только искомая. В случае, если мы найдем самый короткий код для буквы F, но не проверим остальные буквы, но может оказаться ответ неверным.
С нулем не будем строить дерево. Построим только с единицы. Выделим уже имеющиеся коды на бинарном дереве. Получаем:
Осталась только одна веточка. Рассмотрим ее. Наша веточка дает возможность кодировать только две буквы, а нам нужно три. Поэтому наше бинарное дерево требует достройки:
И так нам нужно найти самый короткий код для буквы F, но учесть наличие еще двух букв.
Получаем, что самый короткий код 1000 – будет буквой F и для двух других букв: 10011, 10010.
Ответ: 1000
Задание 4
В этой задаче отличается вопрос. Он стоит следующим образом: Какова наименьшая возможная суммарная длина всех четырех кодовых слов?
К-10
Л –
М-
Н-0
Раз у нас есть ноль, то будет одно бинарное дерево, которое начинается с единицы.
Получаем
К-10
Л-110
М-111
Н-0
Для определения суммарной длины всех кодовых слов считаем количество цифр, обозначающих каждое из слов. В результате получаем 9.
Ответ: 9.
Полезное видео по теме могу рекомендовать по ссылке.
Продолжение разбора заданий № 4…..по ссылке на моем сайте
forum Обсуждение (0)
+ Оставить отзывПока нет комментариев
Вы можете задать вопрос по учебному материалу первым!