Задание 4 ЕГЭ по информатике · 734D40
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1КЭС 2.2
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: А, Б.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
| В | 00 |
|---|---|
| Г | 10 |
| Д | 010 |
| Е | 110 |
| Ж | 0110 |
| З | 111 |
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв?
В ответе запишите суммарную длину кодовых слов для букв: А, Б.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
10
Подсказки (3)
- Представьте известные кодовые слова в виде дерева: новое слово не должно иметь ни одного известного слова своим началом и само не должно быть началом другого слова.
- Ветвь 0110 уже занята, поэтому свободное продолжение начинается с 0111. Чтобы получить два кодовых слова, эту ветвь нужно разделить ещё на один уровень.
- Можно взять кодовые слова 01110 и 01111. Каждое имеет длину 5, поэтому суммарная длина равна 5+5=10.
Решение
1. Проверим свободные ветви дерева кодов. Кодовые слова 00, 10, 010, 110, 0110 и 111 уже заняты, поэтому новое слово не может начинаться с одного из них и не может быть началом другого кодового слова. 2. После слова 0110 остаётся свободная ветвь 0111. Одно кодовое слово можно было бы взять равным 0111, но тогда второго слова в этой ветви разместить нельзя: слово 0111 стало бы его началом. 3. Разделим ветвь 0111 ещё на один уровень. Получаем два кодовых слова: 01110 и 01111. Они имеют одинаковую длину 5 и не являются началами друг друга или известных слов. 4. Находим суммарную длину кодовых слов для букв А и Б. 5+5=10
Частые ошибки
- Выбрать слово 0111 и попытаться добавить второе слово с тем же началом, нарушив условие Фано.
- Не учитывать, что для двух кодовых слов ветвь 0111 нужно разделить ещё на один уровень.
- Сложить сами кодовые слова вместо их длин.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 4E2FD74Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 50D35E4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 5A9AE04Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов · 6B09EA4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · 7410AC4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · D779F54По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов · F9598B
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.