4

Теория к заданию 4 ЕГЭ по информатике Умение кодировать и декодировать информацию

Задание 4 проверяет кодирование и декодирование информации. Буквы кодируют неравномерным двоичным кодом, который удовлетворяет условию Фано: никакое кодовое слово не является началом другого. Такой код декодируется однозначно. Главный инструмент — кодовое дерево: известные слова занимают ветки, а свободные ветки показывают, какие слова ещё можно взять.

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

Ответ — число или кодовое слово. Если подходят несколько слов, пишут слово с наименьшим числовым значением. Программа и файл не нужны: дерево рисуют на черновике за пару минут. За верный ответ дают 1 балл.

Пример задания

Открытый банк ФИПИ

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Г, Д, Е и Ж. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

Буква Кодовое слово
А 01
Б 11
В 1010


Какое наименьшее количество двоичных знаков потребуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Г, Д, Е, Ж.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. 

Что учить: от главного к редкому

Главное

Самые частые правила — учите первыми

  1. 1Неравномерный код и условие Фановстречается в каждом задании

Тренировка в формате ЕГЭ

По каналу связи передаются шифрованные сообщения, содержащие только 9 букв: А, Б, В, Г, Д, Е, Ж, 3, И; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква Кодовое слово   Буква Кодовое слово
А 000 Е 11101
Б 010 Ж 110
В 10101 З 1011
Г 00100 И  
Д 01111  


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

Закрепите на настоящих заданиях №4

Решать