Задание 4 ЕГЭ по информатике: решения ФИПИ с ответами по шагам

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

Кодовые слова 010 и 011 занимают обе ветви после префикса 01. Поэтому четыре оставшихся кодовых слова должны располагаться в поддереве с префиксом 00.

Кодовое слово длины 1 не подходит: 0 является началом слов 000, 001 и 010, а 1 является началом слова 11.

Проверим слова длины 2. Слова 00 и 01 являются началами уже заданных кодовых слов, а слово 11 совпадает с уже использованным кодовым словом.

Проверим двузначные кодовые слова. Код 00 уже занят, 01 является началом кодов 010 и 011, 10 является началом кодов 1000 и 1001, а 11 является началом кода 111.

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

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

Проверим коды длины 2: 00 уже занято, 01 является началом кодов 010 и 011, 10 является началом кодов 1000, 1001 и 1011, 11 является началом кодов 1101 и 111.

Кодовые слова 000 и 001 занимают две ветви, начинающиеся с 00, а слова 10 и 11 — обе ветви, начинающиеся с 1.

Единственная свободная ветвь минимальной длины — 01. Однако если присвоить 01 букве Д, то любое кодовое слово для Е, начинающееся с 01, будет иметь 01 своим началом, что нарушит условие Фано.

Проверим кодовые слова малой длины. Код длины 1 невозможен, так как $0$ и $1$ являются началами существующих слов.

Коды длины 2 также невозможны: $00$ уже занято, а $01$, $10$ и $11$ являются началами существующих кодовых слов.

Код синего цвета не может начинаться с $0$, так как код $0$ уже является кодовым словом белого цвета.

Код $1$ невозможен, поскольку он был бы началом кодов $10$, $1110$, $11110$ и $11111$.

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

Все кодовые слова длины 2 и 3 также конфликтуют с существующими кодами: 00, 01, 10 и 11 уже являются началами кодовых слов, а их продолжения заняты.

Кодовые слова 00 и 01 уже использованы для букв A и B. Оставшиеся кодовые слова должны удовлетворять условию Фано и не пересекаться с ними по началу.

Распределяя оставшиеся ветви двоичного дерева наиболее экономно, можно получить для букв C, D, E, F длины 2, 3, 3 и 4 соответственно.$$l_C + l_D + l_E + l_F = 2 + 3 + 3 + 4$$

Однозначно декодируемый код по условию Фано не допускает, чтобы одно кодовое слово было началом другого.

Слова, начинающиеся с 0, уже занимают ветви 00, 010 и 011. Слова, начинающиеся с 1, занимают ветви 1000, 1001, 1010, 110, 1110 и 1111.

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

Для длины 2 все варианты также исключаются: 00 уже используется, 01 является началом кодов 010 и 011, 10 — началом кодов 1000, 1001 и 1010, а 11 — началом кодов 1100, 1101 и 111.

Известные кодовые слова занимают ветви 01 и 11, а также две ветви 000 и 001 внутри ветви 00.

Единственная свободная крупная ветвь — 10. Чтобы разместить в ней четыре кодовых слова и сохранить условие Фано, её нужно разделить до четырёх листьев: 1000, 1001, 1010 и 1011.

В слове КАНАДКА буква А встречается 3 раза, К — 2 раза, Н и Д — по 1 разу.$$n(А)=3,\quad n(К)=2,\quad n(Н)=1,\quad n(Д)=1$$

С учётом уже заданных кодовых слов Н = 011 и Р = 0101 подбираем кодовые слова для остальных букв так, чтобы условие Фано выполнялось и общее число знаков было минимальным. Оптимальные длины для букв А, К и Д составляют 1, 2 и 4 знака…

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

Все двоичные слова длины 2 уже заняты или являются началами существующих слов: $00$, $01$, $10$ и $11$.

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

Третье сообщение полностью разбивается на допустимые коды:$$110100001001100111=11\mid01\mid000\mid01\mid001\mid10\mid01\mid11$$

Кодовое слово не может начинаться с 0, поскольку 0 уже является кодовым словом. Поэтому оно должно начинаться с 1.

Начало 10 занято кодовым словом чёрного цвета, а начало 110 — кодовым словом красного цвета. Начало 111 также нельзя использовать целиком, поскольку оно является началом кодовых слов 11110 и 11111.

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

Рассмотрим трёхбитные слова. Слово 100 не является началом ни одного заданного кодового слова и не содержит заданного кодового слова как начало.

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

Коды длины 2 также невозможны: $00$ уже занято, а $01$, $10$ и $11$ являются началами существующих кодовых слов.

Проверим свободные ветви дерева кодов. Кодовые слова 00, 10, 010, 110, 0110 и 111 уже заняты, поэтому новое слово не может начинаться с одного из них и не может быть началом другого кодового слова.

После слова 0110 остаётся свободная ветвь 0111. Одно кодовое слово можно было бы взять равным 0111, но тогда второго слова в этой ветви разместить нельзя: слово 0111 стало бы его началом.

Рассмотрим двоичное дерево кодов. Ветвь $01$ уже занята кодовыми словами $0100$, $0101$ и $011$, ветви $11$ — словами $110$ и $111$, а слово $101$ занимает соответствующую ветвь.

Для одной из оставшихся букв можно выбрать кодовое слово $00$: оно не является началом ни одного известного слова.