ЕГЭ по Информатике, Задание А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.
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12785 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Вышивка крестом. Коллекция схем. Megat Cross Stitch №3
Автор:КоллективНазвание: Вышивка крестом. Коллекция схем. Megat Cross Stitch №3Издательство: Megat Cross StitchГод: 2009Формат: JPG, PDFРазмер: 255МВСтраниц:140Натюрморты, пейзажи, герои сказок и муль . . .
-
Вышивка крестом. Коллекция лучших схем Dimensions 2009
Автор:КоллективНазвание: Вышивка крестом. Коллекция лучших схем Dimensions 2009Издательство: DimensionsГод: 2009Формат: РС, РМ, JPGРазмер: 48МВ Страниц:418 Вышивка крестом. Коллекция лучших схем Dimen . . .
-
Бюджетирование в коммерческой организации
В книге кратко и максимально четко даются практические рекомендации по организации процесса бюджетирования в коммерческих организациях. Приводятся конкретные ситуации (кейсы), где разработаны различны . . .
-
Экономика предприятия. Практикум
Практикум содержит системное изложение учебного материала дисциплины "Экономика предприятия отрасли". Приведены основные понятия, механизм функционирования, а также инструменты управления экономическо . . .
-
Маркетинговые каналы
В пятом издании книги основное внимание авторов сосредоточено на описании процессов формирования, развития и долговременного поддержания эффективных отношений между членами маркетинговых каналов, кото . . .
-
Управление финансово - товарными потоками на предприятиях торговли
В данном издании рассматриваются основные моменты организации управления денежными и товарными ресурсами, предлагаются способы повышения эффективности их использования, а также объясняется, как правил . . .
-
Реклама в блогах
Учебное пособие предназначено для студентов, обучающихся по специальности 032401 – Реклама. В фокусе внимания данного пособия – основные понятия, характеризующие блогосферу, функции и типы блогов. Отд . . .
-
Аудит и контроллинг персонала
Подробно рассмотрены аудит персонала, управленческий аудит, методология аудита персонала и практическая работа аудитора в этой сфере деятельности. Особое внимание уделено контроллингу системы управлен . . .
-
ПИФы - это просто
Данная книга предназначена начинающему инвестору-новичку, который хочет вложить свои денежные средства на российском фондовом рынке, но у которого нет ни времени, ни соответствующих знаний, чтобы проф . . .
-
Теория бухгалтерского учета
В учебном пособии рассматриваются все темы, охватывающие общие знания по теории бухгалтерского учета. Все разделы учебного пособия характеризуются системностью и логичностью изложения. В пособии сочет . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге ЕГЭ по Информатике, Задание А9, Поляков К.. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.