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