Задание 4 ЕГЭ по информатике · CF8A23
Наименьшая суммарная длина кодовПовышеннаяКЭС 2.1КЭС 2.2
По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 1, 00, 0100, 0111 соответственно.
Укажите минимальную сумму длин кодовых слов для букв Д и Е, при которых код будет удовлетворять условию Фано.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Укажите минимальную сумму длин кодовых слов для букв Д и Е, при которых код будет удовлетворять условию Фано.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Показать ответ
8
Подсказки (3)
- Рассмотрите двоичное дерево кодов и найдите свободные ветви, которые не будут иметь общих начал с кодовыми словами 1, 00, 0100 и 0111.
- Так как кодовое слово 1 уже заняло всю ветвь, новые слова должны начинаться с 0. Ветвь 00 занята, а после слов 0100 и 0111 свободные листья появляются только на следующем уровне.
- Можно выбрать кодовые слова 0101 и 0110. Их длины равны 4 и 4, поэтому минимальная сумма равна 4+4=8.
Решение
1. Кодовое слово 1 запрещает использовать любые новые слова, начинающиеся с 1, поскольку оно стало бы началом этих слов.
wД,wЕ начинаются с 0
2. Слово 00 занимает всю ветвь 00, поэтому новые кодовые слова не могут начинаться с 00.
3. В ветви 01 уже находятся слова 0100 и 0111. Слова 010 и 011 использовать нельзя, так как они являются началами существующих кодовых слов.
4. Минимальные свободные слова в этих ветвях имеют вид 0101 и 0110. Оба слова имеют длину 4 и не являются началами друг друга или уже заданных слов.
∣0101∣+∣0110∣=4+4=8
wД,wЕ начинаются с 0
2. Слово 00 занимает всю ветвь 00, поэтому новые кодовые слова не могут начинаться с 00.
3. В ветви 01 уже находятся слова 0100 и 0111. Слова 010 и 011 использовать нельзя, так как они являются началами существующих кодовых слов.
4. Минимальные свободные слова в этих ветвях имеют вид 0101 и 0110. Оба слова имеют длину 4 и не являются началами друг друга или уже заданных слов.
∣0101∣+∣0110∣=4+4=8
Частые ошибки
- Использовать кодовое слово, начинающееся с 1, поскольку слово 1 уже является его началом.
- Выбрать слова 010 или 011, которые являются началами кодовых слов 0100 и 0111.
- Считать длину одного из новых слов равной 3, не проверив условие Фано.
Похожие задания
4По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются шифрованные сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи…Наименьшая суммарная длина кодов · F4F3324По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для…Наименьшая суммарная длина кодов · 0D5D7E4По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для…Наименьшая суммарная длина кодов · CE447D4По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для…Наименьшая суммарная длина кодов · 883C3B4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только цифры 2, 3, 4, 5 и четыре знака арифметических…Наименьшая суммарная длина кодов4По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи…Наименьшая суммарная длина кодов
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.