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

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

ТЕОРИЯ
Условие Фано и Префиксный код

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

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

Префиксный код
Префиксный код— код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

НАЙТИ КОД СИМВОЛА С ПОМОЩЬЮ БИНАРНОГО ДЕРЕВА

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

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

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

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

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

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

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

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

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

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

Код символа по бинарному дереву
Код для буквы В

Код символа по бинарному дереву
Код для буквы Г

Код символа по бинарному дереву
Код для буквы Г

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

СОКРАЩЕНИЕ ДВОИЧНОГО КОДА
Тип задачи №1

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

Задача 1
Код: А – 10; Б – 11; В – 000; Г – 001; Д – 010.
Построим бинарное дерево.
Коды листов известны по условию задачи

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

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

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

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

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

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

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

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

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

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

ВЫБОР КОДА ДЛЯ ОДНОЙ БУКВЫ
Тип задачи №2

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

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

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

Задача 2

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

Задача 2
Сравним два получившихся числа
1 меньше 7, следовательно 001 меньше 111
Ответ: код наименьшей длины для буквы Э - 001

ПОМЕХОУСТОЙЧИВЫЕ КОДЫ
Тип задачи №3

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

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

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

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

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

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

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

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

Задача 3

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

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

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

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

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

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

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

ВЫБОР КОДОВ ДЛЯ НЕСКОЛЬКИХ БУКВ
Тип задачи №4

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

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

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

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

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

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

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

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

ДЕКОДИРОВАНИЕ
Тип задачи №5

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

Задача 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
В глаза бросается большое скопление 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 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 . 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 и 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
Подставлю буквы соответственно О и Т.
О
1
1
К
П
0
1
0
0
1
А
0
1
0
1
Т

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

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

СПИСОК ЛИТЕРАТУРЫ