Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Другие методич. материалы / Подготовка к ЕГЭ : Задание 1
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Информатика

Подготовка к ЕГЭ : Задание 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

 




Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 21.09.2015
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров235
Номер материала ДВ-000272
Получить свидетельство о публикации
Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх