Задание 4 ЕГЭ по информатике · 038AED

Минимальная длина кодировки словаПовышеннаяКЭС 2.1КЭС 2.2

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Л, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Ч — 1, Л — 011. Для трёх оставшихся букв А, З и К кодовые слова неизвестны.
Какое количество двоичных знаков потребуется для кодирования слова КАЧАЛКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Показать ответ

Подсказки (3)

Какие кодовые слова могут использоваться в ветви, начинающейся с 0, если кодовые слова Ч и Л уже равны 1 и 011?
Из-за условия Фано кодовые слова для А, З и К не могут быть префиксами друг друга. Минимальные доступные слова имеют длину 3.
В слове КАЧАЛКА буква К встречается 2 раза, А — 3 раза, Ч и Л — по 1 разу. Для каждой из букв А, З и К можно использовать кодовое слово длины 3.

Решение

1. Кодовое слово Ч равно 1, поэтому ни одно другое кодовое слово не может начинаться с 1. Кодовое слово Л равно 011, поэтому в ветви, начинающейся с 0, оно также занимает соответствующую часть дерева.

2. Чтобы закодировать три оставшиеся буквы и сохранить условие Фано, им можно назначить кодовые слова 000, 001 и 010. Все они имеют длину 3 и не являются префиксами друг друга.

3. В слове КАЧАЛКА буква К встречается 2 раза, буква А — 3 раза, буквы Ч и Л — по одному разу. Поэтому длина кодирования равна сумме длин кодовых слов всех букв.

4. Подставляем длины кодовых слов:
2⋅3+3⋅3+1⋅1+1⋅3=18

Частые ошибки

Неверно подсчитывают количество букв К в слове КАЧАЛКА.
Пытаются использовать кодовые слова длины 1 или 2, нарушая условие Фано.
Не учитывают, что буква З в слове КАЧАЛКА не встречается.

Предыдущее Следующее Все задания №4

Нужен репетитор по информатике?

Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.

Репетиторы по информатике

Готовьтесь к ЕГЭ по информатике в Precettore

Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.

Начать бесплатно Я репетитор

Задание 4 ЕГЭ по информатике · 038AED

Похожие задания

Нужен репетитор по информатике?

Готовьтесь к ЕГЭ по информатике в Precettore