Задание 4. Кодирование и декодировании информации. Условие Фано. ЕГЭ 2026 по информатике
Средний процент выполнения: 84.4%
Ответом к заданию 4 по информатике может быть цифра (число) или слово.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
ДЛЯ 2022
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 01; для буквы Б кодовое слово 11. Какова наименьшая возможная длина кодового слова для последовательности ГДЕЕДАДЕДА?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Для начала стоит обратить внимание на то, что буква Д встречает четыре раза. Поэтому, для получения наименьшей длины, стоит закодировать букву Д наименьшим возможным способом. Тогда для Д будем использовать код 10
Е встречается 3 раза, значит для неё нужно найти второй по длине код. Для Е возьмём код 000
Тогда получим: А - 01; Б - 11; В - 0010; Г - 0011; Д - 10; Е - 000. Посчитаем общую длину для последовательности ГДЕЕДАДЕДА - 0011 10 000 000 10 01 10 000 10 01
Задача 2
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Н, К, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы К использовали кодовое слово 01; для буквы Н кодовое слово 11. Какова наименьшая возможная сумма цифр кодового слова для последовательности КАВАБАНГА?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Для начала стоит обратить внимание на то, что буква А встречает четыре раза. Поэтому, для получения наименьшей суммы, стоит закодировать букву А таким возможным способом, чтобы были только 0, тогда и сумма цифр будет равна 0.
Остальные буквы встречаются по 1 разу, поэтому их размещение не сильно повлияет на результат, но главное сделать их минимально возможным по сумме.
Тогда получим: А - 0000; Б - 001; В - 0001; Г - 10; К - 01; Н - 11. Посчитаем общую длину для последовательности КАВАБАНГА - 01 0000 0001 0000 001 0000 11 10 0000
Задача 3
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Н, К, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы К использовали кодовое слово 01; для буквы Н кодовое слово 11. Какова наименьшая возможная длина кодового слова для последовательности КАВАБАНГА?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Для начала стоит обратить внимание на то, что буква А встречает четыре раза. Поэтому, для получения наименьшей длины, стоит закодировать букву А наименьшим возможным способом. Тогда для А будем использовать код 00
Остальные буквы встречаются по 1 разу, поэтому их размещение не сильно повлияет на результат, главное сделать их минимально возможным.
Тогда получим: А - 00; Б - 100; В - 1010; Г - 1011; К - 01; Н - 11. Посчитаем общую длину для последовательности КАВАБАНГА - 01 00 1010 00 100 00 11 1011 00
Задача 4
По каналу связи передаются сообщения, содержащие только буквы A, B, C, D, E, F, G и H. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв A, B, C и D используются такие кодовые слова: A: 000, B: 001, C: 010, D: 011. Укажите кратчайшее кодовое слово для буквы E, которое удовлетворяет всем перечисленным выше условиям. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Все кодовые слова, начинающиеся с 0, заняты из-за символов A, B, C и D.
Подберём кратчайшее кодовое слово для буквы E. Однозначное взять не можем, иначе не останется свободных кодовых слов для оставшихся букв. Попробуем взять двузначное. Предположим, E - это 10.
В этом случае для буквы F подойдёт код 110, а для букв G и H - 1110 и 1111. Все коды при этом будут удовлетворять условию Фано.
Ответ: 10.
Задача 5
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н и О. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К, Л и М используются такие кодовые слова: К: 1, Л: 011, М: 010. Укажите кратчайшее кодовое слово для буквы Н, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Однозначные коды использовать невозможно: 0 является началом для 010, 1 - это К.
Занятые двузначные коды: 01 является началом для 010, 10 и 11 начинаются с 1. 00 свободен, но если его отдать для буквы Н, для буквы О не останется совсем никаких кодовых слов, следовательно, 00 выбрать не можем.
Занятые трёхзначные коды: 010 и 011 заняты буквами М и Л, 100, 101, 110 и 111 начинаются с 1.
Свободные трёхзначные коды: 000 и 001.
Наименьшее числовое значение 000. Его и выберем для буквы Н. Для буквы О остаётся кодовое слово 001.
Ответ: 000.
Задача 6
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н и О. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К, Л, М и Н используются такие кодовые слова: К: 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.
Задача 7
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н, О, П, Р и С. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М и Н используются такие кодовые слова: К: 000, Л: 001, М: 010, Н: 011. Остальные кодовые слова подбираются таким образом, чтобы сумма длин всех кодовых слов была наименьшей и соблюдалось условие Фано. Укажите кратчайшее кодовое слово для буквы С, которое удовлетворяет всем перечисленным выше условиям. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Все кодовые слова, начинающиеся с 0, заняты из-за символов К, Л, М и Н.
Минимальная возможная длина символов О, П, Р и С достигается, когда все они трёхзначные: 100, 101, 110, 111. Если мы сократим хотя бы один символ до двузначного, два других придётся удлинять, что приведёт к увеличению суммарной длины.
В этом случае самый короткий код с наименьшим числовым значением - 100.
Ответ: 100.
Задача 8
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д и Е. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются такие кодовые слова: А: 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.
Задача 9
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В и Г используются такие кодовые слова: А: 10, Б: 11, В: 01, Г: 000. Укажите наименьшую суммарную длину кодовых слов Д и Е.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - является началом для 11.
Двузначные коды использовать невозможно: 10, 01 и 11- это А, В и Б соответственно, 00 является началом для 000 (Г).
Свободный трёхзначный код: 001, но его не хватит для размещения двух букв (Д и Е). Поэтому мы 001 продлим до четырёхзначных вариантов: 0010 - Д, 0011 - Е.
Суммарная длина кодовых слов Д и Е: 4 + 4 = 8
Ответ: 8.
Задача 10
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н и О. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К и Л используются такие кодовые слова: К: 00, Л: 1. Укажите наименьшую возможную сумму длин всех кодовых слов.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - это Л (отсюда следует, что не может быть кодовых слов, начинающихся с единицы).
Из двузначных свободен только код 01, но его не хватит для размещения трёх букв (М, Н и О), поэтому продлим его до кодов 010 и 011. Этого также не хватает для трёх кодов. 010 выберем для буквы О (кратчайшее, наименьшее числовое значение), а 011 продлим до четырёхзначных вариантов: 0110 - М, 0111 - Н.
Общая длина всех кодовых слов: 2 + 1 + 4 + 4 + 3 = 14.
Ответ: 14.
Задача 11
По каналу связи передаются сообщения, содержащие только буквы A, B, C, D, E, F и G. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв A, B, C и D используются такие кодовые слова: A: 100, B: 00, C: 11, D.: 010. Укажите наименьшую суммарную длину всех кодовых слов.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - является началом для 11.
Двузначные коды использовать невозможно: 00 и 11- это B и C соответственно, 01 является началом для 010. 10 является началом для 100.
Свободные трёхзначные коды: 011 и 101, но их не хватит для размещения трёх букв (E, F и G). Поэтому для буквы E мы возьмём код 011 (кратчайшее, наименьшее числовое значение), а 101 продлим до четырёхзначных вариантов: 1010 - F, 1011 - G.
Суммарная длина всех кодовых слов: 3 + 2 + 2 + 3 + 3 + 4 + 4 = 21
Ответ: 21.
Задача 12
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н, О, П, Р и С. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К, Л, М и Н используются такие кодовые слова: К: 100, Л: 101, М: 110, Н: 111. Укажите кратчайшее кодовое слово для буквы С, которое удовлетворяет всем перечисленным выше условиям. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Все кодовые слова, начинающиеся с 1, заняты из-за символов К, Л, М и Н.
Подберём кратчайшее кодовое слово для буквы С. Однозначное взять не можем, иначе не останется свободных кодовых слов для оставшихся букв. Попробуем взять двузначное. Предположим, С - это 00.
В этом случае для буквы О подойдёт код 010, а для букв П и Р - 0110 и 0111. Все коды при этом будут удовлетворять условию Фано.
Ответ: 00.
Задача 13
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н и О. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К, Л и М используются такие кодовые слова: К: 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.
Задача 14
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н и О. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв К и Л используются такие кодовые слова: К: 00, Л: 1. Укажите кратчайшее кодовое слово для буквы М, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - это Л (отсюда следует, что не может быть кодовых слов, начинающихся с единицы).
Из двузначных свободен только код 01, но его не хватит для размещения трёх букв (М, Н и О), поэтому продлим его до кодов 010 и 011. Этого также не хватает для трёх кодов. 010 выберем для буквы М (кратчайшее, наименьшее числовое значение), а 011 продлим до четырёхзначных вариантов: 0110 - Н, 0111 - О.
Ответ: 010.
Задача 15
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е и Ж. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются такие кодовые слова: А: 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.
Задача 16
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж и З. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются такие кодовые слова: А: 100, Б: 101, В: 110, Г: 111. Остальные кодовые слова подбираются таким образом, чтобы сумма длин всех кодовых слов была наименьшей и соблюдалось условие Фано. Укажите кратчайшее кодовое слово для буквы Ж, которое удовлетворяет всем перечисленным выше условиям. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Все кодовые слова, начинающиеся с 1, заняты из-за символов А, Б, В и Г.
Минимальная возможная длина символов Д, Е, Ж и З достигается, когда все они трёхзначные: 000, 001, 010, 011. Если мы сократим хотя бы один символ до двузначного, два других придётся удлинять, что приведёт к увеличению суммарной длины.
В этом случае самый короткий код с наименьшим числовым значением - 000.
Ответ: 000.
Задача 17
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г и Д. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б и В используются такие кодовые слова: А: 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.
Задача 18
По каналу связи передаются сообщения, содержащие только буквы К, Л, М, Н, О, П, Р и С. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М и Н используются такие кодовые слова: К: 000, Л: 001, М: 010, Н: 011. Укажите наименьшую возможную сумму длин кодовых слов О, П, Р, С.
Решение
Все кодовые слова, начинающиеся с 0, заняты из-за символов К, Л, М и Н.
Минимальная возможная длина символов О, П, Р и С достигается, когда все буквы принимают длину в три символа: 100, 101, 110, 111. Если мы сократим хотя бы один символ до двузначного, два других придётся удлинять, что приведёт к увеличению суммарной длины.
Суммарная длина в этом случае получится 3+3+3+3 = 12.
Ответ: 12.
Задача 19
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж и З. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются такие кодовые слова: А: 000, Б: 001, В: 010, Г: 011. Укажите наименьшую возможную сумму длин всех кодовых слов.
Решение
Все кодовые слова, начинающиеся с 0, заняты из-за символов А, Б, В и Г.
Минимальная возможная длина символов Д, Е, Ж и З достигается, когда все они трёхзначные: 100, 101, 110, 111. Если мы сократим хотя бы один символ до двузначного, два других придётся удлинять, что приведёт к увеличению суммарной длины.
Суммарная длина в этом случае получится 3+3+3+3+3+3+3+3 = 24.
Ответ: 24.
Задача 20
По каналу связи передаются сообщения, содержащие только буквы A, B, C, D и E. Для передачи используется неравномерный двоичный код, удовлетворяющих условию Фано. Для букв A и B используются такие кодовые слова: A: 00, B: 1. Укажите наименьшую возможную сумму длин всех кодовых слов таких, чтобы код удовлетворял условию Фано.
Решение
Однозначные коды использовать невозможно: 0 является началом для 00, 1 - это B (отсюда следует, что не может быть кодовых слов, начинающихся с единицы).
Из двузначных свободен только код 01, но его не хватит для размещения трёх букв (C, D и E), поэтому продлим его до кодов 010 и 011. Этого также не хватает для трёх кодов. 010 выберем для буквы C (кратчайшее, наименьшее числовое значение), а 011 продлим до четырёхзначных вариантов: 0110 - D, 0111 - E.
Общая длина всех кодовых слов: 2 + 1 + 4 + 4 + 3 = 14.
Ответ: 14.
Рекомендуемые курсы подготовки
- Узнаешь всё про кодирование: что это такое и как происходит
- Познакомишься с Условием Фано: как оно примняется и почему важно
- Научишься считать колиечтсво информации и сколько под неё нужно выделить памяти
на бесплатном курсе Турбо ЕГЭ
