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

Обновлено: 05.07.2024

Чтобы купить курс,
пожалуйста, войдите
или зарегистрируйтесь

Быстрая регистрация

Информатика (Вариант 1)

Приобретите наш курс

Для продолжения просмотра купите полный курс
наших видеоуроков

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Для трёх букв кодовые слова уже известны, осталось подобрать для оставшихся четырёх букв такие кодовые слова, которые обеспечат наименьшее количество двоичных знаков для кодирования слова ГРАММ.

Закодируем букву М кодовым словом 00, поскольку буква М повторяется в слове ГРАММ два раза. Для буквы Г возьмём кодовое слово 110. Кодовое слово 111 взять не можем, поскольку для остальных букв не останется кодовых слов, удовлетворяющих условию Фано. Оставшиеся две буквы закодируем кодовыми словами длины 4.

Таким образом, наименьшее количество двоичных знаков, которые потребуются для кодирования слова ГРАММ, равно 3 + 4 + 3 + 2 + 2 = 14.

Контакты

ул. Чернышевского, д. 17, офис 33, Казань, Республика Татарстан, 420000, Россия

Запись на тестирование

Поиск по сайту

Личный кабинет

Вы живете в Казани?

Adblock Detected

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

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

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

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице звёздочками обозначено наличие дорог.

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Найдите номера пунктов F и H. В качестве ответа запишите найденные номера в порядке убывания без разделителей.

Вопрос 2

Логическая функция F задаётся выражением x ∧ (¬y ∧ z ∧ w ∨ y ∧ ¬w).

На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

Вопрос 3

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

Вопрос 4

Вопрос 5

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом:

1) Строится двоичная запись числа N.
2) В этой записи последний ноль заменяется на первые две цифры полученной записи. Если нуля нет, алгоритм аварийно завершается.
3) Запись записывается справа налево (в обратную сторону).
4) Результат переводится в десятичную систему счисления.

Для какого минимального значения N в результате работы алгоритма получится число 123?

Вопрос 6

Какой минимальный объём памяти (целое число Мбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 1024x4096 пикселей при условии, что в изображении могут использоваться 1024 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.

Вопрос 7

Алексей составляет 5-буквенные слова из букв М, А, Г, И, С, Т, Р. Каждую букву можно использовать не более одного раза, при этом в слове нельзя использовать более одной гласной. Сколько различных кодов может составить Алексей?

Вопрос 8

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

Вопрос 9

Вопрос 10

При регистрации в компьютерной системе, используемой при проведении командной олимпиады, каждому ученику выдается уникальный идентификатор – целое число от 1 до 1000. Для хранения каждого идентификатора используется одинаковое и минимально возможное количество бит. Идентификатор команды состоит из последовательно записанных идентификаторов учеников и 8 дополнительных бит. Для записи каждого идентификатора команды система использует одинаковое и минимально возможное количество байт. Во всех командах равное количество участников. Сколько участников в каждой команде, если для хранения идентификаторов 20 команд-участниц потребовалось 180 байт?

Вопрос 11

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.

Вопрос 12

Значение выражения 5 2 ∙7 25 + 6 2 ∙7 36 – 4 2 ∙9 3 записали в семеричной системе счисления. Сколько нулей в такой записи?

Вопрос 13

На числовой прямой даны два отрезка: P=[10,30] и Q=[25,55]. Определите наибольшую возможную длину отрезка A, при котором формула

(x ∈ A) → ((x ∈ P) ∨ (x ∈ Q))

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

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

Плейлист видеоразборов задания на 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

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