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

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

А: 101010, 
Б: 011011, 
В: 01000

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

Подобные задания для тренировки


✍ Решение:

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

Результат: 00



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

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

А - 01 
Б - 00
В - 11
Г - 100

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


✍ Решение:

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

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

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

Результат: 101

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



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

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

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

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


✍ Решение:

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

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

Результат: 1100

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



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

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

А: 00011 
Б: 111 
В: 1010

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


✍ Решение:

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

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

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

Результат: 00



5.9: Тренировочный вариант №3 от 01.10.2018 (ФИПИ):

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

Е – 000
Д – 10
К – 111

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


✍ Решение:

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

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

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

Результат: 20

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


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

    Анна

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

      admin

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

        qqq

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

          admin

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

      admin

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

    Анна

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

      admin

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

    Петр

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

      admin

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

    Zvz

    Дед Макар? В задаче о шифровании? Вы серьезно? Ну что ж… Улыбок тебе, Дед Макар.

    natali_z

    в сообщении встречается 10 разных букв. При его передаче использован
    неравномерный двоичный префиксный код. Известны коды трех букв: 11,
    100, 101. Коды остальных семи букв имеют одинаковую длину. Какова
    минимальная суммарная длина всех 10 кодовых слов?
    Если следовать ответу, то все 7 букв имеют длину 3. Но сочетание 3 из 2 — 8 вариантов, два заняты. Где 7 вариант?

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

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

*
*


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