Разбор 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