Буквы кодируют цепочками из нулей и единиц так, чтобы ни одна цепочка не была началом другой — это условие Фано, благодаря ему сообщение читается однозначно. Для части букв коды известны; нужно подобрать остальным самые короткие коды и найти длину кода или всего слова. Базовый уровень, ответ — число, 1 балл.
| Ответ | число в поле ответа |
|---|---|
| Баллы | 1 балл |
| Проверяет | умение кодировать и декодировать сообщения двоичным кодом, который читается однозначно |
| Сколько времени закладывать | около 2 минут по спецификации ФИПИ |
Условие. Сообщения из букв А, К, Л, М, П передают двоичным кодом, который удовлетворяет условию Фано. Известны коды трёх букв: Л — 00, П — 01, К — 110. Коды букв А и М подбирают так, чтобы слово ЛАМПА заняло как можно меньше двоичных знаков. Сколько двоичных знаков займёт это слово?
Ответ: 11
Условие.
Для букв Б, Г, Л используются кодовые слова 000, 11, 100. Для буквы Д нужно выбрать кодовое слово наименьшей длины, при котором код по-прежнему удовлетворяет условию Фано (ни одно кодовое слово не является началом другого). Какова длина такого слова?
Решение.
Кратчайшее свободное слово: 01. Все слова длины 1 и короче конфликтуют с выданными кодами: каждое либо начинается с одного из них, либо само служит началом одного из них.
Проверка: 01 не начинается ни с одного из кодов 000, 11, 100, и ни один из них не начинается с 01.
Ответ: 2
Условие.
Сообщения из букв А, В, Н, О, Р передают двоичным кодом, для которого выполнено условие Фано (ни одно кодовое слово не является началом другого). Коды трёх букв уже выбраны:
| Буква | Код |
|---|---|
| В | 10 |
| Н | 01 |
| Р | 110 |
Коды букв А и О можно выбрать любыми, лишь бы условие Фано не нарушилось. Какое наименьшее количество двоичных знаков может занять закодированное слово «ВОРОНА»?
Решение.
Столько раз каждая буква входит в слово «ВОРОНА».
Лучшая пара свободных слов: более короткое достаётся букве О — она встречается чаще.
Длины кодов по буквам слова.
Ответ: 14
Условие.
Для букв Б, Г, Д используются кодовые слова 1, 00, 011. Для буквы А нужно выбрать кодовое слово наименьшей длины, при котором код по-прежнему удовлетворяет условию Фано (ни одно кодовое слово не является началом другого). Какова длина такого слова?
Решение.
Кратчайшее свободное слово: 010. Все слова длины 2 и короче конфликтуют с выданными кодами: каждое либо начинается с одного из них, либо само служит началом одного из них.
Проверка: 010 не начинается ни с одного из кодов 1, 00, 011, и ни один из них не начинается с 010.
Ответ: 3
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.