Теория к заданию 4 ЕГЭ по информатике Умение кодировать и декодировать информацию
Задание 4 проверяет кодирование и декодирование информации. Буквы кодируют неравномерным двоичным кодом, который удовлетворяет условию Фано: никакое кодовое слово не является началом другого. Такой код декодируется однозначно. Главный инструмент — кодовое дерево: известные слова занимают ветки, а свободные ветки показывают, какие слова ещё можно взять.
Вопрос бывает нескольких видов: кратчайшее кодовое слово для одной буквы, наименьшая сумма длин или наименьшее произведение длин слов для нескольких букв, слово, которое нарушает условие Фано, наименьшая длина сообщения, как в демоверсии 2027 года. В последнем виде кодовое слово нужно каждой букве алфавита, даже если её нет в сообщении.
Ответ — число или кодовое слово. Если подходят несколько слов, пишут слово с наименьшим числовым значением. Программа и файл не нужны: дерево рисуют на черновике за пару минут. За верный ответ дают 1 балл.
Пример задания
Открытый банк ФИПИ
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
| Буква | Кодовое слово |
|---|---|
| А | 01 |
| Б | 11 |
| В | 1010 |
Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Г, Д, Е, Ж.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Что учить: от главного к редкому
Главное
Самые частые правила — учите первыми
Тренировка в формате ЕГЭ
По каналу связи передаются шифрованные сообщения, содержащие только 9 букв: А, Б, В, Г, Д, Е, Ж, 3, И; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
| Буква | Кодовое слово | Буква | Кодовое слово | |
|---|---|---|---|---|
| А | 000 | Е | 11101 | |
| Б | 010 | Ж | 110 | |
| В | 10101 | З | 1011 | |
| Г | 00100 | И | ||
| Д | 01111 | |||
Укажите кратчайшее кодовое слово для буквы И, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.