Однозначное разбиение кодированного сообщения на буквы что это

Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

41) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? У меня не один почему то не подходит ведь если подставлять каждая начинается с той же цифры объясните решение
1) 101 2) 10 3) 11 4) 01

У меня не один почему то не подходит ведь если подставлять каждая начинается с той же цифры объясните решение

Какое количество автобусов и машин нужно заказать, чтобы стоимость заказа была минимальной
надо перевести группу из N человек. можно заказать автобус(вмещает 50 человек) и стоит A или.

Нужно зафиксировать букву флешки, чтобы она была и на других компьютерах
Как зафиксировать определенную букву флешки, чтобы на других компьютерах при использовании флешки.

Разделить каждое слово из текста на буквы, затем закодировать каждую букву
Здравствуйте! Учусь программировать на С++, хочу сделать одну программку. В чем суть: пользователь.

Спланировать перевозки, чтобы стоимость была минимальной
В городе имеется 2 склада муки и 2 хлебозавода. Ежедневно с 1-го склада вывозится 50 т муки, а со.

Источник

Однозначное разбиение кодированного сообщения на буквы что это

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.

Рассмотрим варианты для буквы Г, начиная с самого короткого.

3) Г=11: код буквы A является началом этого кода, поэтому этот вариант не подходит.

4) Код Г=101 не подходит по аналогичной причине.

2) Код Г=000 не совпадает с началом ни одного кода,следовательно это и есть правильный ответ.

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.

Рассмотрим варианты для буквы Г, начиная с самого короткого.

1) Г=1: код буквы Г является началом кода буквы В=101 и Б=100, поэтому этот вариант не подходит.

2) Код Г=11 не совпадает с началом ни одного кода,следовательно это и есть правильный ответ.

В вариантах 3) и 4) код буквы А=0 является началом кода буквы Г, поэтому они не подходят.

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

Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

2) для буквы В – 000

Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.

Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.

Вариант 3 не подходит, потому что 0 является началом кода 0001.

Вариант 4 не подходит, потому что код 1 является началом кода 111.

Вариант 2 подходит, так как не нарушает условия Фано.

Правильный ответ указан под номером 2.

Здравствуйте! Решая задачу по вашему принципу, я столкнулась с проблемой. Приведу пример:

По условию Фано подходят варианты А) и Б).

В вашем примере верный ответ — А. Если для буквы В выбрать код 101, то 1 будет являться началом кода для буквы В, нарушится условие Фано.

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

Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.

Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.

Вариант 3 не подходит, потому что 00 является началом кода 001.

Вариант 4 не подходит, потому что код 00 является началом кода 000.

Вариант 2 подходит, так как не нарушает условия Фано.

Правильный ответ указан под номером 2.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.

Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.

Вариант 3 не подходит, потому что 10 является началом кода 100.

Вариант 4 не подходит, потому что код 10 является началом кода 100 и 101.

Вариант 1 подходит, так как не нарушает условия Фано.

Источник

Мысли вслух

вторник, 23 октября 2012 г.

Ещё раз про однозначное декодирование

Введение

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 00, Б — 01, В — 100, Г — 101, Д — 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Д — 11; 2) это невозможно; 3) для буквы Г — 10; 4) для буквы Д — 10

Как показывает практика, эта задача вызывает серьезные трудности не только у многих учеников, но даже у учителей информатики.

Нужно сказать, что этот материал практически не рассматривается в существующих школьных учебниках информатики, поэтому все (как ученики, так и учителя) вынуждены разбираться самостоятельно. В то же время вузовские учебники 5, где соответствующая теория изложена строго и научно, достаточно сложны для понимания. Попробуем разобраться в сути кодирования и декодирования на школьном уровне, то есть так, как можно объяснить ученикам 8-11 классов.

В чём проблема?

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

Пример 1. Пусть для кодирования фразы «МАМА МЫЛА ЛАМУ» выбран такой код:

Коды букв «сцепляются» в одну битовую строку и передаются, например, по сети:
Эта цепочка битов приходит в пункт назначения, и тут возникает проблема — как восстановить исходное сообщение (конечно, при условии, что мы знаем код, то есть знаем все пары «символ–кодовое слово», которые использовались при кодировании).

