Тренировка задания 5 ЕГЭ (5.1), включая досрочный вариант

Разбор досрочного ЕГЭ по информатике 2019 от ФИПИ:

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

Буква Кодовое слово Буква Кодовое слово
А 00 Л 1001
Б 1000 Р
Е 010 С 1010
И 011 Т 1101
К 1011 У 111

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


✍ Решение:
 

Ответ: 3120101

Видеоразбор:


ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.):

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

А - 0
Б - 111 
В - 11001 
Г - 11000 
Д - 10

Укажите, каким кодовым словом должна быть закодирована буква Е. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.


✍ Решение:

  • Для того, чтобы выполнялось условие Фано, необходимо, чтобы код буквы Е не совпадал с началом кода любого кодового слова.
  • Поскольку кодовые слова достаточно длинные, то использовать для решения дерево не совсем удобно. Воспользуемся таблицей:
  • таблица для подбора кодовых слов

  • Теперь, начиная с однобитных кодов, и, двигаясь сверху вниз, подбираем такой код, который бы удовлетворял условию Фано. С 0 можно не начинать, так как уже есть код 0 для буквы А:
  • 1   - не подходит (все буквы кроме А начинаются с 1)
    10  - не подходит (соответствует коду Д)
    11  - не подходит (начало кодов Б, В и Г)
    100 - не подходит (код Д - 10 - является началом данного кода)
    101 - не подходит (код Д - 10 - является началом данного кода)
    110 - не подходит (начало кода В и Г)
    111 - не подходит (соответствует коду Б)
    1000 - не подходит (код Д - 10 - является началом данного кода)
    1001 - не подходит (код Д - 10 - является началом данного кода)
    1010 - не подходит (код Д - 10 - является началом данного кода)
    1011 - не подходит (код Д - 10 - является началом данного кода)
    1100 - не подходит (начало кода В и Г)
    1101 - подходит
    

Результат: 1101

Более подробное решение данного задания представлено в видеоуроке:

Поделитесь уроком с коллегами и друзьями:

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

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

*
*

Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить