Инфоурок / Информатика / Другие методич. материалы / Подготовка к ЕГЭ : Задание 1

Подготовка к ЕГЭ : Задание 1


библиотека
материалов

Задание 1

Задача 1.

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

1)  00              2)  01              3)  11             4)  010

            Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого).  Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным.

1)      00 – не подходит (является началом кодового слова 000 для буквы Б);

2)      01 – не подходит (является началом кодового слова 011 для буквы Г);

3)      11– не подходит (является продолжением(!) кодового слова 1 для буквы А);

4)      010 – подходит! (не является ничьим началом и никто не является его началом).

Ответ: 4.

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

В рассмотренной задаче А достаточно найти один вариант, удовлетворяющий требованиям задачи. НЕ ТРЕБУЕТСЯ доказывать, что при остальных вариантах код не будет допускать однозначного декодирования. Однако, в данном случае это сделать несложно. А именно:

            1) Код Д: 00. Тогда 000000 допускает две расшифровки: ББ и ДДД.

            2) Код Д: 01. Тогда 011 допускает две расшифровки: Г и ДА.

            2) Код Д: 11. Тогда 11 допускает две расшифровки: АА и Д.

 

2. Задача

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

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

1) 00;   2) 001; 3) 10;   4) 101

            Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого).  Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным. Однако, в отличие от задачи из демо-варианта, здесь по условию более одного варианта может приводить к тому, что получится код, допускающий однозначное декодирование. Поэтому нужно перебирать варианты от более коротких к более длинных и, если вариант не приводит к префиксному коду, убеждаться, что этот вариант действительно дает код, не допускающий однозначного декодирования.

1) Код для Д: 00 – не допускает однозначного декодирования (00 допускает две расшифровки: ГГ и Д).

2) Код для Д: 10 – не допускает однозначного декодирования (100 допускает две расшифровки: В и ДГ).

3) Код для Д: 001 – не допускает однозначного декодирования (00100 допускает две расшифровки: ГГВ и ДГГ).

4) Код для Д: 101 – вместе с кодами для А, Б, В, Г образует префиксный код.

Правильный ответ: 4

 



Только до конца зимы! Скидка 60% для педагогов на ДИПЛОМЫ от Столичного учебного центра!

Курсы профессиональной переподготовки и повышения квалификации от 1 400 руб.
Для выбора курса воспользуйтесь удобным поиском на сайте KURSY.ORG


Вы получите официальный Диплом или Удостоверение установленного образца в соответствии с требованиями государства (образовательная Лицензия № 038767 выдана ООО "Столичный учебный центр" Департаментом образования города МОСКВЫ).

Московские документы для аттестации: KURSY.ORG


Общая информация

Номер материала: ДВ-000272

Похожие материалы



Очень низкие цены на курсы переподготовки от Московского учебного центра для педагогов

Специально для учителей, воспитателей и других работников системы образования действуют 60% скидки (только до конца зимы) при обучении на курсах профессиональной переподготовки (124 курса на выбор).

После окончания обучения выдаётся диплом о профессиональной переподготовке установленного образца с присвоением квалификации (признаётся при прохождении аттестации по всей России).

Подайте заявку на интересующий Вас курс сейчас: KURSY.ORG