Итак, мы получили 0010011100010111010010. Легко понять, что при использовании кода (1) раскодировать такое сообщение можно самыми разными способами. Например, можно предположить, что оно составлено только из букв А (код 1) и Л (код 0). Тогда получаем
В общем, ни мамы, ни ламы.

Определение. Код называется однозначно декодируемым, если любое кодовое сообщение можно расшифровать единственным способом (однозначно).

Сказанное выше означает, что код (1) НЕ является однозначно декодируемым. Как же определить, является ли заданный код однозначно декодируемым? Этим вопросом мы и займемся.

Равномерные коды

Проблема состоит в том, чтобы правильно разбить полученную битовую цепочку на отдельные кодовые слова. Для того, чтобы её решить, можно, например, использовать равномерный код, то есть код, в котором все кодовые слова имеют одинаковую длину. Например, в нашей фразе 6 символов, поэтому можно использовать 3-битный код (который позволяет закодировать 8 = 2 3 различных символов).

Пример 2. Закодируем фразу из примера 1, используя код:

Получаем закодированное сообщение
Длина этого сообщения — 42 бита вместо 22 в предыдущем варианте, зато его легко разбить на отдельные кодовые слова и раскодировать («_» обозначает пробел):
Видим, что равномерные коды неэкономичны (закодированное сообщение в примере 2 почти в два раза длиннее, чем в примере 1), но зато декодируются однозначно.

Неравномерные коды

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

Пример 3. Используем для кодирования фразы из примера 1 следующий код:

Получаем
Здесь 34 бита. Это, конечно, не 22, но и не 42.

Несложно показать, что эта битовая цепочка декодируется однозначно. Действительно, первая буква — М (код 01), потому что ни одно другое кодовое слово не начинается с 01. Аналогично определяем, что вторая буква — А. Действительно, за 01 следует 00 (код буквы А) и никакое другое кодовое слово не начинается с 00. Это же свойство, которое называется условием Фано, выполняется не только для кодовых слов 01 и 00, но и кодовых слов всех других букв (проверьте это самостоятельно).

Условие Фано. Никакое кодовое слово не совпадает с началом другого кодового слова.

Коды, для которых выполняется условие Фано, называют префиксными (префикс слова — это его начальный фрагмент). Все сообщения, закодированные с помощью префиксных кодов, декодируются однозначно.
Префиксные коды имеют важное практическое значение — они позволяют декодировать символы полученного сообщение по мере его получения, не дожидаясь, пока всё сообщение будет доставлено получателю.

Упражнение. Расшифруйте сообщение, закодированное кодом (3). При расшифровке кода очередной буквы не заглядывайте вперёд!
Термины «условие Фано» и «префиксный код» не используются в заданиях ЕГЭ и ГИА, однако для решения этих задача важно, чтобы ученики понимали содержание условия Фано.

Пример 4. Рассмотрим ещё один код

Ясно, что он не является префиксным: код буквы А (00) совпадает с началом кода буквы Л (001) и код пробела (11) совпадает с началом кода буквы Ы (11). Закодированное сообщение
также имеет длину 34 бита, как и при использовании кода (3). Начнем раскодировать с начала. Ясно, что первой стоит буква М, потому что ни один другой код не начинается с 10. Затем — комбинация 001, которая может быть кодом буквы Л или кодом буквы А (00), за которым следует код буквы Ы или пробела. Получается, что для декодирования сообщения нам нужно «заглядывать вперёд», что очень неудобно.

Попробуем декодировать с конца битовой строки. Последние биты 0101 могут представлять только букву У, следующие 10 — только букву М и т.д. Можно проверить, что теперь сообщение однозначно декодируется с конца! Это происходит потому, что выполняется условие, которое можно назвать «обратным» условием Фано: никакое кодовое слово не совпадает с окончанием другого кодового слова. Коды, для которых выполняется обратное условие Фано, называют постфиксными (постфикс или суффикс слова — это его конечный фрагмент). В этом случае тоже обеспечивается однозначное декодирование. Таким образом,

Сообщение декодируется однозначно, если для используемого кода выполняется прямое или обратное условие Фано.

Однозначно декодируемые коды

Пример 5. Рассмотрим код, предназначенный для кодирования сообщений, состоящих только из букв А, Б и В:

Так как код буквы А (0) совпадает как с началом, так и с концом кода буквы В (010), для этого кода не выполняются ни прямое, ни обратное условие Фано. Поэтому пока мы не можем с уверенностью сказать, декодируется ли он однозначно.

Закодируем сообщение
и попытаемся раскодировать эту строку, используя код (5). В первую очередь, замечаем, что две соседние единицы могут появиться только при использовании буквы Б (код 11), поэтому сразу выделяем две таких группы:
Здесь жёлтым фоном выделена уже декодированная часть сообщения. В оставшейся части единица может появиться только в коде буквы В (010), в битовой строке находим две такие группы:
Оставшиеся нули — это коды букв А. Анализ алгоритма показывает, что такой код всегда однозначно декодируется.

Полный ответ на вопрос об однозначной декодируемости получил в начале 1960-х годов советский математик Ал.А. Марков, предложивший решение с помощью графов [2]. Продемонстрируем его метод на примере.

Пример 6. Рассмотрим код

Здесь не выполняется ни «прямое», ни «обратное» условие Фано, поэтому возможно, что декодировать сообщение однозначно не удастся. Но утверждать это заранее нельзя.

Код является однозначно декодируемым тогда и только тогда, когда в построенном таким образом графе нет ориентированных циклов, включающих вершину Λ.

Таким образом, код (6) не обладает свойством однозначной декодируемости.

Проверим таким же способом код (5), который, как мы уже выяснили, не является ни префиксным, ни постфиксным. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состоит из пустой строки и единицы: <Λ, 1>. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю:

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

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

Ещё примеры

Пример 7. Рассмотрим задачу А9 из демо-варианта КИМ ЕГЭ-2013 [1], которая сформулирована в начале статьи. Нужно оптимизировать код
выбрав один из вариантов
Решение. Сначала давайте посмотрим на исходный код, приведённый в условии. Можно заметить, что он префиксный — для него выполняется условие Фано: ни один из трехбитных кодов не начинается ни с 00 (код А), ни с 01 (код Б). Поэтому сообщения, закодированные с помощью такого кода, декодируются однозначно.

Заметим, что «обратное» условие Фано не выполняется: код буквы А (00) совпадает с окончанием кода буквы В (100), а код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Теперь проверим, что получится, если сократить код буквы Д до 11 (вариант 1). Свойство однозначной декодируемости может быть потеряно только тогда, когда в результате такого сокращения нарушится условие Фано, то есть код буквы Д совпадёт с началом какого-то другого кодового слова. Видим, что этого не произошло — нет других кодовых слов, которые начинаются с 11, поэтому вариант 1 — это и есть верное решение.

Остается убедиться, что варианты 3 и 4 не подходят. Если мы сократим код буквы Г до 10 (вариант 3), условие Фано оказывается нарушенным, так как теперь код буквы Г (10) совпал с началом кода буквы В (100). Одновременно нарушено и «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100). Но, как мы знаем, при этом код может всё-таки быть однозначно декодируемым.

Конечно, можно построить граф, как было сделано выше, и проверить, есть ли в нём циклы, включающие вершину Λ. В данном случае граф выглядит так:

Построение и анализ графа — дело достаточно трудоемкое и требующее аккуратности. Обычно в таких случаях значительно легче просто подобрать последовательность, которая может быть декодирована двумя разными способами.

Наконец, нужно убедиться, что вариант 4 не удовлетворяет условию. Если мы сократим код буквы Д до 10, условие Фано оказывается нарушенным, так как теперь код буквы Д (10) совпал с началом кода буквы В (100). Как и раньше, нарушено «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100) и код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Построим граф по методу Ал.А. Маркова:

Пример 8. Оптимизируйте код
сохранив свойство однозначной декодируемости сообщений. Выберите один из вариантов:
Решение. Определим, за счёт чего обеспечивается однозначная декодируемость исходного кода. Легко видеть, что код префиксный — для него выполняется условие Фано: ни одно из трёхбитовых кодовых слов не начинается ни с 11 (код А), ни с 10 (код Б). В то же время, обратное условие Фано не выполняется, потому что код буквы А (11) совпадает с окончанием кода буквы В (011).

Проверим вариант 1 — сократим код буквы Г до 00. При этом нарушилось условие Фано, которое обеспечивало однозначную декодируемость исходного варианта: теперь код буквы Г (00) совпадает с началом кода буквы Д (001). Но и обратное условие Фано тоже не выполняется для пары букв А-В. Поэтому можно предположить, что такой код не обладает свойством однозначной декодируемости. И действительно, легко находится цепочка 001011, которую можно раскодировать как ГБА (00 10 11) или ДВ (001 011).

Рассмотрим вариант 3 — сократим код буквы В до 01. При этом условие Фано выполняется, поскольку ни одно из кодовых слов не начинается с 01, то есть код является префиксным и однозначно раскодируется. Это и есть правильный ответ.

На всякий случай проверяем вариант 4 — сокращает код буквы Б до 1. При этом код перестает быть префиксным, и обратное условие Фано также не выполнено (код буквы Б совпадает с началом и концом кода буквы А). Сразу понятно, что последовательность 11 можно раскодировать как А или как ББ, поэтому этот вариант неверный.

Выводы

В заметке выполнен подробный анализ задачи на кодирование, которая предлагается на ЕГЭ в последние несколько лет. Нужно заметить, что в нём затрагивается вузовский курс дискретной математики. Понятно, что нельзя требовать от школьников знания теорем Ал.А. Маркова об однозначном декодировании, но учителю полезно более глубоко представлять себе эти вопросы, которые можно разбирать на факультативах. В качестве дополнительной литературы по этой теме можно рекомендовать 5.

С точки зрения практического подхода, для решения всех известных автору реальных задач подобного типа достаточно найти вариант, при котором выполняется условие Фано или обратное условие Фано (одно из двух!).

Литература

Комментарии: 16:

Спасибо, что «на пальцах» объяснили еще раз!

Действительно, спасибо. Очень понятно.

Просто великолепная статья!
Спасибо!

Уважаемый Константин! Бесконечно благодарна Вам за неоценимую помощь в подготовке детей к ЕГЭ по информатике.

Спасибо), всё понятно)))

Отличная статья! Спасибо!

Спасибо за статью. В учебнике информатики 10 класса Полякова содержится опечатка в последовательности построения графа Маркова, которая, при всей схожести текста, исправлена у вас. Порадовало также более ясное объяснение примеров.

> В учебнике информатики 10 класса Полякова содержится опечатка
Да, действительно была в первом издании. Сейчас исправлена.

Программа, скачанная отсюда, на codeTable = выдала следующий список вершин графа: [‘Lambda’, ‘0’, ‘1’].
Но разве ‘2’ не должна входит в список вершни, так как является началом ‘E’ и концом ‘C’ и не является кодовым словом?

> Но разве ‘2’ не должна входит в список вершин, так как является началом
> ‘E’ и концом ‘C’ и не является кодовым словом?
Программа предназначена только для обработки двоичных кодов.

А как можно доказать на пальцах, что из отсутствия данного граф-цикла следует однозначность декодируемости? А то зашел в учебник Маркова, а там просто жесть какая-то. Развитие моего ума не позволяет мне это изучить в разумные сроки.

Последний граф для кода А — 00, Б — 01, В — 100, Г — 101, Д — 10 составлен не совсем точно.
Нужно еще из вершины Λ в вершину 1 провести дугу Д → Г.

Подпишитесь на каналы Комментарии к сообщению [Atom]

Константин Поляков Санкт-Петербург

Источник

Тема: Кодирование и декодирование информации

А5 (базовый уровень, время – 2 мин)

Тема: Кодирование и декодирование информации.

· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)

· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход

· один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)

· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

Пример задания:

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится

1) из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный

2) последовательность БАВГ кодируется так:= 1001011

3) разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем

4) правильный ответ – 1.

· расчет на то, что при переводе тетрад в шестнадцатеричную систему можно забыть заменить большие числа (10–15) на буквы (10112 = 11, получаем неверный ответ 41116)

· может быть дан неверный ответ, в котором нужные цифры поменяли местами (расчет на невнимательность), например, B416

· в ответах дана последовательность, напоминающая исходную (неверный ответ BACD16), чтобы сбить случайное угадывание

Еще пример задания:

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

Определить, какой набор букв закодирован двоичной строкой

1) EBCEA 2) BDDEA 3) BDCEA 4) EBAEA

Решение (вариант 1, декодирование с начала):

1) здесь используется неравномерное кодирование, при котором декодирование может быть неоднозначным, то есть, заданному коду может соответствовать несколько разных исходных сообщений

2) попробуем декодировать с начала цепочки, первой буквой может быть B или E, эти случаи нужно рассматривать отдельно

3) пусть первая буква – E с кодом 011, тогда остается цепочка

· для кода первой буквой может быть только B с кодом 01, тогда остается ( начало исходной цепочки – EB?)

· для кода первой буквой может быть только A с кодом 000, тогда остается 11000, а эта цепочка не может быть разложена на заданные коды букв

· поэтому наше предположение о том, что первая буква – E, неверно

4) пусть первая буква – B с кодом 01, тогда остается цепочка

· для кода первой буквой может быть только D с кодом 10, тогда остается (можно полагать, что начало исходной цепочки – BD?)

· для кода первой буквой может быть только С с кодом 100, тогда остается 011000 (начало исходной цепочки – BDC?)

Несмотря на то, что среди ответов есть единственная цепочка, которая начинается с BDC, здесь нельзя останавливаться, потому что «хвост» цепочки может «не сойтись»

· для кода 011000 на первом месте может быть B (код 01) или E (011); в первом случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором – остается код 000 (буква А), поэтому исходная цепочка может быть декодирована как BDCEA

5) правильный ответ – 3

Возможные ловушки и проблемы:

· при декодировании неравномерных кодов может быть очень много вариантов, их нужно рассмотреть все; это требует серьезных усилий и можно легко запутаться

· нельзя останавливаться, не закончив декодирование до конца и не убедившись, что все «сходится», на это обычно и рассчитаны неверные ответы

Решение (вариант 2, декодирование с конца):

1) для кода последней буквой может быть только А (код 000), тогда остается цепочка

2) для последней может быть только буква E (011), тогда остается цепочка 0110100

3) для 0110100 последней может быть только буква C (100), тогда остается цепочка 0110

4) для 0110 последней может быть только буква D (10), тогда остается 01 – это код буквы B

5) таким образом, получилась цепочка BDCEA

6) правильный ответ – 3

Возможные ловушки и проблемы:

· при декодировании неравномерных кодов может быть очень много вариантов (здесь случайно получилась единственно возможная цепочка), их нужно рассмотреть все; это требует серьезных усилий и можно легко запутаться

· нельзя останавливаться, не закончив декодирование до конца и не убедившись, что все «сходится», на это обычно и рассчитаны неверные ответы

Решение (вариант 3, кодирование ответов):

1) в данном случае самое простое и надежное – просто закодировать все ответы, используя приведенную таблицу кодов, а затем сравнить результаты с заданной цепочкой

3) сравнивая эти цепочки с заданной, находим, что правильный ответ – 3.

· сложно сравнивать длинные двоичные последовательности, поскольку они однородны, содержат много одинаковых нулей и единиц

Еще пример задания:

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

Решение (вариант 1, метод подбора):

1) рассмотрим все варианты в порядке увеличения длины кода буквы Г

2) начнем с Г=1; при этом получается, что сообщение «10» может быть раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит

3) следующий по длине вариант – Г=11; в этом случае сообщение «110» может быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит

4) третий вариант, Г=111, дает однозначное раскодирование во всех сочетаниях букв, поэтому…

5) … правильный ответ – 3.

· при переборе можно ошибиться и «просмотреть» какой-нибудь вариант

Решение (вариант 2, «умный» метод):

1) для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода; это условие называют условием Фано

2) как и в первом решении, рассматриваем варианты, начиная с самого короткого кода для буквы Г; в нашем случае код Г=1 является началом кодов букв Б и В, поэтому условие Фано не выполняется, такой код не подходит

3) код Г=11 также является началом другого кода (кода буквы В), поэтому это тоже ошибочный вариант

4) третий вариант кода, Г=111, не является началом никакого уже известного кода; кроме того, ни один уже имеющийся код не является началом кода 111; таким образом, условие Фано выполняется

5) поэтому правильный ответ – 3.

· нужно знать условие Фано

Еще пример задания[1]:

Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

Для компактности результат записали в шестнадцатеричной системе счисления. Выберите правильную запись кода.

1) BD9AA5 2) BDA9B5 3) BDA9D5 4) DB9DAB

1) «вытянем» растровое изображение в цепочку: сначала первая (верхняя) строка, потом – вторая, и т. д.:

2) в этой полоске 24 ячейки, черные заполним единицами, а белые – нулями:

3) поскольку каждая цифра в шестнадцатеричной системе раскладывается ровно в 4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в данном случае все равно, откуда начинать разбивку, поскольку в полоске целое число тетрад – 6):

4) переводя тетрады в шестнадцатеричную систему, получаем последовательно цифры B (11), D(13), A(10), 9, D(13) и 5, то есть, цепочку BDA9D5

5) поэтому правильный ответ – 3.

· нужно уметь быстро переводить тетрады в шестнадцатеричные цифры (в крайнем случае, это можно сделать через десятичную систему)

Задачи для тренировки[2]:

1) Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат в шестнадцатеричной системе счисления, то получится:

2) Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБВА и записать результат шестнадцатеричным кодом, то получится:

Определите, какой набор букв закодирован двоичной строкой

1) baade 2) badde 3) bacde 4) bacdb

4) Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:

5) Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится:

6) Для кодирования букв К, L, М, N используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов KMLN и записать результат в восьмеричном коде, то получится:

7) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

1) cbade 2) acdeb 3) acbed 4) bacde

8) Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

1) DEFBAC 2) ABDEFC 3) DECAFB 4) EFCABD

9) Для кодирования букв А, В, С, D используются четырехразрядные последовательные двоичные числа, начинающиеся с 1 (от 1001 до 1100 соответственно). Если таким способом закодировать последовательность символов CADB и записать результат в шестнадцатеричном коде, то получится:

1) AF5CBF15D16 4) В9СА16

10) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

Если таким способом закодировать последовательность символов ВГАГБВ и записать результат в шестнадцатеричном коде, то получится:

1) CDADBC16 2) A7C4) 4С7А16

11) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

Если таким способом закодировать последовательность символов ГАВБВГ и записать результат в шестнадцатеричном коде, то получится:

12) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

Если таким способом закодировать последовательность символов ГБВАВГ и записать результат в шестнадцатеричном коде, то получится:

1) 7101DBCACD16 3) 31AA1316

13) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:

Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:

1) DACBDC16 2) AD24) 62DA16

14) Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код:

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

15) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное кодирование: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид.

1) AD34 2) 43DACADBCD

16) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

17) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

18) Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода.

19) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное кодирование: А-0, Б-11, В-100, Г-011. Через канал связи передается сообщение: ГБАВАВГ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в восьмеричный код.

20) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное кодирование: А-10, Б-11, В-110, Г-0. Через канал связи передается сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный код.

1) D3A66A3D 4) CADBAADC

21) Для кодирования сообщения, состоящего только из букв О, К, Л, М и Б, используется неравномерный по длине двоичный код:

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

22) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ГБВАВГ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричную систему счисления. Какой вид будет иметь это сообщение?

[2] Источники заданий:

1. Демонстрационные варианты ЕГЭ гг.

2. Гусева И. Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. — СПб: Тригон, 2009.

Источник