Обратное условие фано решу егэ

Всего: 97    1–20 | 21–40 | 41–60 | 61–80 | 81–97

Добавить в вариант

По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А  — 1, Б – 010, В – 001.

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

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

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

Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.

Цвет Кодовое слово
Белый 0
Зелёный 11111
Красный 1110
Цвет Кодовое слово
Синий
Фиолетовый 11110
Чёрный 10

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

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

Источник: ЕГЭ по информатике 2017. Досрочная волна

По каналу связи передаются сообщения, содержащие только пять букв: П, И, Л, О, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы И используется кодовое слово 1; для буквы О используется кодовое слово 01.

Какова минимальная общая длина кодовых слов для всех пяти букв? Примечание: условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова. Для буквы А − 00, Е  — 010, И  — 011, К  — 1111, Л  — 1101, Р  — 1010, С  — 1110, Т  — 1011, У  — 100.

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

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

Источник: Демонстрационная версия ЕГЭ—2018 по информатике.

По каналу связи передаются сообщения, содержащие только четыре буквы: Р, Е, К, А; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Р, Е используются такие кодовые слова: А: 111, Р: 0, Е: 100.

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

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

По каналу связи передаются сообщения, содержащие только четыре буквы: М, О, Р, Е; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв О, Р, Е используются такие кодовые слова: О: 111, Р: 0, Е: 100.

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

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

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

Буква Кодовое слово
А 11
Б 0010
Г 1011
Е 0011
Буква Кодовое слово
И
М 01
Р 000
Т 1010

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

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

Источник: СтатГрад: Тренировочная работа 28.11.2017 ИН10203

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б , Г , Е , И , М, Р , Т . Для передачи и спользуется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

Буква Кодовое слово
А 0101
Б 1000
Г
Е 011
Буква Кодовое слово
И 00
М 0100
Р 11
Т 1001

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

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

Для передачи данных используется двоичный код. Сообщение содержит только буквы А, Б, В или Г, для букв А, Б и В используются следующие кодовые слова: A  — 0, Б  — 101, В  — 111.

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

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

Источник: ЕГЭ — 2018. Досрочная волна. Вариант 1., ЕГЭ — 2018. Досрочная волна. Вариант 2.

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А  — 0; Б  — 110; В  — 101.

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

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

Источник: ЕГЭ — 2018. Досрочная волна. Вариант 2., ЕГЭ — 2018. Досрочная волна. Вариант 1.

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

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

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

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

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г  — 110, И  — 01, Т  — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН?

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

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

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

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А  — 110, Б  — 01, И  — 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ?

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

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

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

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, О, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б  — 01, Д  — 001, Р  — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВОДОВОРОТ?

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

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

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

Источник: ЕГЭ — 2019. Досрочная волна. Вариант 1.

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

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

Источник: ЕГЭ по информатике 03.07.2020. Основная волна

Всего: 97    1–20 | 21–40 | 41–60 | 61–80 | 81–97

Источник

Тема 4.

Кодирование и декодирование

4

.

04

Обратное условие Фано

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.

Готовиться с нами — ЛЕГКО!

Подтемы раздела

кодирование и декодирование

4.01Кодирование буквенных сообщений в двоичный код

4.02Декодирование двоичных кодов в буквенные сообщения

4.03Построение и исправление кода в кодировании.

4.04Обратное условие Фано

4.05Закодированы все буквы алфавита

Решаем задачи

Марафонец кодирует буквы К, Р, А, Б, Ы неравномерным двоичным кодом, который удовлетворяет обратному условию
Фано. Известно, что букве К соответствует код 00, букве Р — 01, а букве А — 11. Укажите кодовое слово для буквы Б, если
известно, что у него минимальное численное значение.

Показать ответ и решение

Не забываем, что граф у нас «перевёрнутый»!

PIC

Источник

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

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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: 1000.

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

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

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

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

Решение:

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

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

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

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

1 вариант

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

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

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

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

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

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

2 вариант

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

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

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

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

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

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

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

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

Ответ: 22.

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

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

Решение:

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

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

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

Ответ: 151646.

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

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

Здравствуйте, а вот такое задание ПО КАНАЛУ СВЯЗИ ПЕРЕДАЮТСЯ СООБЩЕНИЯ, СОДЕРЖАЩИЕ ТОЛЬКО 4 БУКВЫ : А, Б, В, Г; ДЛЯ ПЕРЕДАЧИ ИСП. ДВОИЧНЫЙ КОД, ДОПУСКАЮЩИЙ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ДЛЯ БУКВ А, Б, В ИСПОЛЬЗУЮТСЯ ТАКИЕ КОДОВЫЕ СЛОВА: А:00011, Б:1001, В: 01100.
УКАЖИТЕ КРАТЧАЙШЕЕ КОДОВОЕ СЛОВО ДЛЯ БУКВЫ Г, ПРИ КОТОРОМ КОД БУДЕТ ДОПУСКАТЬ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ЕСЛИ ТАКИХ КОДОВ НЕСКОЛЬКО, УКАЖИТЕ КОД С НАИМЕНЬШИМ ЧИСЛОВЫМ ЗНАЧЕНИЕМ. В ответе указано число 10. Не могу понять почему. У меня 11.

Здравствуйте, а вот такое задание ПО КАНАЛУ СВЯЗИ ПЕРЕДАЮТСЯ СООБЩЕНИЯ, СОДЕРЖАЩИЕ ТОЛЬКО 4 БУКВЫ : А, Б, В, Г; ДЛЯ ПЕРЕДАЧИ ИСП. ДВОИЧНЫЙ КОД, ДОПУСКАЮЩИЙ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ДЛЯ БУКВ А, Б, В ИСПОЛЬЗУЮТСЯ ТАКИЕ КОДОВЫЕ СЛОВА: А:00011, Б:1001, В: 01100.
УКАЖИТЕ КРАТЧАЙШЕЕ КОДОВОЕ СЛОВО ДЛЯ БУКВЫ Г, ПРИ КОТОРОМ КОД БУДЕТ ДОПУСКАТЬ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ЕСЛИ ТАКИХ КОДОВ НЕСКОЛЬКО, УКАЖИТЕ КОД С НАИМЕНЬШИМ ЧИСЛОВЫМ ЗНАЧЕНИЕМ. В ответе указано число 10. Не могу понять почему. У меня 11.

Ольга Владимировна Сорокина, как я понимаю, суть задания в том, что здесь действует либо прямое, либо обратное условие Фано. (Примечание. Условие Фано означает, что соблюдается одно из двух условий.
Либо никакое кодовое слово не является началом другого кодового слова,
либо никакое кодовое слово не является окончанием другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных
сообщений.)
Поэтому 10 является ответом, так как ни один код для букв не оканчивается на 10 (срабатывает обратное условие Фано)

Источник

Урок посвящен тому, как решать 4 задание ЕГЭ по информатике

Содержание:

  • Кодирование информации
    • Кодирование и расшифровка сообщений
  • Решение 4 заданий ЕГЭ

Кодирование информации

4-е задание: «Кодирование и декодирование информации»

Уровень сложности

— базовый,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 2 минуты.

  
Проверяемые элементы содержания: Умение кодировать и декодировать информацию

До ЕГЭ 2021 года — это было задание № 5 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«Из-за невнимательного чтения условия задания экзаменуемые иногда не замечают, что требуется найти кодовое слово минимальной длины с максимальным (минимальным) числовым значением.

Кроме того, если в задании указано, что несколько букв остались без кодовых слов (как, например, в задании демоварианта), то кодовое слово для указанной буквы должно быть подобрано таким образом, чтобы осталась возможность найти кодовые слова, удовлетворяющие условию Фано, и для других букв. Так, например, если мы букву А закодируем нулём, а букву Б единицей, то букву В мы уже никак не сможем закодировать с соблюдением условия Фано, поэтому длину кодового слова для А или Б следует увеличить»

ФГБНУ «Федеральный институт педагогических измерений»

  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • Кодирование бывает равномерным и неравномерным:
  • при равномерном кодировании всем символам соответствуют коды одинаковой длины;
  • при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
двоичное кодирование

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

Кодирование и расшифровка сообщений

Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.

Для решения задач с декодированием, необходимо знать условие Фано:

Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)

Префиксный код — это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.

  • если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:

    • Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова

    Постфиксный код — это код, в котором ни одно кодовое слово не совпадает с концом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.

    постфиксный код

  • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Однозначное декодирование обеспечивается:

Однозначное декодирование

Однозначное декодирование

Декодирование

Декодирование

Егифка ©:

решение 4 задания ЕГЭ

Задание демонстрационного варианта 2022 года ФИПИ
Плейлист видеоразборов задания на YouTube:

ЕГЭ 4.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

✍ Решение:

  • Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
    • О -> 0 -> 00
В -> 1 -> 01
Д -> 2 -> 10
П -> 3 -> 11
А -> 4 -> 100
  • Теперь закодируем последовательность букв из слова ВОДОПАД:
    • 010010001110010
  • Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:
    • 010 010 001 110 010
 ↓   ↓   ↓   ↓   ↓
 2   2   1   6   2

Результат: 22162

Теоретическое решение ЕГЭ данного задания по информатике, видео:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Рассмотрим еще разбор 4 задания ЕГЭ:

ЕГЭ 4.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

a b c d e
000 110 01 001 10

Какой набор букв закодирован двоичной строкой 1100000100110?

✍ Решение:

  • Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.

    •  
    ✎ 1 вариант решения:

  • Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
    • 110 000 01 001 10
 ↓   ↓   ↓  ↓  ↓
 b   a  c   d  e

Результат: b a c d e.

✎ 2 вариант решения:

    Этот вариант решения 4 задания ЕГЭ более сложен, но тоже верен.

  • Сделаем дерево, согласно кодам в таблице:

    • 1

  • Сопоставим закодированное сообщение с кодами в дереве:
    • 110 000 01 001 10

Результат: b a c d e.

Кроме того, вы можете посмотреть видеорешение этого задания ЕГЭ по информатике (теоретическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Решим следующее 4 задание:

ЕГЭ 4.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).

Определите, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110.

✍ Решение:

  • Рассмотрим пример из условия задачи:
    • Было 2310
Стало 00101001102
  • Где сами цифры исходного числа (выделим их красным цветом):
    •  0010100110  (0010 - 2, 0011 - 3)
  • Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).
  • Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:
  • разбиваем по 5:
    • 01100 01010 01001 00110
  • отбрасываем из каждой группы последний символ:
    • 0110 0101 0100 0011
  • Результат переводим в десятичную систему: 
    • 0110 0101 0100 0011
 ↓    ↓     ↓    ↓
 6    5     4    3

Ответ: 6 5 4 3

Вы можете посмотреть видеорешение этого задания ЕГЭ по информатике, теоретическое решение:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

ЕГЭ 4.4:

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Подобные задания для тренировки

✍ Решение:

✎

1 вариант решения

основан на логических умозаключениях:

  • Найдём самые короткие возможные кодовые слова для всех букв.
  • Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
  • Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
  • Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
  • Суммарная длина всех четырёх кодовых слов равна:
    • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

✎ 2 вариант решения:

  • Будем использовать дерево. Влево откладываем 0, вправо — 1:

    • разбор задания 4 егэ по информатике

  • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
    • (Н) -> 0   -> 1 символ
(К) -> 10  -> 2 символа
(Л) -> 110 -> 3 символа
(М) -> 111 -> 3 символа
  • Суммарная длина всех четырёх кодовых слов равна:
    • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9

4.5:

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: 

А: 101010, 
Б: 011011, 
В: 01000

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

Подобные задания для тренировки

✍ Решение:

  • Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
  • Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

Результат: 00

4.6:

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

А - 01 
Б - 00
В - 11
Г - 100

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

✍ Решение:

  • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:

    • ЕГЭ по информатике 2017 задание ФИПИ вариант 16 решение

  • Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:

    • ЕГЭ по информатике 2017 задание ФИПИ вариант 16

  • Перепишем сверху вниз получившееся кодовое слово для Д: 101

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

4.7: Демоверсия ЕГЭ 2018 информатика (ФИПИ):

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
задание 4 егэ информатика 2018

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

Подобные задания для тренировки

✍ Решение:

  • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.

    • задание 4 егэ по информатике решение

  • При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:

    • разбор 4 задания егэ демоверсия 2018

Результат: 1100

Подробное теоретическое решение данного 4 (раньше №5) задания из демоверсии ЕГЭ 2018 года смотрите на видео:

📹 Видеорешение на RuTube здесь

4.8:

По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова: 

А: 00011 
Б: 111 
В: 1010

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

✍ Решение:

  • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
  • Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).

    • Дерево по условию Фано (однозначно декодируется с начала):
    0

  • Получившееся числовое значение кодового слова для буквы Г — 01.

    • Дерево по обратному условию Фано (однозначно декодируется с конца):
    0

  • Получившееся числовое значение кодового слова для буквы Г — 00.
  • После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.

Результат: 00

4.9:

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Е – 000
Д – 10
К – 111

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.

Подобные задания для тренировки

✍ Решение:

  • С помощью дерева отобразим известные коды для букв:

    • Тренировочный вариант №3 решение

  • В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:

    • 00

  • Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
    • Д   Е   Д   М   А   К   А   Р
10 000 10  001 01  111 01  110
  • Посчитаем количество цифр в итоговом коде и получим 20.

Результат: 20

Смотрите виде решения задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Источник

Содержание:

  • Давайте знакомиться! Меня зовут Александр. Готовлю школьников к успешной сдаче ОГЭ и ЕГЭ по информатике

  • В чем смысл прямого условия Фано?

  • В чем смысл обратного условия Фано?

  • Практическое применение условия Фано

  • Связь условия Фано с другими темами информатики

  • Пример задачи, которую можно эффективно решить, при помощи условия Фано

  • Остались вопросы

Давайте знакомиться! Меня зовут Александр. Готовлю школьников к успешной сдаче ОГЭ и ЕГЭ по информатике

Здравствуйте! Меня зовут Александр Георгиевич и я являюсь московским профессиональным репетитором по информатике и программированию. Вам попалась задача, связанная с кодированием и декодированием информации, и вы запутались в алгоритме ее решения?

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

В чем смысл прямого условия Фано?

Условие Фано названо в честь его создателя, итальянско-американского ученого Роберта Фано. Условие является необходимым в теории кодирования при построении самотерминирующегося кода. Учитывая другую терминологию, такой код называется префиксным.

Сформулировать данное условие можно следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова».

С математической точки зрения условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова BC не существует в коде».

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

Пример $№1$(прямое условие Фано выполняется корректно). Например, нам известны символы некоторого множества ${A, B, C, D}$. Произведем кодирование каждого элемента множества неравномерным кодом, необязательно минимальной длины.

Символ $A$ $B$ $C$ $D$
Код символа $00$ $010$ $1011$ $110$

Проверим код буквы $A = 00$. Как видно, ни один другой символ не начинается на связку битов $00$. Аналогичные умозаключения можно сделать, если провести анализ остальных букв алфавита, т е букв $B$, $C$ и $D$.

Пример $№2$(прямое условие Фано нарушено). Пусть нам дано такое же множество элементов, как и в примере $№1$, то есть работаем с множеством ${A, B, C, D}$. Закодируем элементы этого множества неравномерным кодом, опять-таки, необязательно минимальной длины.

Символ $A$ $B$ $C$ $D$
Код символа $00$ $01$ $101$ $0110$

Очевидно, что в данном случае имеется нарушение прямого условия Фано! Давайте рассмотрим пару элементов множества: ${B, D}$. Начало кода буквы $D$ на $100%$ совпадает с полным кодом буквы $B$: $D =  underbrace{01}_{B}10$.

Такие кодовые слова практически невозможно однозначно декодировать.

В чем смысл обратного условия Фано?

Существует также и обратное правило Фано, формулировка которого звучит следующим образом: «ни одно кодовое слово не может выступать в качестве окончания любого другого кодового слова».

С математической точки зрения обратное условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова CB не существует в коде».

Пример $№3$(обратное условие Фано выполняется корректно). Воспользуемся тем же самым алфавитом, что и в примерах выше: ${A, B, C, D}$. Произведем кодирование элементов данного множества неравномерным кодом, причем необязательно минимальной длины.

Символ $A$ $B$ $C$ $D$
Код символа $100$ $0101$ $11$ $110$

Последовательно проверим полный код буквы $A = 100$, не является ли он окончанием какого-либо другого кодового слова. У буквы $B$ последних $3$ бита равны комбинации $101$, что не совпадает с полным кодом буквы $А$.

Полный код буквы $C$ вообще составляет всего $2$ разряда, — проверка как таковая бессмысленна. Код буквы $D$ также состоит из $3$ бит, равных $110$ и они не равны цепочке $100$.

Делаем вывод, что код буквы $A = 100$ не нарушает обратное правило Фано. Аналогично можно рассмотреть оставшиеся кодовые слова и убедиться в том, что ни одно из них не является окончанием другого кодового слова.

Общий вывод: при таких кодовых словах абсолютно четко выполняется обратное условие Фано.

Пример $№4$(обратное условие Фано нарушено). Рассмотрим следущие элементы множества и их кодовые слова.

Символ $A$ $B$ $C$ $D$
Код символа $0$ $01$ $1001$ $110$

Очевидно, что здесь имеет место быть нарушение обратного условия Фано. Внимательный читатель заметит, что нарушение происходит даже не один раз. wink

Давайте рассмотрим пару элементов множества: ${A, D}$. Конец кода буквы $D$ на $100%$ совпадает с полным кодом буквы $A$: $D =  11underbrace{0}_{A}$. Налицо нарушение обратного правила Фано.

Рассмотрим еще одну пару элементов множества: ${B, C}$. Конец кода буквы $C$ на $100%$ совпадает с полным кодом буквы $B$: $C =  10underbrace{01}_{B}$.

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

Практическое применение условия Фано

Рассмотрим телефонные номера в традиционной телефонии. Если уже существует номер $«102»$, то номер $«1029876»$ попросту не будет выдан. В случае набора первых трех цифр АТС перестает распознавать и принимать все остальные цифры, соединяя с абонентом по номеру $102$.

Однако это правило не является действительным для операторов мобильной связи. Связано это с тем, что для набора номера необходимо нажатие соответствующей клавиши, которой, в основном, является клавиша с изображением зеленой телефонной трубки. По этой причине, номера $«102»$, $«1020»$ и $«1029876»$ могут существовать и быть закрепленными за разными адресатами.

Связь условия Фано с другими темами информатики

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

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

Вы могли уже заметить выше, что правило Фано используется тогда, когда приходится анализировать какие-либо кодовые слова, состоящие из цепочки бит, то есть из цепочки $0$ и $1$.

Поэтому, в обязательном порядке, вам нужно прекрасно понимать, как устроена двоичная система счисления, а также знать переводы чисел, как правило натуральных, из $10$-ной СС в $2$-ную СС и обратно.

Практически во всех заданиях ЕГЭ по информатике, где вам потребуется применить условие Фано, упор делается на однозначное кодирование и декодирование какой-либо информации.

Также условие Фано неразрывно связано с неравномерным кодом. Хочу обратить особое внимание на тот факт, что правило Фано практически не распространяется на случаи, когда информация кодируется равномерным кодом.

То есть вы должны понимать, что условие Фано — инструмент, понимание которого позволит вам быстро и эффективно решать задачи, связанные в $1$-ую очередь с кодированием/декодированием информации в двоичном представлении.

Пример задачи, которую можно эффективно решить, при помощи условия Фано

Условие задачи: дана последовательность, которая состоит из букв $A$, $B$, $C$, $D$ и $E$. Для кодирования приведенной последовательности применяется неравномерный двоичный код, при помощи которого можно осуществить однозначное декодирование.

Буква

$A$

$B$

$C$

$D$

$E$

Двоичный эквивалент

$00$

$010$

$011$

$101$

$111$

Вопрос: есть ли возможность для одного из символов сократить длину кодового слова таким образом, чтобы сохранить возможность однозначного декодирования? При этом коды остальных символов должны остаться неизменными.

Номер варианта

$1$

$2$

$3$

$4$

Ответ

$B – 01$

Не представляется возможным

$C – 01$

$D – 01$

Решение: для того, чтобы сохранилась возможность декодирования, достаточным является соблюдение прямого или обратного условия Фано. Проведем последовательную проверку вариантов $1$, $3$ и $4$. В случае если ни один из вариантов не подойдет, правильным ответом будет вариант $2$ (не представляется возможным).

Вариант $1$. Код: $A — 00$, $B — 01$, $C — 011$, $D — 101$, и $E — 111$. Прямое условие Фано не выполняется: код символа $B$ совпадает с началом кода символа $C$, то есть $C =  underbrace{01}_{B}1$.

Обратное правило Фано не выполняется: код символа $B$ совпадает с окончанием кода символа $D$, то есть $D =  1underbrace{01}_{B}$.

Вариант не является подходящим.

Вариант $3$. Код: $A — 00$, $B — 010$, $C — 01$, $D — 101$, и $E — 111$. Прямое условие Фано не выполняется: код символа $C$ совпадает с началом кода символа $B$, то есть $B =  underbrace{01}_{C}0$.

Обратное условие также не выполняется: код символа $C$ совпадает с окончанием кода символа $D$, то есть $D =  1underbrace{01}_{C}$.

Вариант не является подходящим.

Вариант $4$. Код: $A — 00$, $B — 010$, $C — 011$, $D — 01$, и $E — 111$. Прямое условие Фано не выполняется: код символа $D$ совпадает с началом кода символов $B$ и $C$, то есть: $B =  underbrace{01}_{B}0$ и $C =  underbrace{01}_{B}1$ соответственно.

Однако наблюдается выполнение обратного правила Фано: код символа $D = 01$ не совпадает с окончанием кода всех остальных символов. По этой причине, вариант является подходящим. cool

После проверки вариантов решения задачи на соответствие прямому и обратному условию Фано, было установлено, что правильным является вариант $4$.

Ответ: $4$

P.S. Хочу заметить, что это далеко не единственный способ решения такой задачи. Существует очень эффективный и наглядный способ решения подобных задач с использованием специального двоичного дерева.

А сейчас я вам предлагаю ознакомиться с мультимедийным решением задачи, которая была предложена в демонстрационном варианте ЕГЭ по информатике и ИКТ. Кстати, данная задача относится к типу задач, решаемых с использованием условия Фано.

Остались вопросы

Если после прочтения данной публикации у вас все равно остались какие-то вопросы, непонимания или вы хотите закрепить пройденный материал практическими решениями, то звоните и записывайтесь ко мне на частные уроки по информатике и ИКТ.

Я практик! Это означает, что на своих индивидуальных уроках я показываю своим подопечным самые лучшие методики решения заданий, ориентированных на условие Фано.

Источник

Автор материалов — Лада Борисовна Есакова.

Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.

Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.

Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

Код называется однозначно декодируемым, если любое сообщение, составленное из кодовых слов, можно декодировать единственным способом.

Равномерное кодирование всегда однозначно декодируемо.

Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:

Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.

Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

Кодирование в различных системах счисления

Пример 1.

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление

чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится

1) 22162

2) 1020342

3) 2131453

4) 34017

Решение:

Представим коды указанных букв в дво­ич­ном коде, добавив незначащий нуль для одноразрядных чисел:

О

В

Д

П

А

0

1

2

3

4

00

01

10

11

100

Закодируем по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010.

Разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём каждую тройку в восьмеричное число.

010 010 001 110 010 — 22162.

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

Ответ: 1

Пример 2.

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

            1) D3A6

2) 62032206

3) 6A3D

4) CADBAADC

Решение:

За­ко­ди­ру­ем по­сле­до­ва­тель­ность букв: ВАГ­БА­А­ГВ — 1101001110100110. Разобьем это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём каждую четверку в шестнадцатеричное число:

1101 0011 1010 01102 = D3A616

Пра­виль­ный ответ ука­зан под но­ме­ром 1.

Ответ: 1

Расшифровка сообщений

Пример 3.

Для 5 букв ла­тин­ско­го ал­фа­ви­та за­да­ны их дво­ич­ные коды (для не­ко­то­рых букв – из двух бит, для не­ко­то­рых – из трех). Эти коды пред­став­ле­ны в таб­ли­це:

a

b

c

d

e

100

110

011

01

10

Опре­де­ли­те, какой набор букв за­ко­ди­ро­ван дво­ич­ной стро­кой 1000110110110, если из­вест­но, что все буквы в по­сле­до­ва­тель­но­сти – раз­ные:

1) cbade

2) acdeb

3) acbed

4) bacde

Решение:

Мы видим, что усло­вия Фано и об­рат­ное усло­вие Фано не вы­пол­ня­ют­ся, зна­чит код можно рас­ко­ди­ро­вать не­од­но­знач­но.

Значит, будем перебирать варианты, пока не получим подходящее слово :

1) 100 011 01 10 110

Пер­вая буква опре­де­ля­ет­ся од­но­знач­но, её код 100: a.

Пусть вто­рая буква — с, тогда сле­ду­ю­щая буква — d, потом — e и b.

Такой ва­ри­ант удо­вле­тво­ряет усло­вию, зна­чит, окон­ча­тель­но по­лу­чи­ли ответ: acdeb.

Ответ: 2

Пример 4.

Для пе­ре­да­чи дан­ных по ка­на­лу связи ис­поль­зу­ет­ся 5-би­то­вый код. Со­об­ще­ние со­дер­жит толь­ко буквы А, Б и В, ко­то­рые ко­ди­ру­ют­ся сле­ду­ю­щи­ми ко­до­вы­ми сло­ва­ми: А — 11010, Б — 10111, В — 01101.

При пе­ре­да­че воз­мож­ны по­ме­хи. Од­на­ко не­ко­то­рые ошиб­ки можно по­пы­тать­ся ис­пра­вить. Любые два из этих трёх ко­до­вых слов от­ли­ча­ют­ся друг от друга не менее чем в трёх по­зи­ци­ях. По­это­му если при пе­ре­да­че слова про­изо­шла ошиб­ка не более чем в одной по­зи­ции, то можно сде­лать обос­но­ван­ное пред­по­ло­же­ние о том, какая буква пе­ре­да­ва­лась. (Го­во­рят, что «код ис­прав­ля­ет одну ошиб­ку».) На­при­мер, если по­лу­че­но ко­до­вое слово 10110, счи­та­ет­ся, что пе­ре­да­ва­лась буква Б. (От­ли­чие от ко­до­во­го слова для Б толь­ко в одной по­зи­ции, для осталь­ных ко­до­вых слов от­ли­чий боль­ше.) Если при­ня­тое ко­до­вое слово от­ли­ча­ет­ся от ко­до­вых слов для букв А, Б, В более чем в одной по­зи­ции, то счи­та­ет­ся, что про­изо­шла ошиб­ка (она обо­зна­ча­ет­ся ‘х’).

По­лу­че­но со­об­ще­ние 11000 11101 10001 11111. Де­ко­ди­руй­те это со­об­ще­ние — вы­бе­ри­те пра­виль­ный ва­ри­ант.

1) АххБ

2) АВхБ

3) хххх

4) АВББ

Решение:

Де­ко­ди­ру­ем каж­дое слово со­об­ще­ния. Пер­вое слово: 11000 от­ли­ча­ет­ся от буквы А толь­ко одной по­зи­ци­ей. Вто­рое слово: 11101 от­ли­ча­ет­ся от буквы В толь­ко одной по­зи­ци­ей. Тре­тье слово: 10001 от­ли­ча­ет­ся от любой буквы более чем одной по­зи­ци­ей. Четвёртое слово: 11111 от­ли­ча­ет­ся от буквы Б толь­ко одной по­зи­ци­ей.

