5 задание егэ информатика

Урок посвящен тому, как решать 5 задание ЕГЭ по информатике

Кодирование информации

5-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 2 минуты, максимальный балл — 1
  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • Кодирование бывает равномерным и неравномерным:
  • при равномерном кодировании всем символам соответствуют коды одинаковой длины;
  • при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
двоичное кодирование

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

Кодирование и расшифровка сообщений

Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.

Для решения задач с декодированием, необходимо знать условие Фано:

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

Префиксный код — это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.

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

    Постфиксный код — это код, в котором ни одно кодовое слово не совпадает с концом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно и только с конца.

    постфиксный код

  • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Однозначное декодирование обеспечивается:

Однозначное декодирование

Однозначное декодирование


Декодирование

Декодирование

Егифка ©:

решение 5 задания ЕГЭ

Решение 5 заданий ЕГЭ


ЕГЭ 5.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.


✍ Решение:

  • Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
  • О -> 0 -> 00
    В -> 1 -> 01
    Д -> 2 -> 10
    П -> 3 -> 11
    А -> 4 -> 100
    
  • Теперь закодируем последовательность букв из слова ВОДОПАД:
  • 010010001110010
    
  • Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:
  • 010 010 001 110 010
     ↓   ↓   ↓   ↓   ↓
     2   2   1   6   2
    

Результат: 22162

Решение ЕГЭ данного задания по информатике, видео:

Рассмотрим еще разбор 5 задания ЕГЭ:

ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

a b c d e
000 110 01 001 10

Какой набор букв закодирован двоичной строкой 1100000100110?


✍ Решение:

  • Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
  •  
    ✎ 1 вариант решения:

  • Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:
  • 110 000 01 001 10
     ↓   ↓   ↓  ↓  ↓
     b   a  c   d  e 
    

Результат: b a c d e.

✎ 2 вариант решения:

    Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.

  • Сделаем дерево, согласно кодам в таблице:
  • 1

  • Сопоставим закодированное сообщение с кодами в дереве:
  • 110 000 01 001 10

Результат: b a c d e.

Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:

Решим следующее 5 задание:

ЕГЭ 5.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).

Определите, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110.


✍ Решение:

  • Рассмотрим пример из условия задачи:
  • Было 2310
    Стало 00101001102
    
  • Где сами цифры исходного числа (выделим их красным цветом):
  •  0010100110  (0010 - 2, 0011 - 3)
  • Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).
  • Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:
  • разбиваем по 5:
  • 01100 01010 01001 00110
  • отбрасываем из каждой группы последний символ:
  • 0110 0101 0100 0011
  • Результат переводим в десятичную систему:
  • 0110 0101 0100 0011
     ↓    ↓     ↓    ↓
     6    5     4    3
    

Ответ: 6 5 4 3

Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:



ЕГЭ 5.4:
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?


✍ Решение:

1 вариант решения основан на логических умозаключениях:

  • Найдём самые короткие возможные кодовые слова для всех букв.
  • Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
  • Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
  • Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
  • Суммарная длина всех четырёх кодовых слов равна:
  • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

2 вариант решения:

  • Будем использовать дерево. Влево откладываем 0, вправо — 1:
  • разбор задания 5 егэ по информатике

  • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
  • (Н) -> 0   -> 1 символ
    (К) -> 10  -> 2 символа
    (Л) -> 110 -> 3 символа
    (М) -> 111 -> 3 символа
    
  • Суммарная длина всех четырёх кодовых слов равна:
  • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9


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

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: А: 101010, Б: 011011, В: 01000.

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


✍ Решение:

  • Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
  • Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

Результат: 00


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

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

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


✍ Решение:

  • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:
  • ЕГЭ по информатике 2017 задание ФИПИ вариант 16 решение

  • Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:
  • ЕГЭ по информатике 2017 задание ФИПИ вариант 16

  • Перепишем сверху вниз получившееся кодовое слово для Д: 101

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:


ЕГЭ по информатике 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

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

5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

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

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

Похожие задания для тренировки


✍ Решение:

  • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
  • задание 5 егэ по информатике решение

  • При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:
  • разбор 5 задания егэ демоверсия 2018

Результат: 1100

Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

Задание 5_9. Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):

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

А: 00011 
Б: 111 
В: 1010

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


✍ Решение:

  • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
  • Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).
  • Дерево по условию Фано (однозначно декодируется с начала):
    0

  • Получившееся числовое значение кодового слова для буквы Г01.
  • Дерево по обратному условию Фано (однозначно декодируется с конца):
    0

  • Получившееся числовое значение кодового слова для буквы Г00.
  • После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.

Результат: 00

Задание 5_10. Тренировочный вариант №3 от 01.10.2018 (ФИПИ):

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Е – 000
Д – 10
К – 111

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.


✍ Решение:

  • С помощью дерева отобразим известные коды для букв:
  • Тренировочный вариант №3 решение

  • В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:
  • 00

  • Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
  • Д   Е   Д   М   А   К   А   Р
    10 000 10  001 01  111 01  110
    
  • Посчитаем количество цифр в итоговом коде и получим 20.

Результат: 20

Смотрите виде решения задания:

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

    Анна

    В последнем задании нет опечатки в ответе? Должно быть, ответ 01

      admin

      01 не может быть, т.к. было бы началом кодового слова B (там ветвь для В продолжается)

        qqq

        началом колового слова В является 1

          admin

          я говорю про обратное условие Фано, если смотреть, начиная с корня дерева

      admin

      Здесь смотрим по обратному условию Фано, т.к. в постановке задания ничего не сказано о том, что надо по условию Фано. А раз ищем наименьшее значение кодового слова, то по обратному условию Фано получается меньше — 00

    Анна

    00 ведь не подходит по условию Фано, т.к. с него начинается кодовое слово «А»: 00011

      admin

      00 подходит по обратному условию Фано

    Петр

    Как понять когда учитывать обратное условие Фано, а когда не учитывать? Например в этом номере «ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 17 (Крылов С.С., Чуркина Т.Е.)» также как и в «Задание 5_9. Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):» ничего не сказано про условие Фанов, хотя во втором вы учитываете обратное условие, что даёт более короткий ответ. Если в первом номере учесть обратное услоие, то кратчайшим кодом буду 101. Как быть?

      admin

      В подобном задании на ЕГЭ явно звучит «должно соблюдаться условие Фано», соответственно проверяем по Фано. Вообще-то, еще ни разу на самом экзамене не попадались задания с обратным условием, только вот в тренировочных вариантах попалось. Я думаю, если такое задание будет на ЕГЭ, то в задании должно как-то прозвучать, что можно использовать и прямое и обратное условие

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

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

*
*

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