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

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

Слова 10 и 11 не являются началами заданных кодовых слов и не имеют общих начал с ними. Их можно назначить буквам Г и Д.

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

Код длины 1, равный 1, не подходит: он является началом кодовых слов 1110 и 1010.

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

Слова длины 3 также невозможны: варианты, начинающиеся с $00$, $010$, $011$, $100$, $101$, $110$ и $111$, конфликтуют с уже заданными кодовыми словами.

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

Для четырёх букв в ветви 00 требуется четыре различных кодовых слова, не являющихся началами друг друга. Минимальный вариант — использовать все четыре продолжения длины 2: 0000, 0001, 0010 и 0011.

Код 0 уже занят буквой В, поэтому кодовое слово для Г не может начинаться с 0.

Коды 10 и 11 длины 2 не подходят: 10 является началом кода 1010, а 11 — началом кода 1100.

Проверим кодовые слова длины 1. Код $0$ является началом кодов $00$, $010$ и $011$, а код $1$ является началом кодов $1000$, $1001$, $1010$, $1011$, $1110$ и $1111$. Поэтому слова длины 1 невозможны.

Кодовые слова длины 2 также невозможны: $00$ уже занято, $01$ является началом кодов $010$ и $011$, $10$ является началом кодов $1000$, $1001$, $1010$ и $1011$, а $11$ является началом кодов $1110$ и $1111$.

Слова 00 и 01 занимают обе ветви, начинающиеся с 0. Поэтому новые кодовые слова не могут начинаться с 0.

Слово 10 нельзя использовать, так как оно является началом слов 1000 и 1001. Слово 1 также нельзя использовать по той же причине.

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

Одноразрядное слово $1$ не подходит: оно будет началом кодовых слов $101$ и $110$. Двухразрядные слова, начинающиеся с $1$, также не подходят: $10$ является началом слова $101$, а $11$ — началом слова $110$.

Рассмотрим дерево двоичных кодов. Кодовые слова 010 и 011 занимают обе ветви после префикса 01, поэтому в ветви 00 для сохранения условия Фано можно разместить два слова 000 и 001.$$l(000)=3,\quad l(001)=3$$

Кодовые слова 1000 и 1001 занимают обе ветви после префикса 100. В другой ветви после 10 можно разместить слово 101, не являющееся началом других кодов.$$l(101)=3$$

Кодовое слово для буквы Т не может быть короче четырёх символов: все возможные слова длины 1–3 либо уже заняты, либо являются началом одного из заданных кодовых слов.

В ветви 10 код 100 уже занят, а код 1010 занят кодом буквы Р. Единственная свободная четырёхзначная ветвь рядом с ним — 1011.

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

В ветви, начинающейся с 1, кодовые слова 1000, 1001 и 101 занимают соответствующие свободные участки. Кодовое слово 110 занимает одну из ветвей после 11.

В слове КАРАВАН буква А встречается три раза, а буквы К, Р, В и Н — по одному разу. Поэтому наиболее короткое доступное кодовое слово выгодно назначить букве А.

С учётом условия Фано и известных кодов Р = 1 и К = 0000 можно, например, построить кодовые слова: А = 01, В = 001, Н = 00010, Д = 00011, К = 0000, Р = 1. Ни одно кодовое слово не является началом другого.

Проверим ветви двоичного дерева кодов. Ветви 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 заняты или содержат заданные слова.