Таким об­ра­зом, ответ: АВхБ.

Ответ: 2

Однозначное кодирование

Пример 5.

Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из букв А, Б, В, Г, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный по длине код: A=1, Б=01, В=001. Как нужно за­ко­ди­ро­вать букву Г, чтобы длина кода была ми­ни­маль­ной и до­пус­ка­лось од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на буквы?

1) 0001

2) 000

3) 11

4) 101

Решение:

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

Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.

Ответ: 2

Пример 6.

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв У, Ч, Е, Н, И и К, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный пре­фикс­ный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му остал­ся пре­фикс­ным? Коды осталь­ных букв ме­нять­ся не долж­ны.

Вы­бе­ри­те пра­виль­ный ва­ри­ант от­ве­та.

При­ме­ча­ние. Пре­фикс­ный код — это код, в ко­то­ром ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го; такие коды поз­во­ля­ют од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность.

1) ко­до­вое слово для буквы Е можно со­кра­тить до 01

2) ко­до­вое слово для буквы К можно со­кра­тить до 1

3) ко­до­вое слово для буквы Н можно со­кра­тить до 10

4) это не­воз­мож­но

Решение:

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


 

Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. ко­до­вое слово для буквы Н можно со­кра­тить до 10.

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

Ответ: 3

Благодарим за то, что пользуйтесь нашими публикациями.
Информация на странице «Задача №5. Кодирование в различных системах счисления, расшифровка сообщений, выбор кода.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать необходимые и поступить в ВУЗ или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из данного раздела.

Публикация обновлена:
08.03.2023

Источник



Скачать материал

ЕГЭ-2022Разбор задания 4 ИнформатикаКодирование и декодирование информации



Скачать материал

  • Сейчас обучается 41 человек из 22 регионов

Описание презентации по отдельным слайдам:

  • ЕГЭ-2022Разбор задания 4 ИнформатикаКодирование и декодирование информации

    1 слайд

    ЕГЭ-2022
    Разбор задания 4 Информатика
    Кодирование и декодирование информации

  • ВведениеВ данном уроке мы рассмотрим такие понятия как «Условие Фано» и «Преф...

    2 слайд

    Введение
    В данном уроке мы рассмотрим такие понятия как «Условие Фано» и «Префиксный код» , научимся строить бинарные деревья, а так же рассмотрим разные типы задач на тему «Кодирование и декодирование информации».

  • ТеорияУсловие Фано и Префиксный код

    3 слайд

    Теория
    Условие Фано и Префиксный код

  • Условие ФаноПрямое условие Фано. Неравномерный код может быть однозначно дек...

    4 слайд

    Условие Фано
    Прямое условие Фано.
    Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо другого, более длинного кода.
    Такой код называют «префиксным».

  • Условие ФаноОбратное условие Фано. Неравномерный код может быть однозначно д...

    5 слайд

    Условие Фано
    Обратное условие Фано.
    Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с окончанием (постфиксом) какоголибо другого, более длинного кода.
    Такой код называют «постфиксным».

  • Префиксный кодПрефиксный код— код со словом переменной длины, имеющий такое с...

    6 слайд

    Префиксный код
    Префиксный код— код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово a, то для любой непустой строки b слова ab в коде не существует.

    Например, код, состоящий из слов 0, 10 и 11, является префиксным, и сообщение 01001101110 можно разбить на слова единственным образом:
    0 10 0 11 0 11 10
    Код, состоящий из слов 0, 10, 11 и 100, префиксным не является, и то же сообщение можно трактовать несколькими способами.
    0 10 0 11 0 11 10
    0 100 11 0 11 10

  • Бинарное деревоБинарное дерево— это иерархическая структура данных, в которой...

    7 слайд

    Бинарное дерево
    Бинарное дерево— это иерархическая структура данных, в которой каждый узел имеет значение и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне называется корнем. Узлы, не имеющие потомков называются листьями.

  • Бинарное дерево. ТерминыУзел (вершина) — это каждый элемент бинарного дерева;...

    8 слайд

    Бинарное дерево. Термины
    Узел (вершина) — это каждый элемент бинарного дерева;
    Ветви — связи между узлами;
    Глубина (высота) — наибольший уровень какого-нибудь элемента;
    Лист (терминальный узел) — термин применяется, если элемент не имеет потомков;
    Внутренние узлы — узлы ветвления;
    Степень внутреннего узла — число его потомков (наибольшая степень всех существующих узлов — это степень всего бинарного дерева);
    Длина пути к x — количество ветвей, которые необходимо пройти от корня до текущего узла x. Длина пути самого корня равна нулю, а узел на уровне i обладает длиной пути, которая равна i.

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    9 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    Нарисуем корень нашего дерева из которого будут расти ветви.

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    10 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.

    Вырастим две ветки
    * Из одного корня могу выходить только две ветки

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    11 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    Пронумеруем ветки двоичным кодом слева → направо
    0
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    12 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    Вырастим два листика.
    В дереве появилось два места для двух букв.

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    13 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    Как мы видим место больше нет что бы добавить листик дерева.
    В этом случаем листик превращаем в узел и растим ещё две ветки.

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    14 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    Левый лист превращён в узел и теперь он имеет двух потомков
    0
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    15 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    И пронумерую ветки двоичным кодом
    слева → направо
    0
    1
    0
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    16 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    Теперь есть место для трёх букв.

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    17 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    Это корень сюда букву ставить нельзя
    Это узел сюда букву ставить нельзя
    Это листик сюда можно поставить букву

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    18 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    Места всё ещё не хватает
    Правый лист превращу в узел и выращу две ветки.

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    19 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    Пронумеруем ветки двоичным кодом
    слева → направо
    0
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    20 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    Выращу два листа

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    21 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    Пронумерую двоичным кодом ветки
    слева → направо
    0
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    22 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    Место хватает для 4 букв
    0
    1
    0
    1
    0
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    23 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    0
    1
    Места всё ещё не хватает
    Правый лист превращу в узел и выращу две ветки

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    24 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    0
    1
    Пронумерую двоичным кодом ветки
    слева → направо
    0
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    25 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    0
    1
    0
    1
    0
    1
    0
    Место есть для пяти букв
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    26 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    Заполню листья буквами
    А, Б, В, Г, Д
    1

  • Построение Бинарного дереваЗадача: Необходимо закодировать буква А, Б, В, Г,...

    27 слайд

    Построение Бинарного дерева
    Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
    Бинарное дерево закончено
    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1

  • Найти Код символа с помощью бинарного дерева

    28 слайд

    Найти Код символа с помощью бинарного дерева

  • Код символа по бинарному деревуДля того что бы найти код символа посмотрим на...

    29 слайд

    Код символа по бинарному дереву
    Для того что бы найти код символа посмотрим на наш корень
    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1

  • Код символа по бинарному деревуВГД010101АБ01Что бы добрать до листика А от ко...

    30 слайд

    Код символа по бинарному дереву
    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Что бы добрать до листика А от корня – необходимо двигаться по левой стороне.

  • Код символа по бинарному деревуВГД010101АБ01От корня спускаюсь в левый узел....

    31 слайд

    Код символа по бинарному дереву
    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    От корня спускаюсь в левый узел.
    Запишу в таблицу нумерацию ветки от корня к узлу.

  • Код символа по бинарному деревуВГД010101АБ01От узла спускаюсь ниже на 1 урове...

    32 слайд

    Код символа по бинарному дереву
    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    От узла спускаюсь ниже на 1 уровень в левый узел.
    Запишу в таблицу нумерацию ветки от узла к узлу.

  • Код символа по бинарному деревуВГД010101АБ01От узла спускаюсь в листик А. Зап...

    33 слайд

    Код символа по бинарному дереву
    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    От узла спускаюсь в листик А.
    Запишу в таблицу нумерацию ветки от узла к листику А.

  • Код символа по бинарному деревуВГД010101АБ01Получился маршрут от корня до лис...

    34 слайд

    Код символа по бинарному дереву
    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Получился маршрут от корня до листика А которые равен 000.

  • ВГД010101АБ01Код символа по бинарному деревуАналогично найду код символа Б.

    35 слайд

    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Код символа по бинарному дереву
    Аналогично найду код символа Б.

  • ВГД010101АБ01Код символа по бинарному дереву

    36 слайд

    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Код символа по бинарному дереву

  • ВГД010101АБ01Код символа по бинарному дереву

    37 слайд

    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Код символа по бинарному дереву

  • ВГД010101АБ01Код символа по бинарному дереву

    38 слайд

    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Код символа по бинарному дереву

  • ВГД010101АБ01Код символа по бинарному деревуКод для буквы В

    39 слайд

    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Код символа по бинарному дереву
    Код для буквы В

  • ВГД010101АБ01Код символа по бинарному деревуКод для буквы Г

    40 слайд

    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Код символа по бинарному дереву
    Код для буквы Г

  • ВГД010101АБ01Код символа по бинарному деревуКод для буквы Г

    41 слайд

    В
    Г
    Д
    0
    1
    0
    1
    0
    1
    А
    Б
    0
    1
    Код символа по бинарному дереву
    Код для буквы Г

  • Код символа по бинарному дереву

    42 слайд

    Код символа по бинарному дереву

  • Сокращение двоичного кодаТип задачи №1

    43 слайд

    Сокращение двоичного кода
    Тип задачи №1

  • Задача 1Для кодирования некоторой последовательности, состоящей из букв А, Б,...

    44 слайд

    Задача 1
    Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
    Вот этот код: А – 10; Б – 11; В – 000; Г – 001; Д – 010.
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    Коды остальных букв меняться не должны. Если есть несколько вариантов, выберите кодовое слово с минимальным значением.

  • Задача 1Код: А – 10; Б – 11; В – 000; Г – 001; Д – 010. Построим бинарное де...

    45 слайд

    Задача 1
    Код: А – 10; Б – 11; В – 000; Г – 001; Д – 010.

    Построим бинарное дерево.
    Коды листов известны по условию задачи

  • Задача 1Код: А – 10; Б – 11; В – 000; Г – 001; Д – 010. АБ010101ВГ01Д01

    46 слайд

    Задача 1
    Код:
    А – 10;
    Б – 11;
    В – 000;
    Г – 001;
    Д – 010.

    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Д
    0
    1

  • Задача 1Как можно сократить длину кодового слова для буквы Д так, чтобы код п...

    47 слайд

    Задача 1
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Д
    0
    1
    Как видим у этого узла два листочка.
    Левый листок Д, а правый листок пустой.

  • Задача 1Как можно сократить длину кодового слова для буквы Д так, чтобы код п...

    48 слайд

    Задача 1
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Д
    0
    1
    Как видим у этого узла два листочка.
    Левый листок Д, а правый листок пустой.

  • Задача 1Как можно сократить длину кодового слова для буквы Д так, чтобы код п...

    49 слайд

    Задача 1
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Д
    0
    1

    Пустой листочек мы не используем в кодирование сообщений, следовательно его можно отбросить

  • Задача 1Как можно сократить длину кодового слова для буквы Д так, чтобы код п...

    50 слайд

    Задача 1
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Д
    0
    1

  • Задача 1Как можно сократить длину кодового слова для буквы Д так, чтобы код п...

    51 слайд

    Задача 1
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Д
    После порезав ветки узел превратился в листок

  • Задача 1Как можно сократить длину кодового слова для буквы Д так, чтобы код п...

    52 слайд

    Задача 1
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Д
    После порезав ветки узел превратился в листок (одно свободное место)

  • Задача 1Как можно сократить длину кодового слова для буквы Д так, чтобы код п...

    53 слайд

    Задача 1
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Д
    Перемещаем опавшую Д в пустой листок

  • Задача 1Как можно сократить длину кодового слова для буквы Д так, чтобы код п...

    54 слайд

    Задача 1
    Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
    Д
    А
    Б
    0
    1
    0
    1
    0
    1
    В
    Г
    0
    1
    Теперь
    код буквы Д равен 01

  • Ответ Длину кодового слова для буквы Д можно сократить до 01

    55 слайд

    Ответ
    Длину кодового слова для буквы Д
    можно сократить до 01

  • Выбор кода для одной буквыТип задачи №2

    56 слайд

    Выбор кода для одной буквы
    Тип задачи №2

  • Задача 2По каналу связи передаются сообщения, содержащие только шесть букв: У...

    57 слайд

    Задача 2
    По каналу связи передаются сообщения, содержащие только шесть букв: У, Р, А, Е, Г, Э; для передачи используется двоичный код, удовлетворяющий условию Фано.
    Буквы Е, Р, А, Г, У имеют коды 01, 000, 100, 101, 110 соответственно. Укажите код наименьшей длины для буквы Э.
    Если в качестве кода может быть использовано несколько кодов одинаковой длины, выбрать тот, числовое значение которого меньше.

  • Задача 2Буквы Е, Р, А, Г, У имеют коды 01, 000, 100, 101, 110 соответственно....

    58 слайд

    Задача 2
    Буквы Е, Р, А, Г, У имеют коды 01, 000, 100, 101, 110 соответственно.
    Е
    0
    1
    0
    1
    0
    1
    Р
    0
    1
    А
    Г
    0
    1
    У
    1
    0

  • Задача 2Укажите код наименьшей длины для буквы Э.Е010101РЭ01АГ01УЭ10Букву Э м...

    59 слайд

    Задача 2
    Укажите код наименьшей длины для буквы Э.
    Е
    0
    1
    0
    1
    0
    1
    Р
    Э
    0
    1
    А
    Г
    0
    1
    У
    Э
    1
    0
    Букву Э можно поставить в один из двух листочков
    001
    111

  • Задача 2Сравним два получившихся числа Для удобства можно перевести в дес...

    60 слайд

    Задача 2
    Сравним два получившихся числа

    Для удобства можно перевести в десятичную систему счисления
    001 2 = 1 10
    111 2 = 7 10

  • Задача 2Сравним два получившихся числа

    61 слайд

    Задача 2
    Сравним два получившихся числа

  • Задача 2Сравним два получившихся числа 1 меньше 7, следовательно 001 мень...

    62 слайд

    Задача 2
    Сравним два получившихся числа

    1 меньше 7, следовательно 001 меньше 111
    Ответ: код наименьшей длины для буквы Э — 001

  • Помехоустойчивые кодыТип задачи №3

    63 слайд

    Помехоустойчивые коды
    Тип задачи №3

  • Задача 3По каналу связи с помощью равномерного двоичного кода передаются сооб...

    64 слайд

    Задача 3
    По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы: А, Б, В, Г.
    Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех.
    Для кодирования букв Б, В, Г используются 5-битовые кодовые слова: Б – 00001, В – 01111, Г – 10110.
    5-битовый код для буквы А начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы А.

  • Задача 3Пример0 0 0 0 1кодовое словопозиция

    65 слайд

    Задача 3
    Пример
    0 0 0 0 1
    кодовое слово
    позиция

  • Задача 3Сравним позиции кодовых слов Б, В, Г с позициями кодового слова А

    66 слайд

    Задача 3
    Сравним позиции кодовых слов Б, В, Г с позициями кодового слова А

  • Задача 3Сравним первые позиции кодовых слов А и Б1 01 = 0 ?

    67 слайд

    Задача 3
    Сравним первые позиции
    кодовых слов А и Б
    1 0
    1 = 0 ?

  • Задача 3Сравним первые позиции кодовых слов А и В1 01 = 0 ?

    68 слайд

    Задача 3
    Сравним первые позиции кодовых слов А и В
    1 0
    1 = 0 ?

  • Задача 3Сравним первые позиции кодовых слов А и Г 1 11 = 1 ?

    69 слайд

    Задача 3
    Сравним первые позиции кодовых слов А и Г
    1 1
    1 = 1 ?

  • Задача 3Теперь сравниваем последние позиции

    70 слайд

    Задача 3
    Теперь сравниваем последние позиции

  • Задача 30110? А=Б 0=1? А=В 0=1? А=Г 0=0

    71 слайд

    Задача 3
    0
    1
    1
    0
    ?
    А=Б
    0=1
    ?
    А=В
    0=1
    ?
    А=Г
    0=0

  • Задача 3

  • Задача 3У кодового слова буква Б сошлись две позиции. По условию: любые два с...

    73 слайд

    Задача 3
    У кодового слова буква Б сошлись две позиции.
    По условию: любые два слова из набора отличаются не менее чем в трёх позициях.
    У нас уже есть две одинаковые позиции значит остальные три должны быть различные.

  • Задача 3У кодового слова буква Б сошлись две позиции. По условию: любые два с...

    74 слайд

    Задача 3
    У кодового слова буква Б сошлись две позиции.
    По условию: любые два слова из набора отличаются не менее чем в трёх позициях.
    У нас уже есть две одинаковые позиции значит остальные три должны быть различные.

  • Задача 3Если вторая позиция у кодового слова Г равна 0, следовательно вторая...

    75 слайд

    Задача 3
    Если вторая позиция у кодового слова Г равна 0, следовательно вторая позиция у кодового слова А равна НЕ Г (¬ г).
    ¬0 (НЕ 0)

  • Задача 3Если вторая позиция у кодового слова Г равна 0, следовательно вторая...

    76 слайд

    Задача 3
    Если вторая позиция у кодового слова Г равна 0, следовательно вторая позиция у кодового слова А равна НЕ Г (¬ г).
    ¬0 (НЕ 0)

  • Задача 3¬1 (НЕ 1)

    77 слайд

    Задача 3
    ¬1 (НЕ 1)

  • Задача 3¬1 (НЕ 1)

    78 слайд

    Задача 3
    ¬1 (НЕ 1)

  • Задача 3Ответ: кодовое слово для буквы А равно 11000

    79 слайд

    Задача 3
    Ответ: кодовое слово для буквы А равно 11000

  • Выбор кодов для нескольких буквТип задачи №4

    80 слайд

    Выбор кодов для нескольких букв
    Тип задачи №4

  • Задача 4Для кодирования некоторой последовательности, состоящей из букв П, О,...

    81 слайд

    Задача 4
    Для кодирования некоторой последовательности, состоящей из букв П, О, Е, Х, А, Л, И, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.
    Для букв О, Е, А, И использовали соответственно кодовые слова 01, 110, 1010, 001.
    Найдите наименьшую возможную суммарную длину всех кодовых слов.

  • Задача 4Для букв О, Е, А, И использовали соответственно кодовые слова 01, 110...

    82 слайд

    Задача 4
    Для букв О, Е, А, И использовали соответственно кодовые слова 01, 110, 1010, 001.

    О
    0
    1
    0
    1
    0
    1
    И
    0
    1
    Е
    0
    1
    0
    1
    А
    0
    1

  • Задача 4Некоторая последовательность, состоит из букв П, О, Е, Х, А, Л, ИО010...

    83 слайд

    Задача 4
    Некоторая последовательность, состоит из букв П, О, Е, Х, А, Л, И
    О
    0
    1
    0
    1
    0
    1
    П
    И
    0
    1
    Е
    Л
    0
    1
    Х
    0
    1
    А
    0
    1
    Для букв П Х Л нет кода.
    Добавим его самостоятельно.

  • Задача 4Некоторая последовательность, состоит из букв П, О, Е, Х, А, Л, ИО010...

    84 слайд

    Задача 4
    Некоторая последовательность, состоит из букв П, О, Е, Х, А, Л, И
    О
    0
    1
    0
    1
    0
    1
    П
    И
    0
    1
    Е
    Л
    0
    1
    Х
    0
    1
    А
    0
    1
    Оставшийся листик 1011 мы не берём т.к в нём самое большое количество знаков чем в остальных

  • Задача 4Допишем оставшиеся коды.

    85 слайд

    Задача 4
    Допишем оставшиеся коды.

  • Задача 4Подсчитаю количество знаков

    86 слайд

    Задача 4
    Подсчитаю количество знаков

  • Задача 4П+О+Е+Х+А+Л+И = 3+2+3+3+4+3+3 = 21Ответ: наименьшая возможная суммарн...

    87 слайд

    Задача 4
    П+О+Е+Х+А+Л+И = 3+2+3+3+4+3+3 = 21
    Ответ: наименьшая возможная суммарная длина всех кодовых слов равна 21

  • ПримечаниеПредположим для буквы Л выбрали код 1011 вместо кода 111, тогдаО010...

    88 слайд

    Примечание
    Предположим для буквы Л выбрали код 1011 вместо кода 111, тогда
    О
    0
    1
    0
    1
    0
    1
    П
    И
    0
    1
    Е
    0
    1
    Х
    0
    1
    А
    Л
    0
    1
    П+О+Е+Х+А+Л+И = 3+2+3+3+4+4+3 = 22

  • ДекодированиеТип задачи №5

    89 слайд

    Декодирование
    Тип задачи №5

  • Задача 5Заглавные буквы русского алфавита закодированы неравномерным двоичным...

    90 слайд

    Задача 5
    Заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений.
    Известно, что все кодовые слова содержат не меньше двух и не больше трёх двоичных знаков, а слову КАПОТ соответствует код 11000111110011. Какой код соответствует слову ТОК?

  • Задача 5Рассмотрим внимательно код 11000111110011 С первого взгляда можно ска...

    91 слайд

    Задача 5
    Рассмотрим внимательно код 11000111110011
    С первого взгляда можно сказать что количество 1 больше чем количество 0, из чего можно сделать вывод что левая ветка будет иметь минимум третий уровень, т.к. одна буква шифруется тремя знаками.
    Набрасываем бинарное дерево
    1
    1
    0
    1
    0
    0

  • Задача 5Про просмотре кода 1 1 0 0 0 1 1 1 1 1 0 0 1 1 В глаза бросается бол...

    92 слайд

    Задача 5
    Про просмотре кода
    1 1 0 0 0 1 1 1 1 1 0 0 1 1
    В глаза бросается большое скопление 1 в середине.
    1
    1
    0
    1
    0
    0

  • Задача 5Предположим что код 111 - П 1 1 0 0 0 1 1 1 1 1 0 0 1 1 Тогда 1 1 0...

    93 слайд

    Задача 5
    Предположим что код 111 — П
    1 1 0 0 0 1 1 1 1 1 0 0 1 1
    Тогда
    1 1 0 0 0 1 .1 1 1 .1 0 0 1 1

    * Если 111 листок, следовательно 11 и 1 это узел, в которых не может быть букв.

    1
    1
    П
    0
    1
    0
    0

  • Задача 5От 111 справа на лево распределим ещё две буквы под два символа 1 1 0...

    94 слайд

    Задача 5
    От 111 справа на лево распределим ещё две буквы под два символа
    1 1 0 . 0 0 1 . 1 1 1 . 1 0 0 1 1
    Поскольку кодовое слово начинается на К,
    то 110 – К, следовательно 001 – А.
    Дорисовываем дерево.
    *Если 110 или 001 листок,
    следовательно 11 и 1 это узел, в которых не может быть букв.

    1
    1
    К
    П
    0
    1
    0
    0
    0
    1
    А
    0
    1

  • Задача 5Осталось 5 символов которые можно разложить на 100 и 11, или на 10 и...

    95 слайд

    Задача 5
    Осталось 5 символов которые можно разложить на 100 и 11, или на 10 и 011
    1 1 0 . 0 0 1 . 1 1 1 . 1 0 0 1 1
    Листок 100 существует А вот листочка 11 быть не может. Мы уже сказали что это узел, а в узле не может быть буквы. Это вариант вычёркиваем.
    1
    1
    К
    П
    0
    1
    0
    0
    0
    1
    А
    0
    1
    0
    1

  • 0Задача 5Остался вариант 10 и 011 1 1 0 . 0 0 1 . 1 1 1 . 1 0 . 0 1 1 Подстав...

    96 слайд

    0
    Задача 5
    Остался вариант 10 и 011
    1 1 0 . 0 0 1 . 1 1 1 . 1 0 . 0 1 1
    Подставлю буквы соответственно О и Т.
    О
    1
    1
    К
    П
    0
    1
    0
    0
    1
    А
    0
    1
    0
    1
    Т

  • Задача 5Запишем результат в таблицу

    97 слайд

    Задача 5
    Запишем результат в таблицу

  • Задача 5С помощью таблицы закодируем слово ТОК Ответ: слову ТОК соответ...

    98 слайд

    Задача 5
    С помощью таблицы закодируем слово ТОК

    Ответ: слову ТОК соответствует код 01110110

  • Список литературы

    99 слайд

    Список литературы

  • Список литературы1. Учебник для 11 класса : в 2 ч. Ч. 1 / К. Ю. Поляков, Е. А...

    100 слайд

    Список литературы
    1. Учебник для 11 класса : в 2 ч. Ч. 1 / К. Ю. Поляков, Е. А. Ере- мин. — М. : БИНОМ. Лаборатория знаний, 2020
    2. Богомолова О.Б., Усенков Д.Ю. Фано и его «коллеги»: растим дерево. // компьютерные инструменты в школе – 2017 – Выпуск №2 — С. 26-31. Режим доступа: http://ipo.spb.ru/journal/index.php?article/1873/, свободный.
    3. Задачи для подготовки ЕГЭ https://kpolyakov.spb.ru/school/ege/generate.htm

