Закодированы все буквы алфавита —Каталог задач по ЕГЭ - Информатика

Тема 4. Кодирование и декодирование

4.05 Закодированы все буквы алфавита

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела кодирование и декодирование

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#40708

Для кодирования русского алфавита решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Какова наименьшая возможная суммарная длина кодовых слов для букв Х, Т, О, Н, Ь?

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.

Показать ответ и решение

$PIC$

Нарисуем бинарное дерево. Так как «подвесить» нужно все буквы русского алфавита нам необходимо оставить одну ветку свободной. Тогда ответ равен $2+ 2+ 3 + 3+ 3 = 13$

Ответ: 13

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#30057

По каналу связи передаются сообщения, содержащие только все заглавные буквы русского алфавита. Для передачи используется двоичный код, допускающий однозначное декодирование. Укажите минимальную возможную длину закодированной последовательности ПАРАЛЛЕЛЬ.

Показать ответ и решение

Подвешиваем все буквы на бинарное дерево и не забываем оставить $1$ свободную ветку для остальных букв алфавита.

$PIC$

Складываем длины кодов каждой буквы и получаем ответ: $3+ 2 + 3+ 2+ 2 + 2+ 3+ 2+ 4 = 23$

Ответ: 23

Ошибка.
Попробуйте повторить позже

Задача 3#30055

Машина дикая бешеная совсем взбесилась и закодировала заглавные буквы русского алфавита неравномерным двоичным кодом, удовлетворяющим условию Фано. Он вспомнил, что у всех кодовых слов длина больше $2$ символов, но при том минимально возможная. Слову ОБМАН соответствует код $111101011000001$ . Помогите машине дикой бешеной найти код для слова БОМБА.

Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

Так как длина каждого кодового слова не меньше $2$ символов и минимальна, а букв $5$ , то можно сделать вывод, что длина каждого кодового слова равна $3$ . Разобьём код слова ОБМАН на тройки справа налево: $111 101 011 000 001$ . Таким образом, букве О соответствует код $111$ , Б — $101$ , М — $011$ , А — $000$ , Н — $001$ . Тогда нетрудно записать код слова БОМБА, используя полученные выше коды.

Получаем ответ: $101111011101000$

Ответ: 101111011101000

Ошибка.
Попробуйте повторить позже

Задача 4#29351

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, удовлетворяющим условию Фано, где никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слово ВОЛОС закодировано последовательностью букв соответственно $011$ $100$ $101$ $100$ $001.$ Какое наименьшее число двоичных знаков может содержать код слова ПОВОРОТ?

Показать ответ и решение

$PIC$

Так как в задаче сказано, что слово ВОЛОС закодировано соответственно некоторому кодовому слову, то каждой букве соответствует кодовое слово длины $3$ (они разделены между собой пробелами). Разместим буквы ПбР и Т на самые короткие веточки. Посчитаем общую длину слова ПОВОРОТ: $3+ 3+ 3 +3 + 3+ 3+ 3 = 21$

Ответ: 21

Ошибка.
Попробуйте повторить позже

Задача 5#26083

По каналу связи передаются сообщения, которые могут содержать все строчные и заглавные гласные буквы русского алфавита; для передачи используется двоичный код, допускающий однозначное декодирование. Укажите длину кратчайшего кода для слова ОаоЫАы, при котором будет допускаться однозначное декодирование.

Примечание. Русский алфавит содержит 33 буквы, 10 из которых — гласные.

Показать ответ и решение

$PIC$

Все буквы в слове используются по одному разу, значит, приоритезации нет, поэтому нужно создать $7$ ветвей (одна дополнительная, так как используются все строчные и заглавные буквы алфавита), минимизируя общую длину шести из них. Получим: $2+ 3+ 3 +3 + 3+ 3 = 17$

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 6#26056

По каналу связи передаются сообщения, содержащие строчные и заглавные согласные буквы английского алфавита; для передачи используется двоичный код, допускающий однозначное декодирование. Укажите длину кратчайшего код для слова PRTTST, при котором код будет допускаться однозначное декодирование.

Примечание. Английский алфавит содержит 26 букв, 21 из которых согласная.

Показать ответ и решение

$PIC$

Так как в задаче сказано, что использованы строчные и заглавные согласные буквы английского алфавита, но в слове, длину которого нужно найти, нет строчных букв, значит, нужно оставить одну ветку, с помощью которой будет возможно закодировать хотя бы одну строчную букву. В предложенном слове $4$ буквы - P, R, S, T, значит, веточек должно быть >= $5$ (одна свободная ветка для хотя бы одной строчной буквы). Буква T встречается $3$ раза, значит, чтобы слово имело минимальную длину, её кодовое слово должно быть небольшим. Пусть T - $0$ , добавим ветви к $1$ , получим $10$ и $11$ , но у нас три буквы, продлив еще ветви, получим четыре веточки, на которые и подвесим оставшиеся буквы, одна ветвь останется свободной. Получаем, что кодовое слово для PRTTST имеет длину: $3 + 3+ 1+ 1+ 3 + 1 = 12$

Ответ: 12

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#25764

По каналу связи передаются сообщения, содержащие только десять букв: А, Б, Г, И, М, Н, Р, Т, Ы, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – $101$ , И – $100$ , Р – $1100$ . Какое наименьшее количество двоичных знаков потребуется для кодирования слова АНИМАГ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать ответ и решение

На картинке ниже представлена возможная кодировка букв. Не забываем оставить одно место для оставшихся трёх букв.

$PIC$

Итого, наименьшее количество двоичных знаков, которое потребуется для кодировки слова АНИМАГ равно: $2 + 3+ 3+ 3+ 2 + 3 = 16$

Ответ: 16

Ошибка.
Попробуйте повторить позже

Задача 8#25602

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Показать ответ и решение

$PIC$

Рисуем дерево до глубины 2. Легче все было бы за каждую вершину повесить одну букву и вышла бы длина 8, но нам надо закодировать весь алфавит, поэтому разветвляем одну вершину и за один конец вешаем букву, другой оставляем пустым. Получается, все буквы, кроме одной, имеют длину 2, а эта одна - длину 3. Сумма = 9.

Ответ: 9

Ошибка.
Попробуйте повторить позже

Задача 9#25575

Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известно, что слову КАША соответствует код 011011010. Какое наименьшее количество двоичных знаков может содержать сообщение, кодирующее слово ОСОКА?

Показать ответ и решение

Начнем с расшифровку кодового слова с конца. Букве А не может соответствовать код 0, так как в начале слова есть 0, а в начале должна стоять буква К. 10 подходящий код, но стоит проверить дальше. 010 не может соответствовать А, так как в слове больше нет 010, а буквы А две в слове, 1010 не может по тем же причинам. Далее проверять нет смысла, так как с кодами длиннее мы не уместим вторую букву А. Значит, А - 10. Если перебрать варианты, получается, что 01 10 110 10 единственный подходящий порядок. Выходит, К - 01, А - 10, Ш - 110. Если перерисовать это в дерево, получим, что веточка 00 не занята, буква О встречается два раза, поэтому за 00 подвесим О. Остается разветвить 111 и за 1110 подвесить С. Минимальная длина выходит 12.

Ответ: 12

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел