По каналу связи передается сообщение которое содержит 20 букв е 18 букв и

Обновлено: 02.07.2024

5. Автомат обрабатывает десятичное натуральное число N по следующему алгоритму.
1. К десятичной записи справа дописывается последняя цифра числа N.
2. Получившееся число переводится в двоичное представление.
3. К двоичной записи этого числа справа дописывается бит четности, единица, если количество единиц в двоичной записи нечетно, 0 – если четно.
4. Полученное в результате этих операций число переводится в десятичную систему счисления.
Пример.
Дано число 13.
1310 -> 13310 -> 100001012 -> 1000010112 -> 26710
Укажите минимальное число N, после обработки которого получится число, превышающее 413.
Ответ: ________________________.

8. Вася составляет 7-буквенные коды из букв К, А, Б, И, Н, Е, Т. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Б и не может содержать сочетания ЕА. Сколько различных кодов может составить Вася?
Ответ: _________________________.

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

Подготовка к ЕГЭ- 2020 по информатике. Рассматриваются задачи по теме "Кодирование и декодирование информации. Условие Фано"

Список вопросов теста

Вопрос 1

Вопрос 2

Вопрос 3

Вопрос 4

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 10 и 111.

Определите наименьшую возможную суммарную длину всех пяти кодовых слов.

Вопрос 5

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

Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.

Вопрос 6

Вопрос 7

Вопрос 8

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 00, для буквы Б — кодовое слово 01. Укажите наименьшую сумму длин кодовых слов для букв В, Г, Д и Е, при котором код будет допускать однозначное декодирование.

Вопрос 9

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

Известно, что для одной из букв использовано кодовое слово 01. Укажите кратчайшее кодовое слово для буквы П, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Вопрос 10

Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращённое кодовое слово без пробелов и запятых, например—А0.

Привет! Сегодня узнаем, как решать 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.

На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.

ЕГЭ по информатике - Задание 1 (Практика)

Стас костюшкин 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

Проверяемые элементы содержания: Умение кодировать и декодировать информацию

Плейлист видеоразборов задания на YouTube:

ЕГЭ 4.1: Для кодирования букв О , В , Д , П , А решили использовать двоичное представление чисел 0 , 1 , 2 , 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

Ответ: 22162

Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
Теперь закодируем последовательность букв из слова ВОДОПАД :
Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:

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

a	b	c	d	e
000	110	01	001	10

Какой набор букв закодирован двоичной строкой 1100000100110 ?

Ответ: b a c d e

Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.

Результат: b a c d e.

✎ 2 вариант решения:

ЕГЭ 4.3:
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4 , и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23 , то получим последовательность 0010100110 ).

Определите, какое число передавалось по каналу в виде 01100010100100100110 .

Ответ: 6 5 4 3

ЕГЭ 4.4:
Для кодирования некоторой последовательности, состоящей из букв К , Л , М , Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0 , для буквы К — кодовое слово 10 .

Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

Ответ: 9

Найдём самые короткие возможные кодовые слова для всех букв.
Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
Суммарная длина всех четырёх кодовых слов равна:

✎ 2 вариант решения:

ЕГЭ по информатике 4 (раньше №5) задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):

Укажите кратчайшее кодовое слово для буквы Г , при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 00

Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

ЕГЭ по информатике 4 (раньше №5) задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):

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

Укажите, каким кодовым словом должна быть закодирована буква Д . Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 101

Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:

Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 1100

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

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 00

Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).

Дерево по условию Фано (однозначно декодируется с начала):

Дерево по обратному условию Фано (однозначно декодируется с конца):

Результат: 00

Читайте также: