По каналу связи передаются шифрованные сообщение

Обновлено: 07.07.2024

К, У, Ш, А, О, Н, С, И, Л, П, Ю. Для передачи используется неравномерный двоичный код. Для десяти букв используются кодовые слова:
К-00, У-111, Ш-0100, А-0101,О-0110, Н-0111, С-1000, И-1001, Л-1011, П-1100, Ю-.

Укажите кратчайшее кодовое слово для буквы Ю, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением

Приговор Безумцев Просветленный (26627) Павел А. Коржов, Как формируется вопрос, так формируется ответ. Ты в интернете.

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: 1000.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: 151646.

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

ЕГЭ по информатике - Задание 16 (Чемпионская подготовка)

Стас костюшкин 15-10-2020 в 18:48:52

Этого не знаю. Это просто примерные задачи, которые наиболее часто попадаются в книжках и на сайтах по подготовке к ЕГЭ по информатике.

Калужский Александр 15-10-2020 в 18:57:40

Глеб Цыбрий 15-11-2020 в 10:30:33

Ольга Владимировна Сорокина 05-03-2021 в 12:09:08

Ольга Владимировна Сорокина 05-03-2021 в 12:09:14

Буква	Кодовое слово
А	010
Б	1010
В	1100
Г	1111
Д	0011
Е
Ж	0010
З	0111
И	0110
К	1101

Укажите кратчайшее кодовое слово для буквы Е, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Вместе с этой задачей также решают:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать полученную дво…

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную пос…

За правильное выполненное задание получишь 1 балл. На решение отводится примерно 2 минуты.

Для выполнения задания 4 по информатике необходимо знать:

Кодирование - это перевод информации из одной формы представления в другую.

Декодирование - это обратный процесс кодированию.

Кодирование бывает равномерное и неравномерное;

Для однозначного декодирования код должен удовлетворять условию Фано: никакое кодовое слово не может быть началом другого кодового слова.

Задачи для тренировки

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв — П и Р — длины кодовых слов неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Буква	Кодовое слово	Буква	Кодовое слово
А	00	Л	1101
Б	Р	1010
Е	010	С	1110
И	011	Т	1011
К	1111	У	100

Буква	Кодовое слово	Буква	Кодовое слово
А	1001	В
Б	101	Г
Е	001	Д
И	0100	Ж
Л	1111	З

Буква	Кодовое слово	Буква	Кодовое слово
А	00	В	11
Б	Г
Е	Д	101
И	Ж	100
Л	З

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?

Читайте также: