Задание 4 ЕГЭ по информатике · 32DCC7
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1КЭС 2.2
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: А, Б.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| В | 00 |
|---|---|
| Г | 1000 |
| Д | 111 |
| Е | 1001 |
| Ж | 01 |
| З | 110 |
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: А, Б.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
8
Подсказки (3)
- Рассмотрите известные кодовые слова как листья двоичного дерева.
- Ветви 00 и 01 полностью занимают поддерево, начинающееся с 0. В поддереве, начинающемся с 1, свободной остаётся ветвь 101.
- Чтобы разместить два кодовых слова в ветви 101 и сохранить условие Фано, разделите её на 1010 и 1011. Суммарная длина равна 4+4=8.
Решение
1. Построим двоичное дерево кодов. Кодовые слова 00 и 01 полностью занимают ветви, начинающиеся с 0. 2. В ветви, начинающейся с 1, слова 1000 и 1001 занимают подветвь 100, а слова 110 и 111 — подветви 11. Единственная свободная ветвь — 101. 3. Нельзя назначить одно из оставшихся слов 101, поскольку второе слово тогда должно быть его продолжением, а 101 стало бы началом другого кодового слова. Поэтому ветвь 101 делим на два слова одинаковой минимальной длины: 1010 и 1011. 4. Суммарная длина двух кодовых слов равна: 4+4=8
Частые ошибки
- Выбирают кодовые слова 101 и 1010, нарушая условие Фано.
- Считают длину только одного из двух оставшихся кодовых слов.
- Пытаются использовать ветви, уже занятые известными кодовыми словами.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
4По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется…Наименьшая суммарная длина кодов4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 20A17C4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 3B93844Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 4E2FD74Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 50D35E4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 5A9AE0
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.