Решения заданий ФИПИ ЕГЭ по информатике: «Информация и кодирование» — с ответами

Проверим ветви двоичного дерева кодов. Ветви 00, 010, 011, 1000, 1001, 1100, 1101, 1110 и 1111 уже заняты.

Кодовое слово, начинающееся с 00, 010, 011, 1000, 1001, 1100, 1101, 1110 или 1111, нарушит условие Фано. Свободная ветвь начинается с 101.

В слове КАНАВКА буква А встречается 3 раза, К — 2 раза, В и Н — по 1 разу.

Кодовые слова О — 101 и К — 110 имеют длину 3. Чтобы минимизировать общую длину, наиболее часто встречающейся букве А можно назначить код 0.

В слове КАНТАТА буква К встречается 1 раз, Н — 1 раз, А — 3 раза, Т — 2 раза.

Кодовое слово $К=1$ означает, что кодовые слова остальных букв должны начинаться с $0$. С учётом слова $Н=001$ минимальный набор длин для трёх неизвестных кодов можно выбрать как $2$, $4$, $4$: например, $З=01$, $А=0000$, $Т=0001$.

Кодовое слово для буквы A не должно быть началом ни одного из заданных кодовых слов.

Однозначные коды длины 1 невозможны: 0 является началом слов 000, 0010, 0011, 0100 и 0101, а 1 является началом слов 100 и 101.

Код С = 0 означает, что кодовые слова остальных букв должны начинаться с 1. Код К = 1011 фиксирует одну из ветвей дерева.

Чтобы минимизировать длину слова КОСОГОР, код буквы О, встречающейся три раза, нужно сделать как можно короче. Выбираем О = 11.

В слове КОЛОБОК буква О встречается 3 раза, К — 2 раза, Л и Б — по 1 разу.

С учётом уже заданных кодов $00$, $010$ и $111$ минимальные подходящие кодовые слова для К и О можно выбрать как $011$ и $10$. Более короткое слово выгодно назначить букве О, которая встречается чаще.

В слове БАРАБАН буква А встречается 3 раза, Б — 2 раза, Р — 1 раз, Н — 1 раз.

Для минимизации длины сообщения короткое кодовое слово назначается наиболее частой букве А, а остальные кодовые слова выбираются с учётом условия Фано.

Проверим кодовые слова по префиксам. Код 0 невозможен, так как он является началом слова 00, а код 1 — началом слов 100, 1010, 1011, 1101, 1110 и 1111.

Коды длины 2 и 3 также невозможны: их продолжения уже используются существующими кодовыми словами. Например, ветви 010, 011, 100, 101, 110 и 111 заняты или содержат заданные слова.

В слове КОЛОКОЛ буква О встречается 3 раза, а буквы К и Л — по 2 раза. Код буквы К уже задан и имеет длину 2: $К = 11$.

Подберём кратчайшие возможные кодовые слова для остальных букв так, чтобы ни одно слово не было началом другого. Например: $О = 0$, $Л = 101$, $Н = 1000$. Вместе с заданными кодами $Б = 1001$ и $К = 11$ условие Фано выполняется.

Одноразрядные слова 0 и 1 не подходят: 0 уже используется, а 1 является началом кодовых слов 101 и 110.

Двухразрядные слова, начинающиеся с 0, также не подходят, поскольку кодовое слово 0 является их началом. Слово 10 является началом слова 101, а слово 11 является началом слова 110.

Кодовое слово 0 является началом любого слова, начинающегося с 0, поэтому дополнительные кодовые слова не могут начинаться с 0.

В ветви 1 уже используются слова 11, 1000 и 1011. Чтобы не нарушить условие Фано, новые слова должны быть свободными листьями двоичного дерева.

Кодовое слово $1$ запрещает использовать любые новые слова, начинающиеся с $1$, поскольку оно стало бы началом этих слов.$$w_{Д}, w_{Е} \text{ начинаются с } 0$$

Слово $00$ занимает всю ветвь $00$, поэтому новые кодовые слова не могут начинаться с $00$.

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

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

Рассмотрим двоичное дерево кодов. Код 00 уже занят, поэтому все слова, начинающиеся с 00, использовать нельзя. Аналогично ветвь 01 занята словами 010 и 011.

В свободной ветви 10 можно разместить два кодовых слова одинаковой длины: 100 и 101.$$l(100) + l(101) = 3 + 3$$

Кодовое слово 0 занимает всю ветвь, начинающуюся с 0. Кодовое слово 10 занимает ветвь, начинающуюся с 10.

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

Последовательным буквам А, Б, В, Г соответствуют коды:$$\text{А}=00,\quad \text{Б}=01,\quad \text{В}=10,\quad \text{Г}=11$$

Кодируем последовательность ГБВА:$$\text{ГБВА}=11\ 01\ 10\ 00$$

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

Все кодовые слова длины 3 либо уже используются, либо являются префиксами существующих слов: 010, 011, 100 заняты, 101 является префиксом 1011, а слова, начинающиеся с 11, являются префиксами слов 1100, 1101, 1110 или 1111.

Проверим двоичные слова длины 1. Слово 1 является началом всех заданных кодовых слов, а слово 0 можно использовать только в одном кодовом слове: после выбора 0 другие слова, начинающиеся с 0, использовать нельзя.

Два кодовых слова длины 2 можно выбрать как 00 и 01. Ни одно из них не является началом кодовых слов 101, 110 и 1000, и они не являются началами друг друга.$$l(\text{Г}) = 2,\quad l(\text{Д}) = 2$$

Изобразим известные кодовые слова как ветви двоичного дерева. Слово 10 занимает ветвь 10, а слова 0100, 0101 и 011 занимают ветви под началом 01.

Для четырёх оставшихся букв можно выбрать свободные кодовые слова 000, 001, 110 и 111. Ни одно из них не является началом другого и не начинается с уже занятого кодового слова.

Кодовые слова 00, 01 и 11 занимают три ветви двоичного дерева. Чтобы условие Фано выполнялось, неизвестные слова могут располагаться только в ветви 10.

Для трёх кодовых слов в ветви 10 минимально возможные длины — 3, 4 и 4. Более короткое слово длины 3 выгоднее назначить букве, которая встречается чаще всего.