Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

4. Кодирование и декодирование

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения
Задание 1 #12669

Для кодирования последовательности, состоящей из букв слова ШKOЛKOВО решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Ш использовали кодовое слово 00, для буквы К — 1. Укажите, какова наименьшая длина всех символов заданного слова.

Построим дерево для решения задачи. Для букв Ш и К есть кодовые слова 00 и 1 соответственно. В слове ШКОЛКОВО самая частовстречаемая буква — О, следовательно, её нужно закодировать минимальновозможным количеством символов.

Минимально возможная длина кодового слова для буквы состоит из трёх битов, то есть О закодируем с помощью 010.

Буквы Л и В встречаются всего один раз, закодируем их минимально возможным количеством символов.

Самая маленькая длина кодовых слов для них \(=4\): 0110 и 0111.

Посчитаем сумму длин кодовых слов:

Ш, Л и В встречаются один раз,

К — 2 раза,

О — 3 раза.

\(3\cdot3+2\cdot1+1\cdot2+2\cdot4=21\)

Ответ: 21

Задание 2 #12670

Для кодирования последовательности, состоящей из букв слова Р, Б, О, Т, А используется неравномерный двоичный код, удовлетворяющий прямому условию Фано.

Вот этот код: А – 0; Р – 100; Б – 1010; О – 111; Т – 110. Необходимо сократить для одной из букв длину кодового слова так, чтобы код можно было однозначно декодировать.

Для какой буквы это возможно сделать? В ответе укажите эту букву.

Так как код удовлетворяет прямому условию Фано (ни одно кодовое слово не является началом другого), то следует учитывать это при сокращении исходных кодовых слов.

1. Код буквы А сократить нельзя, так как он состоит всего из одного символа.

2. Р сократить нельзя,так как при сокращении до 10 код перестанет удовлетворять прямому условию Фано.

3. Б возможно сократить до 101, в таком случае код по-прежнему будет удовлетворять одному из условий Фано (прямому).

4. О нельзя сократить, т.к. в этом случае нарушится прямое условие Фано.

5. Код буквы Т нельзя сократить, т.к тогда он совпадёт с началом кода буквы О, что недопустимо при выполнении прямого условия Фано.

Ответ: Б

Задание 3 #12671

По каналу связи передаются сообщения, которые содержат только следующие буквы: С, Т, Р, И, М; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв С, Т, Р используются такие кодовые слова: С – 0; Т – 110; Р – 101. Укажите кратчайшее кодовое слово для буквы И, при котором код будет допускать однозначную расшифровку. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Построим дерево решений. Код не может начинаться с нуля, т.к из данной вершины нельзя построить новые варианты, удовлетворяющие условию Фано. Из схемы видно, что для букв И, М есть два возможных варианта кодировки,которые начинаются с 1.

Первый вариант: 111

Второй вариант: 100

Оба варианта удовлетворяют условию Фано (не являются началом других кодовых слов), нам подходит вариант с наименьшим значением, то есть 100 — ответ.

Ответ: 100

Задание 4 #12672

Пётр Николаевич решил списать решение задачи у одноклассника, но ошибся. Необходимо найти ошибку в решении Петра и записать её в ответ. Известно, что задача была составлена на проверку знания прямого условия Фано.

Кодируется сообщение с помощью символов У, Ч, Е, Б, А.

Для каждой буквы выделено кодовое слово: У — 00; Е — 110; А — 010; Ч — 111; Б — 001.

В ответе укажите букву и кодовое слово без пробелов. Например, Д010.

Из условия задания мы знаем, что кодировка сообщения происходит по прямому условию Фано. Построим для решения задания дерево.

Начиная заполнение вершин дерева символами возникают проблемы с Б. Символ У занимает позицию 00, то есть дальше продолжить дерево нельзя, т.к вершина уже занята.

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

Ответ: Б001

Задание 5 #12673

Для кодирования последовательности,состоящей из букв О, С, К, А используется неравномерный двоичный код, удовлетворяющий условию Фано.

Каким минимальным количеством символов можно закодировать слово ОСОКА, чтобы коды имели однозначное декодирование.

Первый вариант разбиения

Рассмотрим заданное слово: в нём используется 4 разных символа. Построим дерево решений с двоичными кодами букв. На каждую букву будем выделять по два бита. Посчитаем информационный вес слова:

\(2\cdot2+(2\cdot1)\cdot3=10\)

Второй вариант разбиения

Рассмотрим иную ситуацию: так как символ О встречается два раза,а все остальные только по одному,то закодируем O минимально возможным количеством символов — одним.

Остальные символы также закодируем минимальным количеством символов. (см. дерево 2)

Посчитаем сумму кодовых слов:

\(1\cdot2+2\cdot3+2\cdot1=10\)

Получили так же 10 символов, более выгодных для распределения символов комбинаций нет.

Значит получившийся ответ: 10.

Ответ: 10

Задание 6 #12674

По информационному каналу передаются сообщения,которые содержат буквы B, A, L, I. Для передачи используется двочиный код, допускающий однозначное декодирование. Для букв A, L, I используются кодоые слова: A — 101010, L — 111010, I — 111100.

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

Если таких кодов несколько, укажите код с наименьшим числовым значением.

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

Начнём перебирать коды с минимально возможного, т.е. с кода длиной 1. Таких кода два: 0 и 1.

С 1 код начинаться может, так как в таком случае будет игнорироваться условие однозначности декодирования, ведь коды для букв А, L, I начинаются с 1.

С 0 код может начинаться,ведь никакой иной код с данного символа не начинается.

Значит кратчайшее кодовое слово для B состоит из одного символа — 0.

Ответ: 0

Задание 7 #12675

В сообщении встречается 8 разных букв.

При его передаче использован неравномерный двоичный префиксный код. Известны коды трех букв: 11, 100, 101.

Коды остальных пяти букв имеют одинаковую длину. Какова минимальная суммарная длина всех 8 кодовых слов?

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

Двух символов не хватит,так как всего один код поместится на код,состоящий из двух символов.

Кода длиной 3 единицы тоже не хватит: в таком случае удастся разместить только 4 буквы, а по условию необходимо пять.

Значит нам подойдут коды длиной 4: таких в нашем дереве 8 штук. Разместим 5 букв по любым из них и посчитаем суммарную длину.

\(5\cdot4+2\cdot3+2\cdot1=28\)

Итоговый ответ на задачу: 28

Ответ: 28