Разбор 5 задания ЕГЭ 2016 по информатике из демоверсии

Разбор 5 задания ЕГЭ 2016 года по информатике из демоверсии. Это задание на умение кодировать и декодировать информацию (уметь интерпретировать результаты, получаемые в ходе моделирования реальных процессов). Это задание базового уровня сложности. Примерное время выполнения задания 2 минуты.

Задание 5:

По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: ________

Разбор 5 задания ЕГЭ 2016:

Для решения данного задания нужно знать условие Фано.

Условие Фано:
Закодированное сообщение можно однозначно декодировать если никакое кодовое слово не является окончанием другого кодового слова.

Обратное условие Фано:
Закодированное сообщение можно однозначно декодировать с конца, если никакое кодовое слово не является окончанием другого кодового слова.

Начнем проверять по порядку:

0 — быть не может, так как О-0 (также кодовое слово не может начинаться с 0, так как не выполнится условие Фано),

1 — быть не может, так как с единицы начинаются Т-111 и П-100,

10 — быть не может, так как с 10 начинается П-100,

11 — быть не может, так как с 11 начинается Т-111,

100 — быть не может, так как П-100,

101 — подходит, так как выполняется условие Фано,

110 — подходит, так как выполняется условие Фано.

По условию задачи, если слов будет несколько, нужно выбрать код с наименьшим числовым значением — поэтому выбираем 101.

Ответ: 101

Опубликовано: 02.03.2016 Обновлено: 12.03.2020
Поделись с друзьями

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

пятнадцать − 9 =