Информатика ЕГЭ 5 задание разбор и объяснение

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


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

5-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 2 минуты, максимальный балл — 1

  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • Кодирование бывает равномерным и неравномерным:
  • при равномерном кодировании всем символам соответствуют коды одинаковой длины;
  • при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.
Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

Таким образом, мы получили равномерный код, т.к.

длина каждого кодового слова одинакова для всех кодов (2).

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

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

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

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

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

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

    • Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова

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


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

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

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


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

Егифка ©:

Решение 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 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
    abcde
    0001100100110

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


    ✍ Решение:
    
110 000 01 001 10
 ↓   ↓   ↓  ↓  ↓
 b   a  c   d  e

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

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

      Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.
    • Сделаем дерево, согласно кодам в таблице:

    • Сопоставим закодированное сообщение с кодами в дереве:
    
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:

    • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
    
(Н) -> 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.

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


    ✍ Решение:
    • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:

    • Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:

    • Перепишем сверху вниз получившееся кодовое слово для Д: 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 информатика (ФИПИ):

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

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


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

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

    Результат: 1100

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

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

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

    
А: 00011 
Б: 111 
В: 1010

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


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

      • Дерево по условию Фано (однозначно декодируется с начала):

    • Получившееся числовое значение кодового слова для буквы Г — 01.

      • Дерево по обратному условию Фано (однозначно декодируется с конца):

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

    Результат: 00

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

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

    
Е – 000
Д – 10
К – 111

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


    ✍ Решение:
    • С помощью дерева отобразим известные коды для букв:

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

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

    • Результат: 20

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

    labs.org.ru

    Задание 5 ЕГЭ по информатике 2019: практика и теория

    Статьи

    Среднее общее образование

    Информатика

    Предлагаем вашему вниманию разбор задания № 5 ЕГЭ 2019 года по информатике и ИКТ. Этот материал содержит пояснения и подробный алгоритм решения, а также рекомендации по использованию справочников и пособий, которые могут понадобиться при подготовке к ЕГЭ.

    16 января 2019

    Что нового?

    В предстоящем ЕГЭ не появилось никаких изменений по сравнению с прошлым годом.

    Возможно, вам также будут интересны демоверсии ЕГЭ по математике и физике.

    О нововведениях в экзаменационных вариантах по другим предметам читайте в наших новостях.

    ЕГЭ-2019. Информатика (60×90/16) 10 тренировочных вариантов экзаменационных работ для подготовки к единому государственному экзамену

    Издание содержит 10 типовых тренировочных вариантов экзаменационных работ для подготовки к единому государственному экзамену. Каждый вариант составлен в полном соответствии с требованиями единого государственного экзамена по информатике, включает задания разных типов и уровня сложности. В конце книги даны ответы для самопроверки на все задания.

    Купить

    Источник: сайт ФИПИ

    Демо-КИМ ЕГЭ-2019 по информатике не претерпел никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.

    Мы рассмотрим решение предлагаемого проекта (на момент написания статьи пока еще ПРОЕКТА) КИМ ЕГЭ по информатике.

    Часть 1

    Ответами к заданиям 1–23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

    Задание 5

    Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?

    Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

    Ответ: ___________________________.

    Решение

    Для решения поставленной задачи построим граф:


    Кодовое слово длины 2 – 11, или любое из кодовых слов длины 3, неизбежно станет началом одного из слов длины 4. Выбор длины 4 связан с тем, что была потребность в кодировании четырех букв. Полученные кодовые слова в совокупности дают длину 16.

    Ответ: 16.

    #ADVERTISING_INSERT#

    rosuchebnik.ru

    Как решать 5 задание ЕГЭ по информатике 2018

    5-е задание: «Кодирование и расшифровка сообщений»
    Уровень сложности — базовый,
    Максимальный балл — 1,
    Примерное время выполнения — 2 минуты.

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

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

    Ответ: 22162

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

    ? Видео

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

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

    Ответ: b a c d e

    ✍ Показать решение:
    
110 000 01 001 10
 ↓   ↓   ↓  ↓  ↓
 b   a  c   d  e

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

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

      Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.
    • Сделаем дерево, согласно кодам в таблице:

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

    ? Видео

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

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

    Ответ: 6 5 4 3

    ✍ Показать решение:
    • Рассмотрим пример из условия задачи:
    
