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