Задание 4. Кодирование и декодировании информации. Условие Фано. ЕГЭ 2026 по информатике
Средний процент выполнения: 83%
Ответом к заданию 4 по информатике может быть цифра (число) или слово.
Алгоритм решения задания 4:
- Внимательно прочитай условие и определи, что требуется: кодирование или декодирование.
- Выясни правило кодирования, указанное в задании (алфавит, длина кода, соответствия).
- Если требуется кодирование, замени каждый символ исходного сообщения его кодом.
- Если требуется декодирование, разбей кодированное сообщение на элементы по правилу и восстанови исходные символы.
- Проверь, что преобразование выполнено строго по заданному правилу.
- Убедись, что не пропущены и не добавлены лишние символы.
- Запиши полученный результат в требуемом формате.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З.
Для передачи используется двоичный код, удовлетворяющий условию Фано.
Кодовые слова для некоторых букв известны:
А — 100
Б — 01
В — 000
Г — 001
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: Д, Е, Ж, З.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Известные кодовые слова:
А — 100
Б — 01
В — 000
Г — 001
По условию Фано ни одно кодовое слово не может быть началом другого.
Все коды, начинающиеся с 0, использовать нельзя, так как уже существуют коды 000, 001 и 01.
Коды, начинающиеся с 100, также использовать нельзя, так как 100 — код буквы А.
Минимально возможные свободные коды:
101, 110, 111
Это три кода длины 3. Но нужно закодировать 4 буквы, поэтому один код придётся взять большей длины.
Например:
101 — 3 бита
110 — 3 бита
1110 — 4 бита
1111 — 4 бита
Суммарная длина кодовых слов:
3 + 3 + 4 + 4 = 14
Ответ: 14
Задача 2
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Н, К, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы К использовали кодовое слово 01; для буквы Н кодовое слово 11. Какова наименьшая возможная длина кодового слова для последовательности КАВАБАНГА?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Для начала стоит обратить внимание на то, что буква А встречает четыре раза. Поэтому, для получения наименьшей длины, стоит закодировать букву А наименьшим возможным способом. Тогда для А будем использовать код 00
Остальные буквы встречаются по 1 разу, поэтому их размещение не сильно повлияет на результат, главное сделать их минимально возможным.
Тогда получим: А - 00; Б - 100; В - 1010; Г - 1011; К - 01; Н - 11. Посчитаем общую длину для последовательности КАВАБАНГА - 01 00 1010 00 100 00 11 1011 00
Задача 3
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 01; для буквы Б кодовое слово 11. Какова наименьшая возможная длина кодового слова для последовательности ГДЕЕДАДЕДА?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Для начала стоит обратить внимание на то, что буква Д встречает четыре раза. Поэтому, для получения наименьшей длины, стоит закодировать букву Д наименьшим возможным способом. Тогда для Д будем использовать код 10
Е встречается 3 раза, значит для неё нужно найти второй по длине код. Для Е возьмём код 000
Тогда получим: А - 01; Б - 11; В - 0010; Г - 0011; Д - 10; Е - 000. Посчитаем общую длину для последовательности ГДЕЕДАДЕДА - 0011 10 000 000 10 01 10 000 10 01
Задача 4
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Н, К, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы К использовали кодовое слово 01; для буквы Н кодовое слово 11. Какова наименьшая возможная сумма цифр кодового слова для последовательности КАВАБАНГА?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Для начала стоит обратить внимание на то, что буква А встречает четыре раза. Поэтому, для получения наименьшей суммы, стоит закодировать букву А таким возможным способом, чтобы были только 0, тогда и сумма цифр будет равна 0.
Остальные буквы встречаются по 1 разу, поэтому их размещение не сильно повлияет на результат, но главное сделать их минимально возможным по сумме.
Тогда получим: А - 0000; Б - 001; В - 0001; Г - 10; К - 01; Н - 11. Посчитаем общую длину для последовательности КАВАБАНГА - 01 0000 0001 0000 001 0000 11 10 0000
Задача 5
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, Ж, З, И, К. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова:
| Буква | Кодовое слово | Буква | Кодовое слово | |
| А | 1010 | Е | 011 | |
| Б | 1000 | Ж | 0101 | |
| В | 1011 | З | 0100 | |
| Г | 0001 | И | ||
| Д | 1001 | К | 0010 |
Укажите кратчайшее кодовое слово для буквы И, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
По условию задачи кодовое слово буквы И не должно быть началом никакого другого кодового слова, должно быть наименьшей длины и иметь наименьшее числовое значение. Поэтому, учитывая уже заданные кодовые слова, будем перебирать, начиная с наименьшего кода, возможные варианты, проверять их на выполнимость условия Фано.
1) Кодовые слова длины 1: 0, 1 не удовлетворяют условию Фано.
2) Среди кодовых слов длины 2: 00, 01, 10, 11 только кодовое слово 11 удовлетворяет условию Фано. Это слово имеет наименьшую длину и наименьшее числовое значение.
Ответ: 11.
Задача 6
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 00, для буквы Б кодовое слово 01. Укажите наименьшую сумму длин кодовых слов для букв В, Г, Д и Е, при котором код будет допускать однозначное декодирование.
Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки кодированных сообщений.
Решение
Для решения данной задачи рассмотрим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим с каждой левой ветвью 0, а с каждой правой - 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого).
Согласно условию задачи, искомый код должен содержать слова 00 и 01. Значит, узлы, соответствующие этим кодовым словам, должны соответствовать листьям дерева. На основе этих данных построим дерево.
По условию задачи требуется шесть кодовых слов. Для их получения продолжим построение дерева для узлов 11 и 10. Такое построение возможно сделать двумя способами.
а) 
б) 
В первом случае (см. рис. а) для букв В, Г, Д и Е мы получим одно кодовое слово длины 2, одно кодовое слово длины 3 и два кодовых слова длины 4. Суммарная длина этих кодовых слов равна 2 + 3 + 2 · 4 = 13. Во втором случае (см. рис. б) для букв В, Г, Д и Е мы получим четыре кодовых слова длины 3. Суммарная длина всех кодовых слов равна 4 · 3 = 12.
Ответ: 12.
Задача 7
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н, О, П, Р и С. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К, Л, М и Н используются такие кодовые слова: К: 100, Л: 101, М: 110, Н: 111. Укажите кратчайшее кодовое слово для буквы С, которое удовлетворяет всем перечисленным выше условиям. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Все кодовые слова, начинающиеся с 1, заняты из-за символов К, Л, М и Н.
Подберём кратчайшее кодовое слово для буквы С. Однозначное взять не можем, иначе не останется свободных кодовых слов для оставшихся букв. Попробуем взять двузначное. Предположим, С - это 00.
В этом случае для буквы О подойдёт код 010, а для букв П и Р - 0110 и 0111. Все коды при этом будут удовлетворять условию Фано.
Ответ: 00.
Задача 8
По каналу связи передаются сообщения, содержащие только буквы: А, Б и В. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б используются такие кодовые слова: А: 01, Б: 10. Укажите кратчайшее кодовое слово для буквы В, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Решение
Однозначные коды использовать невозможно: 0 является началом для 01, 1 является началом для 101, что противоречит условию Фано.
Из двузначных кодов не заняты и не противоречат условию Фано два: 00 и 11. Выбираем код с наибольшим числовым значением: 11.
Ответ: 11.
Задача 9
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н, О, П, Р и С. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М и Н используются такие кодовые слова: К: 000, Л: 001, М: 010, Н: 011. Остальные кодовые слова подбираются таким образом, чтобы сумма длин всех кодовых слов была наименьшей и соблюдалось условие Фано. Укажите кратчайшее кодовое слово для буквы С, которое удовлетворяет всем перечисленным выше условиям. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Все кодовые слова, начинающиеся с 0, заняты из-за символов К, Л, М и Н.
Минимальная возможная длина символов О, П, Р и С достигается, когда все они трёхзначные: 100, 101, 110, 111. Если мы сократим хотя бы один символ до двузначного, два других придётся удлинять, что приведёт к увеличению суммарной длины.
В этом случае самый короткий код с наименьшим числовым значением - 100.
Ответ: 100.
Задача 10
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: А: 100110, Б: 110010, В: 001011. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Для буквы Г определим кратчайшее кодовое слово, которое вместе с заданными кодовыми словами образует префиксный код (код, в котором ни одно кодовое слово не является началом другого). Для этого будем последовательно рассматривать кодовые слова, начиная со слов длины 1, и определять, образует ли рассматриваемое слово префиксный код.
Кодовые слова 0 и 1 являются началом заданных кодовых слов.
Среди кодовых слов 00, 01, 10 и 11 только кодовое слово 01 не является началом ни одного из заданных кодовых слов. Следовательно, оно и является кратчайшим кодом для буквы Г, при котором код будет допускать однозначное декодирование.
Ответ: 01.
Задача 11
По каналу связи передаются сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В, Г используются такие кодовые слова: А: 000010, Б: 010011, В: 110111, Г: 101011. Укажите кратчайшее кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Кратчайшее кодовое слово с наименьшим числовым значением: 001. Приоритет у длины, а затем числовое значение.
Задача 12
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
| Цвет | Кодовое слово | Цвет | Кодовое слово | |
| Белый | 1000 | Зелёный | ||
| Красный | 010 | Жёлтый | 0011 | |
| Синий | 11 | Чёрный | 000 |
Укажите кратчайшее кодовое слово для кодирования зелёного цвета, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Свободная кратчайшая ветка с наименьшим числовым значением: 011. Приоритет у длины кодового слова, а затем уже наименьшее значение.
Задача 13
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н и О. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К, Л, М и Н используются такие кодовые слова: К: 10, Л: 111, М: 00, Н: 011. Укажите кратчайшее кодовое слово для буквы О, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 является началом для 111, что противоречит условию Фано.
Двузначные коды использовать невозможно: 00 - это М, 01 является началом для 011, 10 - это К, 11 является началом для 111.
Занятые трёхзначные коды: 000 и 001 начинаются с 00, 011 это Н, 100 и 101 начинаются с 10, 111 это Л.
Свободные трёхзначные коды: 010 и 110.
Наибольшее числовое значение 110. Его и выберем для буквы О.
Ответ: 110.
Задача 14
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д и Е. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются такие кодовые слова: А: 00, Б: 11, В: 01, Г: 100. Укажите наименьшую суммарную длину всех кодовых слов.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - является началом для 11.
Двузначные коды использовать невозможно: 00, 01 и 11- это А, В и Б соответственно, 10 является началом для 100 (Г).
Свободный трёхзначный код: 101, но его не хватит для размещения двух букв (Д и Е). Поэтому мы 101 продлим до четырёхзначных вариантов: 1010 - Д, 1011 - Е.
Суммарная длина всех кодовых слов: 2 + 2 + 2 + 3 + 4 + 4 = 17
Ответ: 17.
Задача 15
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н и О. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К, Л и М используются такие кодовые слова: К: 1, Л: 011, М: 010. Укажите кратчайшее кодовое слово для буквы Н, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Решение
Однозначные коды использовать невозможно: 0 является началом для 010, 1 - это А.
Занятые двузначные коды: 01 является началом для 010, 10 и 11 начинаются с 1. 00 свободен, но если его отдать для буквы Н, для буквы О не останется совсем никаких кодовых слов, следовательно, 00 выбрать не можем.
Занятые трёхзначные коды: 010 и 011 заняты буквами М и Л, 100, 101, 110 и 111 начинаются с 1.
Свободные трёхзначные коды: 000 и 001.
Наибольшее числовое значение 001. Его и выберем для буквы Н. Для буквы О остаётся кодовое слово 000.
Ответ: 001.
Задача 16
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В и Г используются такие кодовые слова: А: 10, Б: 11, В: 01, Г: 000. Укажите наименьшую суммарную длину кодовых слов Д и Е.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - является началом для 11.
Двузначные коды использовать невозможно: 10, 01 и 11- это А, В и Б соответственно, 00 является началом для 000 (Г).
Свободный трёхзначный код: 001, но его не хватит для размещения двух букв (Д и Е). Поэтому мы 001 продлим до четырёхзначных вариантов: 0010 - Д, 0011 - Е.
Суммарная длина кодовых слов Д и Е: 4 + 4 = 8
Ответ: 8.
Задача 17
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е и Ж. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются такие кодовые слова: А: 100, Б: 11, В: 00, Г - 010. Укажите наименьшую суммарную длину всех кодовых слов.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - является началом для 11.
Двузначные коды использовать невозможно: 00 и 11- это В и Б соответственно, 01 является началом для 010. 10 является началом для 100.
Свободные трёхзначные коды: 011 и 101, но их не хватит для размещения трёх букв (Д, Е и Ж). Поэтому для буквы Д мы возьмём код 011 (кратчайшее, наименьшее числовое значение), а 101 продлим до четырёхзначных вариантов: 1010 - Е, 1011 - Ж.
Суммарная длина всех кодовых слов: 3 + 2 + 2 + 3 + 3 + 4 + 4 = 21
Ответ: 21.
Задача 18
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Известно, что для двух букв были использованы кодовые слова 00 и 11. Определите наименьшую возможную суммарную длину всех кодовых слов.
Решение
Для решения данной задачи рассмотрим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим с каждой левой ветвью 0, а с каждой правой - 1 (см. рис.). Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого).
Согласно условию задачи, искомый код должен содержать слова 00 и 11. Значит, узлы, соответствующие этим кодовым словам, должны соответствовать листьям дерева. На основе этих данных построим дерево (см. рис.).
По условию задачи требуется шесть кодовых слов. Для их получения продолжим построение дерева для узлов 01 и 10.
Так как количество вхождений каждой из букв в кодируемую последовательность неизвестно, то наименьшая суммарная длина кодовых слов получится, если из каждого узла провести по две ветви (см. рис.).
В этом случае суммарная длина всех кодовых слов равна 2 · 2 + 4 · 3 = 16.
Ответ: 16.
Задача 19
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н, О, П, Р и С. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М и Н используются такие кодовые слова: К: 000, Л: 001, М: 010, Н: 011. Укажите наименьшую возможную сумму длин кодовых слов О, П, Р, С.
Решение
Все кодовые слова, начинающиеся с 0, заняты из-за символов К, Л, М и Н.
Минимальная возможная длина символов О, П, Р и С достигается, когда все буквы принимают длину в три символа: 100, 101, 110, 111. Если мы сократим хотя бы один символ до двузначного, два других придётся удлинять, что приведёт к увеличению суммарной длины.
Суммарная длина в этом случае получится 3+3+3+3 = 12.
Ответ: 12.
Задача 20
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н и О. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К и Л используются такие кодовые слова: К: 00, Л: 1. Укажите наименьшую возможную сумму длин всех кодовых слов.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - это Л (отсюда следует, что не может быть кодовых слов, начинающихся с единицы).
Из двузначных свободен только код 01, но его не хватит для размещения трёх букв (М, Н и О), поэтому продлим его до кодов 010 и 011. Этого также не хватает для трёх кодов. 010 выберем для буквы О (кратчайшее, наименьшее числовое значение), а 011 продлим до четырёхзначных вариантов: 0110 - М, 0111 - Н.
Общая длина всех кодовых слов: 2 + 1 + 4 + 4 + 3 = 14.
Ответ: 14.
Рекомендуемые курсы подготовки
- Узнаешь как кодируется изображение
- Поймешь как решать 7 номер ЕГЭ
- Разберешься с паролями
- Потренируешь 11 и 4 номер ЕГЭ
на бесплатном курсе Турбо ЕГЭ
