Через канал связи передается сообщение вагбаагв
Обновлено: 05.07.2024
А — 0; Б — 10; В — 110.
2. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно).
Закодируйте таким образом последовательность символов АВГАБ и запишите полученное двоичное число в восьмеричной системе счисления.
3. Для кодирования букв Д, Л, О, Е, Х решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ЛЕДОХОД таким способом и результат запишите шестнадцатеричным кодом.
4. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Вот этот код: А – 00; Б – 101; В – 011; Г – 111; Д – 110.
Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны.
Для букв A, Б, В используются такие кодовые слова: А – 1, Б – 010, В – 001. Какова наименьшая возможная суммарная длина всех кодовых слов?
1. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность. Для букв А, Б, В и Г использовали такие кодовые слова:
А — 001, Б — 010, В— 000, Г — 011.
Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
А – 00, Б – 11, В – 010, Г – 011.
Закодируйте таким образом последовательность символов ВГАГБВ и запишите результат в восьмеричном коде.
3. Для кодирования букв Е, П, Н, Ч, Ь решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ПЕЧЕНЬЕ таким способом и результат запишите восьмеричным кодом.
4. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 011, Б – 001, В – 010, Г – 000, Д – 11.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.
Какова наименьшая возможная суммарная длина всех кодовых слов?
A - 0, Б - 100, В - 101.
А - 0, Б - 11, В - 100, Г - 011.
3. Для кодирования букв Р, С, Н, О, Г решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв НОСОРОГ таким способом и результат запишите шестнадцатеричным кодом.
4. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Вот этот код: А – 001; Б – 100; В – 101; Г – 111; Д – 110.
Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким способом это можно сделать?
5. Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.
Для буквы Л использовали кодовое слово 1, для буквы М —011.
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код. Для букв А, Б, В и Г использовали такие кодовые слова:
А – 111, Б – 110, В – 100, Г – 101.
Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
А - 10, Б - 11, В - 110, Г - 0.
3. Для кодирования букв X, Е, Л, О, Д решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
Закодируйте последовательность букв ЛЕДОХОД таким способом и результат запишите шестнадцатеричным кодом.
4. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 011, Б – 000, В – 11, Г – 001, Д – 10.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.
5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.
Для буквы А использовали кодовое слово 0; для буквы Б – 10.
Какова наименьшая возможная сумма длин всех шести кодовых слов?
A - 0, Б - 100, В - 101.
А – 00, Б – 11, В – 010, Г – 011.
Закодируйте таким образом последовательность символов ГАВБВГ и запишите результат в восьмеричном коде.
3. Для кодирования букв Е, Н, П, Ь, Ч решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ПЕЧЕНЬЕ таким способом и результат запишите шестнадцатеричным кодом.
4. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Вот этот код: А – 01; Б – 100; В – 000; Г – 001; Д – 11.
Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким способом это можно сделать?
Решение:
АВАБАГ = 101 11 101 01 101 100 = 1011 1101 0110 1100
1011 = 8 + 0 + 2 + 1 = 11 = B
1101 = 8 + 4 + 0 + 1 = 13 = D
0110 = 0 + 4 + 2 + 0 = 6
1100 = 8 + 4 + 0 + 0 = 12 = C
Итого получаем BD6C.
Отличная статья по теме основных преобразований: goo.gl/jTPR4M
Ответ:
Задание добавил(а)
О задание:
Источник условия: ЕГЭ-2017. Информатика. 20 тренировочных вариантов. Д.М. Ушаков.
Источник решения: Авторский коллектив проекта ExamMe
Обсуждения
camera_alt
Последние задачи
На стороне $BC$ остроугольного треугольника $ABC$ как на диаметре построена полуокружность, пересекающая $AD$ в точке $M$, $AD=90$, $MD=69$, $H$ - точка пересечения высот треугольника $ABC$. Найдите $AH$.
В треугольнике $ABC$ биссектриса угла $A$ делит высоту, проведенную из вершины $B$, в отношении $13:12$, считая от точки $B$. Найдите радиус окружности, описанной около треугольника $ABC$, если $BC=20$.
В треугольнике $ABC$ известны длины сторон $AB=60$, $AC=80$, точка $O$-центр окружности, описанной около треугольника $ABC$. Прямая $BD$, перпендикулярная прямой $AO$, пересекает $AC$ в точке $D$. Найдите $CD$.
Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.
Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.
Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.
Равномерное кодирование всегда однозначно декодируемо.
Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:
Кодирование в различных системах счисления
Для кодирования букв О, В, Д, П, А решили использовать двоичное представление
чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится
Представим коды указанных букв в двоичном коде, добавив незначащий нуль для одноразрядных чисел:
Закодируем последовательность букв: ВОДОПАД — 010010001110010.
Разобьём это представление на тройки справа налево и переведём каждую тройку в восьмеричное число.
010 010 001 110 010 — 22162.
Правильный ответ указан под номером 1.
Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется посимвольное кодирование: А-10, Б-11, В-110, Г-0. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в шестнадцатеричный вид.
Закодируем последовательность букв: ВАГБААГВ — 1101001110100110. Разобьем это представление на четвёрки справа налево и переведём каждую четверку в шестнадцатеричное число:
1101 0011 1010 01102 = D3A616
Правильный ответ указан под номером 1.
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные:
Мы видим, что условия Фано и обратное условие Фано не выполняются, значит код можно раскодировать неоднозначно.
Значит, будем перебирать варианты, пока не получим подходящее слово :
1) 100 011 01 10 110
Первая буква определяется однозначно, её код 100: a.
Пусть вторая буква — с, тогда следующая буква — d, потом — e и b.
Такой вариант удовлетворяет условию, значит, окончательно получили ответ: acdeb.
Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: А — 11010, Б — 10111, В — 01101.
Получено сообщение 11000 11101 10001 11111. Декодируйте это сообщение — выберите правильный вариант.
Декодируем каждое слово сообщения. Первое слово: 11000 отличается от буквы А только одной позицией. Второе слово: 11101 отличается от буквы В только одной позицией. Третье слово: 10001 отличается от любой буквы более чем одной позицией. Четвёртое слово: 11111 отличается от буквы Б только одной позицией.
Таким образом, ответ: АВхБ.
Однозначное кодирование
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:
Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.
Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны.
Выберите правильный вариант ответа.
Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
1) кодовое слово для буквы Е можно сократить до 01
2) кодовое слово для буквы К можно сократить до 1
3) кодовое слово для буквы Н можно сократить до 10
4) это невозможно
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:
Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. кодовое слово для буквы Н можно сократить до 10.
Привет! Сегодня узнаем, как решать 4 задание из ЕГЭ по информатике нового формата 2021.
Четвёртое задание из ЕГЭ по информатике раскрывает тему кодирование информации. Одним из центральных приёмов при решении задач подобного типа является построение дерева Фано. Рассмотрим на примерах этот метод.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование
Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.
Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).
От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.
Получается структура похожая на дерево!
В конце каждой ветки можно располагать букву, которую мы хотим закодировать, но если мы расположили букву, от этой ветки больше нельзя делать новых ответвлений.
Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.
Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.
Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.
Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствовать наименьшему возможному двоичному числу. Как расположить буквы D и E в данной задаче не принципиально.
Ответ: 1000.
Ещё один важный тип задания 4 из ЕГЭ по информатике нового формата 2021.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоить как можно меньшую длину!
Отметим на дереве Фано уже известные буквы (Б, К, Л).
У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?
Если продолжить линию 1-0, то получится такая картина :
Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.
Посчитаем общую длину слова АБСЦИССА.
3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.
Продлим линию 1-1-0 (можно и 0-1-1, не принципиально, т.к. эти ветки имеют одинаковую длину.), то получится:
Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.
3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22
Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.
В этой задаче ничего не сказано про условие Фано. Здесь уже все буквы закодированы, осталось написать сам код.
Задача сводится к переводу из двоичной системы в восьмеричную систему. На эту тему был урок на моём сайте.
Ответ: 151646.
На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.
ЕГЭ по информатике 2022 - Задание 13 (Лёгкое!)
Стас костюшкин 15-10-2020 в 18:48:52
Этого не знаю. Это просто примерные задачи, которые наиболее часто попадаются в книжках и на сайтах по подготовке к ЕГЭ по информатике.
Калужский Александр 15-10-2020 в 18:57:40
Глеб Цыбрий 15-11-2020 в 10:30:33
Ольга Владимировна Сорокина 05-03-2021 в 12:09:08
Ольга Владимировна Сорокина 05-03-2021 в 12:09:14
Задача 1. Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится 1) 22162 2) 1020342 3) 2131453 4) 34017
Решение Представим данные в условии числа в виде двоичного кода: Закодируем последовательность букв ВОДОПАД = 01 00 10 00 11 100 10 3. Разобьем это представление на тройки справа налево, переведя полученный набор в восьмеричный код: 010 010 001 110 010 = 22162. О В Д П А 0 1 2 3 4 00 01 10 11 100 Ответ: 1
Задача 2 (самостоятельно) Для кодирования букв Д, X, Р, О, В решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ХОРОВОД таким способом и результат записать восьмеричным кодом, то получится 1) 12334 2) 2434541 3) 36714 4) 1323430 Ответ: 3
Решение Закодируем последовательность букв: ВБГАГВ — 0101101100011010. 2. Теперь разобьём это представление на четвёрки справа налево и переведём полученный набор чисел шестнадцатеричный код 0101 1011 0001 1010 — 5В1А. Ответ: 3
Задача 6 Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице: Определите, какой набор букв закодирован двоичной строкой 1100000100110 1) baade 2) badde 3) bacde 4) bacdb a b c d e 000 110 01 001 10
Решение Разобьём код слева направо по данным таблицы и переведём его в буквы: 110 000 01 001 10 — b a c d e. Ответ: 3. 1100000100110 a b c d e 000 110 01 001 10
Задача 7 Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице: Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные: 1) cbade 2) acdeb 3) acbed 4) bacde a b c d e 100 110 011 01 10
Решение 1) Для решения задачи проверим выполняется ли условие Фано: никакое кодовое слово не является началом другого кодового слова Условие не выполняется! (d –начало c, e – начало а) a b c d e 100 110 011 01 10
Решение 2 )Проверим выполняется ли обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова Условие не выполняется! (e – конец b) Значит данный код можно раскодировать неоднозначно a b c d e 100 110 011 01 10
Решение Будем пробовать разные варианты, отбрасывая те, в которых получаются повторяющиеся буквы: 1) 100 011 01 10 110 Первая буква определяется однозначно, её код 100: a. Пусть вторая буква — с, тогда следующая буква — d, потом — e и b. Такой вариант удовлетворяет условию, значит, окончательно получили ответ: acdeb. Ответ: 2
Читайте также: