Решение задач ЕГЭ типа А9
материал для подготовки к егэ (гиа) по информатике и икт (11 класс) на тему

Слайд 1

ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Кодирование и декодирование информации . А 9 Разбор задач ЕГЭ

Слайд 2

Задача 1. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа. 1) это невозможно 2) для буквы В – 000 3) для буквы Б – 0 4) для буквы Г – 11

Слайд 3

В секундах. Задача 1. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение. Мы видим, что выполняется условие Фано : никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала. Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде . Вариант 1 оставляем, пока не проверим остальные. Вариант 2 подходит, так как не нарушает условия Фано . Вариант 3 не подходит, потому что 0 является началом кода 0001. Вариант 4 не подходит, потому что код 11 является началом кода 111 . Правильный ответ указан под номером 2. Ответ 2

Слайд 4

Рассмотрим варианты ответов. 1) ОК. Разбивать на части нужно так: 11 и 2. Возможные исходные 61 8 и 31 8 . 2) Не подходит. Разбить на части можно только так: 21 и 11. Число 21 8 нельзя получить, как сумму однозначных восьмеричных чисел. (нарушено условие в2). 3) Не подходит. Цифра 9 не может встречаться в восьмеричном числе. 4) Не подходит. Разбить на части можно только так: 2 и 7. При этом 2 > 7 (нарушено условие в3 - первое число должно быть больше второго) Правильный ответ : 1 Задача 2. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © По каналу связи передаются сообщения, содержащие только 4 буквы: А, И, С, Т. В любом сообщении больше всего букв А, следующая по частоте буква — С, затем — И. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать? 1) А−0, И−1, С−00, Т−11 2) С−1, И−0, А−01, Т−10 3) А−1, И−01, С−001, Т−000 4) С−0, И−11, А−101, Т−100

Слайд 5

В секундах. Задача 2. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение. Выберем коды, для которых выполнено условие Фано . Это коды 3 и 4. Чтобы сообщение было как можно короче, необходимо, чтобы чем чаще встречалась буква, тем короче был ее код. Следовательно, ответ 3, поскольку буква А — самая часто встречающаяся буква и для ее кодирования в варианте 3 используется один символ. Ответ 3

Слайд 6

Рассмотрим варианты ответов. 1) ОК. Разбивать на части нужно так: 11 и 2. Возможные исходные 61 8 и 31 8 . 2) Не подходит. Разбить на части можно только так: 21 и 11. Число 21 8 нельзя получить, как сумму однозначных восьмеричных чисел. (нарушено условие в2). 3) Не подходит. Цифра 9 не может встречаться в восьмеричном числе. 4) Не подходит. Разбить на части можно только так: 2 и 7. При этом 2 > 7 (нарушено условие в3 - первое число должно быть больше второго) Правильный ответ : 1 Задача 3. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится 1) 22162 2) 1020342 3) 2131453 4) 34017

Слайд 7

В секундах. Задача 3. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение. Сначала следует представить данные в условии числа в двоичном коде : Затем закодировать последовательность букв: ВОДОПАД — 01-00-10-00-11-100-10 . Теперь разобьём это представление на тройки справа налево и переведём полученный набор чисел в десятичный код, затем в восьмеричный (восьмеричное представление совпадает с десятичным при разбиении тройками, воспользуемся таблицей из А1) 010-010-001-110-010 — 22162. Правильный ответ указан под номером 1. Ответ 1 О В Д П А 0 1 2 3 4 0 0 0 1 10 11 100 «сохранение одного незначащего нуля в случае одноразрядного представления»

Слайд 8

Рассмотрим варианты ответов. 1) ОК. Разбивать на части нужно так: 11 и 2. Возможные исходные 61 8 и 31 8 . 2) Не подходит. Разбить на части можно только так: 21 и 11. Число 21 8 нельзя получить, как сумму однозначных восьмеричных чисел. (нарушено условие в2). 3) Не подходит. Цифра 9 не может встречаться в восьмеричном числе. 4) Не подходит. Разбить на части можно только так: 2 и 7. При этом 2 > 7 (нарушено условие в3 - первое число должно быть больше второго) Правильный ответ : 1 Задача 4. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами: А — 0, И — 00, К — 10, О — 110, Т — 111. Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту. 1) КАА 2) ИКОТА 3) КОТ 4) ни одно из сообщений не подходит

Слайд 9

В секундах. Задача 4. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение. Закодируем каждое слово. КАА — 1000 ИКОТА — 00101110 КОТ — 10110111 Слово КАА можно декодировать как КИ Слово ИКОТА можно декодировать как ААКОТА Слово КОТ никак нельзя декодировать по-другому. Следовательно, ответ 3. Ответ 3

Слайд 10

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © По каналу связи передаются сообщения, содержащие только 4 буквы: П, О, Р, T. Для кодирования букв П, О, Р используются 5-битовые кодовые слова: П — 11111, О — 11000, Р — 00100. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трех позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы T, чтобы указанное свойство выполнялось для всех четырёх кодовых слов? 1) 00000 2) 11100 3) 00011 4) не подходит ни одно из указанных слов Ответ 3

Слайд 11

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © По каналу связи передаются сообщения, содержащие только 4 буквы: А, Т, О, М; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, М используются такие кодовые слова: Т: 100, О: 00, М: 11. Укажите такое кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина. 1) 1 2) 0 3) 01 4) 101 Ответ 3

Слайд 12

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Для кодирования букв И, Д, Т, О, X решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ТИХОХОД таким способом и результат записать шестнадцатеричным кодом, то получится 1) CD89 2) 89CD 3) 3154542 4) 2043431 Ответ 2

Слайд 13

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © По каналу связи передаются сообщения, содержащие только 4 буквы — П, О, Р, Т. Для кодирования букв используются 5-битовые кодовые слова: П — 00000, О — 00111, Р — 11011, Т — 11100. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех (в предположении, что передаваемые биты могут искажаться, но не пропадают). Закодированное сообщение считается принятым корректно, если его длина кратна 5 и каждая пятёрка отличается от некоторого кодового слова не более чем в одной позиции; при этом считается, что пятёрка кодирует соответствующую букву. Например, если принята пятерка 11111, то считается, что передавалась буква Р . Среди приведённых ниже сообщений найдите то, которое принято корректно, и укажите его расшифровку (пробелы несущественны). 11011 10111 11101 00111 10001 10000 10111 11101 00111 00001 1) ПОТОП 2) РОТОР 3) ТОПОР 4) ни одно из сообщений не принято корректно Ответ 1. Ответ 2