Краткое описание документа:

ЕГЭ-2022 информатикаРазбор задания 4 — Кодирование и декодирование информацииВ материале представлены теория, пять видов задач и список одновной литературы, необходимые для решения задания 4 ЕГЭ информатика.

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 154 718 материалов в базе

  • Выберите категорию:

  • Выберите учебник и тему

  • Выберите класс:

  • Тип материала:

    • Все материалы

    • Статьи

    • Научные работы

    • Видеоуроки

    • Презентации

    • Конспекты

    • Тесты

    • Рабочие программы

    • Другие методич. материалы

Найти материалы

Материал подходит для УМК

  • «Информатика. Углубленный уровень (в2 частях)», Поляков К.Ю., Еремин Е.А.

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

  • 29.10.2021
  • 92
  • 0

«Информатика. Углубленный уровень (в 2-ух частях) », Поляков К.Ю., Еремин Е.А.

«Информатика», Босова Л.Л., Босова А.Ю.

«Информатика», Босова Л.Л., Босова А.Ю.

«Информатика», Босова Л.Л., Босова А.Ю.

«Информатика», Босова Л.Л., Босова А.Ю.

«Информатика», Босова Л.Л., Босова А.Ю.

«Информатика», Босова Л.Л., Босова А.Ю.

Вам будут интересны эти курсы:

  • Курс повышения квалификации «Информационные технологии в деятельности учителя физики»

  • Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»

  • Курс повышения квалификации «Облачные технологии в образовании»

  • Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»

  • Курс профессиональной переподготовки «Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации»

  • Курс повышения квалификации «Введение в программирование на языке С (СИ)»

  • Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»

  • Курс повышения квалификации «Современные тенденции цифровизации образования»

  • Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»

  • Курс повышения квалификации «Применение интерактивных образовательных платформ на примере платформы Moodle»

Источник

Понравилась статья? Поделить с друзьями:
  • Обучение организаторов егэ 2022 платформа для организаторов
  • Обучение написанию сочинения рассуждения огэ 9 класс
  • Обучение написанию сочинения рассуждения на материале публицистического текста проблемного характера
  • Обучение написанию сочинения по картине 5 класс
  • Обучение написанию сочинения на лингвистическую тему 8 класс