ЕГЭ по Информатике, Задание А9, Поляков К

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

Демонстрационный вариант ЕГЭ 2017 г. – задание №5

Решение:

Для на­хож­де­ния ко­до­вых слов будем ис­поль­зо­вать данную таблицу.

Если коды остальных букв будет начинаться на 0, код буквы А=0 будет яв­ля­ть­ся на­ча­лом их кодов, по­это­му этот ва­ри­ант не под­хо­дит. Если код Б=10, коды букв В, Г, Д, Е начинаются на11. Чтобы получить 4 разных кода, нужно использовать коды, состоящие из 4-х символов (1111, 1110, 1101, 1100) .

А - 0 (1 символ)
Б - 10 (2 символа)
В - 1100 (4 символа)
Г - 1101 (4 символа)
Д - 1110 (4 символа)
Е - 1111 (4 символа)

1+2+4+4+4+4 = 19

Ответ: 19

Демонстрационный вариант ЕГЭ 2016 г. – задание №5

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

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

Решение:

Для на­хож­де­ния ко­до­вых слов будем ис­поль­зо­вать данную схему.

Если коды остальных букв будет начинаться на 0 , код буквы О =0 будет яв­ля­ть­ся на­ча­лом их кодов, по­это­му этот ва­ри­ант не под­хо­дит. Так как код буквы П =100 , а код буквы Т =111 , то буква С не может начинаться и заканчиваться этими цифрами.

Ответ: 101

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

Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:

1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16

Решение:

ГАВБГВ = 0110001011011010

Ответ: 4

Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода.

1) 57414 2) 53414 3) 53412 4) 53012

Решение:

Ответ: 3

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

1) 6543 2) 62926 3) 62612 4) 3456

Решение:

01100010100100100110

Ответ: 1

Для кодирования букв О, Л, А, З, К используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ЗАКОЛКА и записать результат в шестнадцатеричном коде, то получится:

1) 4531253 2) 9876 3) E832 4) 238E

Решение:

ЗАКОЛКА = 1110100000110010

Ответ: 3

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=00, Б=11, В=100. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 010 2) 0 3) 01 4) 011

Решение:

A=00, Б=11, В=100, Г=?

Ответ: 3

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

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

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

1) 1 2) 0 3) 01 4) 10

Решение:

А – 111, Б – 110, В – 101, Г – 100, Д – ?

Ответ: 2

По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А – 10110, Б – 11000, В – 00101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

1) 01110 2) 01011 3) 10001 4) не подходит ни одно из указанных выше слов

Решение:

1) 01 110: А – 10 110 – не отличаются не менее чем в трёх позициях

2) 01011: А – 101 10 , Б – 1 1000 , В – 0010 1 – отличаются не менее чем в трёх позициях

Ответ: 2

Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:

А – 10001, Б – 01101, В – 10110.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01111, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).

Получено сообщение 00110 11101 11000 11001. Декодируйте это сообщение – выберите правильный вариант.

1) ВБхх 2) ВБВА 3) хххх 4) ВБхА

Решение:

Ответ: 4

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 1; Б – 0100; В – 000; Г – 011; Д – 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

А-1, Б-011, В-00, Г-010

Ответ: 9

По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

1) А:1, Б:01, В:001, Г:111

2) А:1, Б:01, В:10, Г:111

3) А:00, Б:01, В:10, Г:11

4) А:100, Б:101, В:11, Г:0

Решение:

Ни одно кодовое слово не является началом другого: А является началом Г в 1-й и 2-й вариантах.

Общая длина закодированного сообщения должна быть как можно меньше.

3) А:00 (15), Б:01 (10), В:10 (6), Г:11 (4)

2.15+2.10+2.6+2.4 = 70

4) А:100 (15), Б:101 (10), В:11 (6), Г:0 (4)

3.15+3.10+2.6_1.4 = 61

Ответ: 3

По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы П, Р, С, Т. Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв П, Р, С используются 5-битовые кодовые слова: П: 01111, Р: 00001, С: 11000. 5-битовый код для буквы Т начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы Т.

Решение:

С: 1 1000

Т: 1 0110 (Т начинается с 1 и заканчивается на 0)

С и Т: 2 буквы одинаковы, то это означает, что остальные 3 буквы должны быть разными.

Ответ: 1 0110

ЕГЭ по Информатике, Задание А9, Поляков К.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

Примеры.
1. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.
1) 00 2) 01 3)11 4) 010
Решение:
8) заметим, что для известной части кода выполняется условие Фано – никакое кодовое слово не является началом другого кодового слова
9) если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит
10) если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит
11) если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит
12) для четвертого варианта, Д = 010, условие Фано не нарушено;
13) правильный ответ – 4.

2. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 1 2) 1110 3) 111 4) 11
Решение (вариант 1, метод подбора):
1) рассмотрим все варианты в порядке увеличения длины кода буквы Г
2) начнем с Г=1; при этом получается, что сообщение «10» может быть раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит
3) следующий по длине вариант – Г=11; в этом случае сообщение «110» может быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит
4) третий вариант, Г=111, дает однозначное раскодирование во всех сочетаниях букв, поэтому…
5) … правильный ответ – 3.

Возможные проблемы:
при переборе можно ошибиться и «просмотреть» какой-нибудь вариант

Решение (вариант 2, «умный» метод):
1) для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода; это условие называют условием Фано
2) как и в первом решении, рассматриваем варианты, начиная с самого короткого кода для буквы Г; в нашем случае код Г=1 является началом кодов букв Б и В, поэтому условие Фано не выполняется, такой код не подходит
3) код Г=11 также является началом другого кода (кода буквы В), поэтому это тоже ошибочный вариант
4) третий вариант кода, Г=111, не является началом никакого уже известного кода; кроме того, ни один уже имеющийся код не является началом кода 111; таким образом, условие Фано выполняется
5) поэтому правильный ответ – 3.

Бесплатно скачать электронную книгу в удобном формате и читать:

Скачать книгу ЕГЭ по Информатике, Задание А9, Поляков К. - fileskachat.com, быстрое и бесплатное скачивание.

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

Проверяемые элементы : Умение кодировать и де кодировать информацию

Теоретический материал :

Кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите).

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

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

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

Пример задания:

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

Код должен удовлетворять свойству однозначного декодирования.

Общий подход:

Используя условие Фано или логические рассуждения подобрать ответ.

Решение:

1) 00 - нарушает условие Фано, так как кодовая цепочка совпадает с началом Б = 000 и В = 001. Невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ, поэтому первый вариант не подходит

2) 01 - нарушает условие Фано, так как кодовая цепочка совпадает с началом Г = 011. Невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г, поэтому второй вариант тоже не подходит

3) 11 - нарушает условие Фано, так как кодовая цепочка совпадает с началом А = 1. Н евозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит

4) 010 - условие Фано не нарушено.

Ответ: 4) 010

Задания для тренировки:

1)Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=00, Б=11, В=100. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

2)Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=000, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

3)Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–11, В–000, Г–001, Д–011. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) это невозможно

2) для буквы Б – 1

3) для буквы В – 00

4) для буквы Д – 01

4)Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–11, Б–10, В–011, Г–000, Д–001. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Г – 00

2) это невозможно

3) для буквы В – 01

4) для буквы Б – 1

5)Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Г – 11

2) это невозможно

3) для буквы В – 000