Задание 4 ЕГЭ по информатике

12.03.2024

Сборник необходимой теории и практики к заданию №4 ЕГЭ 2024 по информатике «Кодирование и декодирование информации».

Формулировка задания №4 ЕГЭ 2024 из демоверсии ФИПИ

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано, согласно которому никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н – 1111, З – 110. Для трёх оставшихся букв А, К и Ч кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Самое необходимое по заданию №4 в формате видеоурока

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

Кодирование — это перевод информации, представленной символами первичного алфавита, в последовательность кодов.
Декодирование (операция, обратная кодированию) — перевод кодов в набор символов первичного алфавита.
Двоичный код — это способ представления данных в одном разряде в виде комбинации двух знаков, обычно обозначаемых цифрами 0 и 1. Разряд в этом случае называется двоичным разрядом.
Двоичное кодирование — один из распространённых способов представления информации. В вычислительных машинах, в роботах и станках с числовым управлением, как правило, вся информация, с которой имеет дело устройство, кодируется в виде слов двоичного алфавита.

Кодирование может быть равномерное и неравномерное.

Равномерный код

Равномерный код (или код постоянной длины) — код, кодовые слова которого содержат одинаковое число букв (одинаковую длину слов).

кодирование называется равномерным, если соответствующий ему код имеет постоянную длину

Пример: Запишем буквы A, B, C, D при помощи двоичного кодирования равномерным кодом: А - 00, B - 01, C - 10, D - 11. Таким образом, мы получим равномерный код, так как длина каждого кодового слова одинакова.

Неравномерный код

Неравномерный код (или код переменной длины) — код, кодовые слова которого имеют разное число букв (неодинаковую длину слов).

кодирование называется неравномерным, если соответствующий ему код имеет переменную длину

Пример: Закодируем буквы A, B, C, D при помощи двоичного кодирования неравномерным кодом: А - 00, B - 100, C - 101, D - 1010. Таким образом, мы получим неравномерный код, так как длина кодовых слов для букв различна.

Однозначно декодируемый код

Однозначно декодируемый код — код, в котором любое сообщение, составленное из кодовых слов, можно декодировать единственным способом.

Равномерное кодирование всегда однозначно декодируемо. Для неравномерных кодов существует достаточное (но не необходимое) условие однозначного декодирования.

Прямое условие Фано

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

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

Пример: Для букв А, Б, В используются такие кодовые слова: А - 1, Б - 010, В - 000. Каким наименьшим кодовым словом может быть закодирована буква Д, при котором будет допускаться однозначное декодирование, удовлетворяющее прямому условию Фано.

Буква Д не может кодироваться как 0, т.к. кодирование буквы В начинается с 0.
Буква Д не может кодироваться как 1, т.к. это кодирование буквы А.
Буква Д не может кодироваться как 10 и 11, т.к. кодирование буквы А - 1.
Буква Д не может кодироваться с 01 и 00, т.к. кодирование буквы В - 010, а кодирование буквы С - 000.

Следовательно, буква Д может кодироваться как 001 — это наименьшее возможное значение.

Обратное условие Фано

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

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

Пример: Для букв А, Б, В используются такие кодовые слова: А - 100, Б - 110, В - 010. Каким наименьшим кодовым словом может быть закодирована буква Д, при котором будет допускаться однозначное декодирование, удовлетворяющее обратному условию Фано.

Буква Д не может кодироваться как 0, т.к. А - 100, Б - 110, В - 010.
Буква Д не может кодироваться как 10, т.к. Б - 110, В - 010.

Следовательно, буква Д может кодироваться как 01 — это наименьшее возможное значение.

Для возможности однозначного декодирования достаточно выполнения одного из условий — или прямого, или обратного.

Как решать задание №4 ЕГЭ

Пример 1: По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П:100.

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

Решение (первый способ): Код однозначно декодируется, если выполняется условие Фано или обратное условие Фано. В данном случае "прямое" условие Фано выполняется: с кода буквы О (0) не начинается ни один из двух других кодов. Новый код не может начинаться с нуля (иначе нарушится условие Фано).

Начнём проверку с кодов длиной 1:

единственный код, не начинающий с нуля — 1 — не подходит, потому что с 1 начинаются два других кода: Т (111) и П (100).

Кодов длиной 2, начинающихся с 1, всего два:

10 и 11, но их использовать нельзя, потому что с 10 начинается код буквы П, а с 11 — код буквы Т.

Рассматриваем коды длиной 3, начинающиеся с 1:

коды 100 и 111 уже заняты, а ещё два — 101 и 110 — свободны и их можно использовать, причём условие Фано выполняется в обоих случаях.

Поскольку нужно выбрать код с минимальным значением, выбираем 101. Ответ: 101.

Решение (второй способ):

Пример 2: Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений.

Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв — П и Р — кодовые слова неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:

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

Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:

Пример 4: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 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: По каналу связи передаются сообщения, содержащие четыре буквы: М, Ы, Л, О. Для передачи используется неравномерный двоичный код, допускающий однозначное кодирование. Для букв М, Ы, Л используются такие кодовые слова: М: 01, Ы: 110, Л: 10.

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

Решение: Неравномерный код, допускающий однозначное декодирование, должен соответствовать условию Фано. По условию Фано в неравномерном префиксном коде ни одно кодовое слово не может быть началом другого слова.

Проще говоря, если у буквы М код 01, то кодом буквы О не может быть 0, так как 0 — начало кода 01.

Нам даны коды: 01 110 10. Очевидно, что 0 и 1 кодом буквы О быть не может, так как другие буквы начинаются с 0 и 1. Зато нам подходит двузначный код 00, в этом случае ни 00 не будет являться началом других букв, ни другие буквы не будут являться началом кода 00. Ответ: 00.

Примеры заданий №4

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

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

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Пример 2. По каналу связи передаются сообщения, содержащие только четыре буквы: М, О, Р, Е; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв О, Р, Е используются такие кодовые слова: О: 111, Р: 0, Е: 100.

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

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Пример 3. По каналу связи передаются сообщения, содержащие только шесть букв: А, И, К, Л, Н, Т, для передачи используется двоичный код, удовлетворяющий условию Фано. Буквы Л и Н имеют коды 0 и 11 соответственно. Укажите наименьшую возможную длину закодированной последовательности для слова КАЛИТКА.

Пример 4. Для кодирования некоторой последовательности, состоящей из букв А, К, Л, О, C, Т решили использовать неравномерный двоичный код, для которого выполняется условие Фано. Для букв А и К использовали соответственно кодовые слова 10, 111. Найдите кодовую последовательность наименьшей длины для кодирования слова КОЛОКОЛ и запишите полученный результат в восьмеричном коде. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответы к примерам заданий №4

1. 101; 2. 110; 3. 25; 4. 161161.

Ниже представлены замечательные материалы, подготовленные Поляковым Константином Юрьевичем, доктором технических наук. В них вы найдёте всё самое полезное для себя — теория, решения заданий и практика. Все материалы для ЕГЭ по информатике: https://kpolyakov.spb.ru/school/ege.htm.

Смотреть в PDF:

Для просмотра установите Adobe Reader и обязательно вернитесь для просмотра файла :).

Или прямо сейчас: cкачать в pdf файле.

Сохранить ссылку:

Комментарии (0) Добавить комментарий

У вас недостаточно прав для комментирования