x-uni.com
x-uni.com
x-uni.com
Математика
Биология
Литература
Русский язык
География
Физика
Химия
История
Английский
Информатика
География
Информатика
ВИДЕОКУРСЫ

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

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

2012.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–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.

Предложения интернет-магазинов

Подготовка к ЕГЭ по информатике. Оптимальные способы выполнения заданий

Автор(ы): Чупин Николай Александрович   Издательство: Феникс, 2013 г.  Серия: Абитуриент

Цена: 58 руб.   Купить

Обсуждаются оптимальные способы решения задач ЕГЭ по информатике на примере демонстрационного варианта ЕГЭ 2013 года. Для учащихся при подготовке к ЕГЭ по информатике и учителей информатики.


Подготовка к ЕГЭ по информатике (CDpc)

Автор(ы): Масленкова Ольга Федоровна   Издательство: Дрофа, 2011 г.  Серия: ЕГЭ

Цена: 253 руб.   Купить

Подготовка к ЕГЭ по информатике включает в себя: - полное соответствие спецификации ЕГЭ; - случайную генерацию вариантов; - возможность подготовки по отдельным темам; - ручную и автоматическую проверку ответов; Технические требования: Windows XPVista7, процессор 1500 МГц, 512 Мб ОЗУ, CD-ROM 8x, видеосистема 800х600, 16 bit.


ЕГЭ-тетрадь. Информатика

Автор(ы): Сафронов Игорь Константинович   Издательство: BHV, 2011 г.  Серия: Информатика и ИКТ

Цена: 180 руб.   Купить

В рабочей тетради для подготовки старшеклассников к сдаче ЕГЭ по информатике подробно разбираются задания демо-версии ЕГЭ-2011, ЕГЭ-2010 и заданий предыдущих лет, к ним приводятся аналогичные задачи. Экзаменационный материал представлен в соответствии с государственными образцами ЕГЭ по информатике, что позволяет готовиться по модели экзамена индивидуально. Есть раздел усложненных и комплексных задач. В конце тетради к большинству заданий приведены ответы.


Информатика и ИКТ. Подготовка к ЕГЭ. Поиск выигрышных стратегий. Решение задач С3

Автор(ы): Евич Людмила Николаевна   Издательство: Легион, 2014 г.  Серия: Готовимся к ЕГЭ

Цена: 59 руб.   Купить

Предлагаемое пособие представляет собой сборник задач с решениями по теме "Поиск выигрышных стратегий" (задание С3). В книге представлены самые разнообразные задания, предлагаемые на ЕГЭ начиная с 2009 года и другие интересные задачи по данной теме. Издание адресовано учащимся 10-11-х классов, готовящимся к ЕГЭ по информатике и ИКТ, и учителям, которые организуют процесс подготовки к экзамену. Книга является дополнением к учебно-методическому комплексу "Информатика и ИКТ. Подготовка к ЕГЭ". Допущено Министерством образования и науки Российской Федерации.