ГлавнаяИнформатикаКак решатьДля передачи сообщений нужно использовать неравномерный двоичный код

Для передачи сообщений нужно использовать неравномерный двоичный код

2016-05-29 22:17:37

Формулировка задания: По каналу связи передаются сообщения, содержащие только 4 буквы. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

Задание входит в ЕГЭ по информатике для 11 класса под номером 5 (Кодирование и декодирование информации).

Рассмотрим, как решаются подобные задания на примере.

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

По каналу связи передаются сообщения, содержащие только 4 буквы: А, И, С, Т. В любом сообщении больше всего букв А, следующая по частоте буква — С, затем — И. Буква Т встречается реже, чем любая другая.

Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?

  1. А−0, И−1, С−00, Т−11
  2. С−1, И−0, А−01, Т−10
  3. А−1, И−01, С−001, Т−000
  4. С−0, И−11, А−101, Т−100

Решение:

Проверим каждый код на однозначное декодирование и выберем наиболее оптимальный из них. Оптимальным вариантом будет тот, при котором самые используемые буквы будут иметь самый короткий код.

Вариант 1

Данный код не является однозначно декодируемым, так как 00 можно расшифровать как АА или С, а 11 можно расшифровать как ИИ или Т.

Вариант 2

Данный код не является однозначно декодируемым, так как 10 можно расшифровать как СИ или Т, а 01 можно расшифровать как ИС или А.

Вариант 3

Данный код является однозначно декодируемым, так как он является префиксным (ни одно слово не является началом другого слова).

Вариант 4

Данный код также является однозначно декодируемым, так как он является префиксным (ни одно слово не является началом другого слова).

Значит, нужно сделать выбор между вариантами 3 и 4. Вариант 3 предпочтительнее, так как буква А в сообщениях встречается чаще всего и она имеет самый короткий код именно в варианте номер 3.

Ответ: 3

До экзаменов еще есть время!

Наверх