Было 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

    ? Видео

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

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

    Ответ: 9

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

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

    • Будем использовать дерево. Влево откладываем 0, вправо — 1:

    • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
    
(Н) -> 0   -> 1 символ
(К) -> 10  -> 2 символа
(Л) -> 110 -> 3 символа
(М) -> 111 -> 3 символа
  • Суммарная длина всех четырёх кодовых слов равна:
    • (Н)1 + (К)2 + (Л)3 + (М)3 = 9
    ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):

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

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

    Ответ: 00

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

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

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

    Ответ: 101

    ✍ Показать решение:
    • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:

    • Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:

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

    ? Видео

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

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

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

    Ответ: 1101

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

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

    ? Видео

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

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

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

    Ответ: 1100

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

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

    ? Видео

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

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

    
А: 00011 
Б: 111 
В: 1010

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

    Ответ: 00

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

      • Дерево по условию Фано (однозначно декодируется с начала):

    • Получившееся числовое значение кодового слова для буквы Г — 01.

      • Дерево по обратному условию Фано (однозначно декодируется с конца):

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

    Результат: 00

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

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

    
Е – 000
Д – 10
К – 111

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

    Ответ: 20

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

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

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

    • Результат: 20

    ? Видео

    labs.org.ru

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

    infedu.ru

    Разбор 5 задания и демоверсия егэ по информатике 2019 ФИПИ

    Задание 5. Кодирование и расшифровка сообщений: демонстрационный вариант егэ информатика 2019; государственный выпускной экзамен 2019; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2019


    *** КАНАЛ ЮТЬЮБ ***
     
    ЕГЭ по информатике -> ЕГЭ 2019 -> ЕГЭ 2019
     


    Разбор 5 задания. Демоверсия егэ по информатике 2019:

    Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10.
    Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?

    Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

    ? Видеоразбор демоверсии егэ 2019

    ✍ Решение: 

    • Построим дерево, в котором расположим известные кодовые слова:

    • По условию Фано получаем, что там, где уже есть лист дерева (кодовое слово), продолжать дерево нельзя. С учетом этого продолжим дерево для остальных кодовых слов:

    • Для удобства подсчета разместили уровни. Теперь подсчитаем сумму длин кодовых слов для 4-х добавленных букв:
    
4(буквы) * 4(уровень) = 16

    Результат: 16

    labs.org.ru

    Разбор 5 задания егэ по информатике 2018

    Задание 5. Кодирование и расшифровка сообщений: Демонстрационный вариант ЕГЭ по информатике 2018; государственный выпускной экзамен 2018; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2018

    *** КАНАЛ ЮТЬЮБ ***
     
    ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 5
     

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

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

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

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

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

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

    Результат: 1100

    Решение 5 задания ЕГЭ по информатике, вариант 1 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты», С.С. Крылов, Т.Е. Чуркина):

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

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

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

    Результат: 01

    ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 5

    labs.org.ru

    Скачать информатика егэ 5 задание разбор — смотерть онлайн

    Опубликовано: меньше минуты назад

    33 728 просмотров

    Опубликовано: меньше минуты назад

    33 699 просмотров

    Опубликовано: меньше минуты назад

    13 630 просмотров

    Опубликовано: 49 лет назад

    38 918 просмотров

    Опубликовано: меньше минуты назад

    29 535 просмотров

    Опубликовано: меньше минуты назад

    62 515 просмотров

    Опубликовано: меньше минуты назад

    35 120 просмотров

    Опубликовано: меньше минуты назад

    2 032 просмотра

    Опубликовано: 49 лет назад

    22 196 просмотров

    Опубликовано: меньше минуты назад

    893 просмотра

    Опубликовано: меньше минуты назад

    19 866 просмотров

    Опубликовано: меньше минуты назад

    47 558 просмотров

    Опубликовано: меньше минуты назад

    36 164 просмотра

    Опубликовано: 49 лет назад

    153 099 просмотров

    Опубликовано: меньше минуты назад

    26 515 просмотров

    Опубликовано: меньше минуты назад

    71 721 просмотр

    Опубликовано: меньше минуты назад

    16 519 просмотров

    Опубликовано: 49 лет назад

    18 646 просмотров

    Опубликовано: меньше минуты назад

    92 218 просмотров

    Опубликовано: меньше минуты назад

    15 305 просмотров

    videocameron.ru