Кодирование и декодирование информации (продолжение разбора задания 4 ЕГЭ)
08.02.2022
Кодирование и декодирование информации. В задачах на тему «кодирование и декодирование информации» обязательно оговаривается используется ли условие Фано. Обратите внимание, что все задачи построены на условии Фано, разницей является лишь то, что условия задания построены несколько иначе.
Начало разбора заданий можно просмотреть по ссылке.
Продолжим разбирать новые задания по той же теме «Кодирование и декодирование информации»
Задание 6
Выписываем все буквы:
А -101
Б
К
О -11
Т
Р
Я- 011
Надо найти сколько двоичных знаков потребуется для кодирования слова КАТОК.
От нас требуется наименьшая длина. Мы видим, что буква К в нашем слове повторяется 2 раза, поэтому для буквы К нужно найти самое короткое кодовое слово.
Для букв Б и Р, которые мы должны учесть при поиске, но не должны указать в слове, можно взять любые слова, главным условием остается то, что слова должны подходить под условие Фано.
В нашем случае будет уже два дерева: и с 0 и с 1.
Отметим на бинарном дереве уже существующие коды букв:
Далее начинам искать коды недостающих букв.
Мы определились, что буква К должна иметь самый короткий код. Самый короткий код, который можно извлечь из двух бинарных деревьев – это 00.
Подставляем К -00
Для буквы Т, которая используется в слове возьмем три символа 010 и дальше по данной ветке мы идти не можем.
Т-010
Теперь осталось определить буквы Б и Р. По факту осталась только одна ветка бинарного дерева, от которой мы можем вниз отвести две ветки:0 и 1:
В результате получим код из 4 знаков для буквы Б и код из четырех знаков для буквы Р.
Б – 1000
Р -1001
Теперь перенесем все получившиеся коды в один столбик:
А -101
Б – 1000
К -00
О – 11
Т – 010
Р – 1001
Я – 011
Теперь считаем цифры кода для указанного слова:
КАТОК = 2+3+3+2+2 = 12
Количество двоичных знаков, которые необходимы для кодирования слова КАТОК – 12.
Ответ: 12
Задание 7
Это обратное задание предыдущему.
В -1110
Г -110
Д – 0000
Е -01
Б –
А –
О –
Все буквы русского алфавита.
БАОБАБ = 16
Буква Б – используется 3 раза, если я возьму для буквы Б код из 2 цифр, то получим 2*3 = 6
Буква А повторяется в слове 2 раза. Если для буквы А возьмем по 3 символа, т.к. 3*2 = 6
Буква О будет иметь 4 символа: 16 –6 — 6 = 4
Теперь необходимо найти эти коды на двух бинарных деревьях. Показываем те буквы, которые уже известны.
Осталось 4 ветки. Нужно учесть 3 буквы и оставить одну ветку под все буквы алфавита.
Ищем для буквы Б – 2 символа. Берем 10.
Ранее определили, что буква А должна иметь 3 символа. В нашем случае существует единственный вариант кода из трех симолов_ А – 001
Определяем код буквы О – 0001 (4 символа)
Тогда для всех остальных букв алфавита осталась одна ветка, которая будет расширяться дальше вниз.
В результате задание решено.
В -1110
Г -110
Д – 0000
Е -01
Б –10
А –001
О –0001
Все буквы русского алфавита (отдельная ветка осталась)
Все буквы русского алфавита (отдельная ветка осталась)
Сложность задания в том, что много учеников забывают, что нужно оставить одну ветку для всех букв алфавита
Уровень сложности здания довольно высокий.
Ответ: 001
Задание 8
В этом задании нет ни слова про однозначное декодирования или про условие Фано.
Р — 0
С- 1
Н — 2
О — 3
Г — 4
Как кодируется слово НОСОРОГ? При использовании двоичного представления чисел 1,2,3, и 4 соответственно.
Переводим десятичные цифры в двоичную систему счисления.
Р – 0 — 0
С- 1 — 1
Н – 2 — 10
О – 3 — 11
Г – 4 – 100
Но в условиях написано «с сохранением одного незначащего нуля в случае одноразрядного представления».
Одноразрядное представление – это когда в числе всего одна цифра. Незначащий ноль – это ноль, который стоит крайне слева.
В задаче одноразрядными представлены буквы Р и С, соответственно, Р – 00, С – 01.
Р – 0 — 00
С — 1 — 01
Н – 2 — 10
О – 3 — 11
Г – 4 – 100
Записываем слово НОСОРОГ посредством полученных кодов.
10 11 01 11 00 11 100
Теперь результат переводим в восьмиричную систему счисления. Для этого справа на лево отделяются по три символа:
Для того, чтобы воспользоваться таблицей триад для перевода числа из двоичной системы счисления в восьмеричную систему счисления, построим ее.
Вторую графу строим по очереди: сначала в каждую строку графы проставляем четыре нуля и четыре единицы. Затем опять идем по графе (сверху вниз) и проставляем сначала два нуля потом две единицы. Потом достраиваем триады путем подставления поочередного, то нуля, то единицы.
Сначала заполним графу цифр в восьмеричной системе счисления, их всего восемь.
Теперь подставляем новые цифры:
В результате получаем ответ: 55634
Если бы в задании была шестнадцатеричная система счисления, то надо было бы получить тетрады (по четыре цифры в двоичной системе счисления)
Если на четыре знака не делится, то добиваем незначащими нулями так, чтобы все цифры были задействованы.
Видео на тему «Кодирование и декодирование информации для подготовки к ЕГЭ» могу рекомендовать по ссылке
Экономист по первому образованию и учитель информатики по второму. Преподаю в школе информатику, программирование, сайтостроение, экономику.
Спасибо за разбор. Актуально. На сайт вовремя попал.
задачи, задачи, задачи…
С наступающим новым годом!
Интересно. Самое простое задание на экзамене, по-моему.
На сайте много интересного материала. Зайду позже и возможно, найду что-нибудь новое.
Полезная информация.
Слова про подготовку к ЕГЭ уже написаны. Ждем других материалов — все меняется ежегодно.
Готовлюсь к ЕГЭ
Тема интересна, приму участие в обсуждении. Вместе мы сможем прийти к правильному ответу. Я уверен.
Готовлюсь к экзаменам.)))