Задание 4 ЕГЭ по информатике · 8171DA
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1КЭС 2.2
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1; для буквы Б — кодовое слово 01.
Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
16
Подсказки (3)
- Какие ветви двоичного дерева кодов остаются свободными после кодовых слов 1 и 01?
- Все четыре оставшихся кодовых слова должны начинаться с 00. Чтобы разместить четыре слова без нарушения условия Фано, нужны четыре листа на следующем уровне.
- Можно выбрать кодовые слова 0000, 0001, 0010 и 0011. Каждое имеет длину 4, поэтому сумма равна 4⋅4=16.
Решение
1. Кодовое слово 1 занимает всю ветвь, начинающуюся с 1. Кодовое слово 01 занимает ветвь 01, поэтому оставшиеся слова могут размещаться только в ветви 00. 2. Для четырёх букв в ветви 00 требуется четыре различных кодовых слова, не являющихся началами друг друга. Минимальный вариант — использовать все четыре продолжения длины 2: 0000, 0001, 0010 и 0011. ∣0000∣=∣0001∣=∣0010∣=∣0011∣=4 3. Сумма длин кодовых слов для букв В, Г, Д, Е равна: 4+4+4+4=16
Частые ошибки
- Учитывают длины кодовых слов 1 и 01, хотя требуется сумма только для букв В, Г, Д, Е.
- Пытаются использовать кодовые слова, начинающиеся с 1 или 01, нарушая условие Фано.
- Выбирают четыре слова внутри ветви 00 с разными длинами, из-за чего сумма получается больше минимальной.
Похожие задания
4Для кодирования некоторой последовательности, состоящей из букв A, B, C, D, E, F, решили использовать…Наименьшая суммарная длина кодов · DA3FC44Для кодирования некоторой последовательности, состоящей из букв A, B, C, D, E, F, решили использовать…Наименьшая суммарная длина кодов · 543CA74Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов4Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.