Как решать 4 задание егэ информатика деревом - Помощь в подготовке к экзаменам и поступлению

Урок посвящен тому, как решать 4 задание ЕГЭ по информатике

Содержание:

Кодирование информации
- Кодирование и расшифровка сообщений
Решение 4 заданий ЕГЭ

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

4-е задание: «Кодирование и декодирование информации»

Уровень сложности

— базовый,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 2 минуты.

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

До ЕГЭ 2021 года — это было задание № 5 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«Из-за невнимательного чтения условия задания экзаменуемые иногда не замечают, что требуется найти кодовое слово минимальной длины с максимальным (минимальным) числовым значением.

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

ФГБНУ «Федеральный институт педагогических измерений»

Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
Кодирование бывает равномерным и неравномерным:
при равномерном кодировании всем символам соответствуют коды одинаковой длины;
при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

Кодирование и расшифровка сообщений

Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.

Для решения задач с декодированием, необходимо знать условие Фано:

Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)

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

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

Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова

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

условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Однозначное декодирование обеспечивается:

Однозначное декодирование

Декодирование

Егифка ©:

Задание демонстрационного варианта 2022 года ФИПИ
Плейлист видеоразборов задания на YouTube:

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

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

✍ Решение:

Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:

О -> 0 -> 00
В -> 1 -> 01
Д -> 2 -> 10
П -> 3 -> 11
А -> 4 -> 100

Теперь закодируем последовательность букв из слова ВОДОПАД:

010010001110010

Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:

010 010 001 110 010
 ↓   ↓   ↓   ↓   ↓
 2   2   1   6   2

Результат: 22162

Теоретическое решение ЕГЭ данного задания по информатике, видео:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Рассмотрим еще разбор 4 задания ЕГЭ:

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

a	b	c	d	e
000	110	01	001	10

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

✍ Решение:

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

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

Код разбиваем слева направо согласно данным, представленным в таблице. Затем переведём его в буквы:

110 000 01 001 10
 ↓   ↓   ↓  ↓  ↓
 b   a  c   d  e

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

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

Сделаем дерево, согласно кодам в таблице:

Сопоставим закодированное сообщение с кодами в дереве:

110 000 01 001 10

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

Кроме того, вы можете посмотреть видеорешение этого задания ЕГЭ по информатике (теоретическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Решим следующее 4 задание:

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

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

✍ Решение:

Рассмотрим пример из условия задачи:

Было 23₁₀
Стало 0010100110₂

Где сами цифры исходного числа (выделим их красным цветом):

 0010100110  (0010 - 2, 0011 - 3)

Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).
Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:
разбиваем по 5:

01100 01010 01001 00110

отбрасываем из каждой группы последний символ:

0110 0101 0100 0011

Результат переводим в десятичную систему:

0110 0101 0100 0011
 ↓    ↓     ↓    ↓
 6    5     4    3

Ответ: 6 5 4 3

Вы можете посмотреть видеорешение этого задания ЕГЭ по информатике, теоретическое решение:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

ЕГЭ 4.4:

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

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

Подобные задания для тренировки

✍ Решение:

✎

1 вариант решения

основан на логических умозаключениях:

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

(Н)1 + (К)2 + (Л)3 + (М)3 = 9

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

Будем использовать дерево. Влево откладываем 0, вправо — 1:

Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:

(Н) -> 0   -> 1 символ
(К) -> 10  -> 2 символа
(Л) -> 110 -> 3 символа
(М) -> 111 -> 3 символа

Суммарная длина всех четырёх кодовых слов равна:

(Н)1 + (К)2 + (Л)3 + (М)3 = 9

Ответ: 9

4.5:

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

А: 101010, 
Б: 011011, 
В: 01000

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

Подобные задания для тренировки

✍ Решение:

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

Результат: 00

4.6:

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

А - 01 
Б - 00
В - 11
Г - 100

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

✍ Решение:

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

Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:

Перепишем сверху вниз получившееся кодовое слово для Д: 101

Результат: 101

Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

4.7: Демоверсия ЕГЭ 2018 информатика (ФИПИ):

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

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

Подобные задания для тренировки

✍ Решение:

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

При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:

Результат: 1100

Подробное теоретическое решение данного 4 (раньше №5) задания из демоверсии ЕГЭ 2018 года смотрите на видео:

📹 Видеорешение на RuTube здесь

4.8:

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

А: 00011 
Б: 111 
В: 1010

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

✍ Решение:

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

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

Получившееся числовое значение кодового слова для буквы Г — 01.

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

Получившееся числовое значение кодового слова для буквы Г — 00.
После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.

Результат: 00

4.9:

По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

Е – 000
Д – 10
К – 111

Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
В ответе напишите число – количество бит.

Подобные задания для тренировки

✍ Решение:

С помощью дерева отобразим известные коды для букв:

В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:

Расположим буквы в порядке их следования в слове и подставим их кодовые слова:

Д   Е   Д   М   А   К   А   Р
10 000 10  001 01  111 01  110

Посчитаем количество цифр в итоговом коде и получим 20.

Результат: 20

Смотрите виде решения задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Источник

Привет! Сегодня узнаем, как решать 4 задание из ЕГЭ по информатике нового формата 2021.

Четвёртое задание из ЕГЭ по информатике раскрывает тему кодирование информации. Одним из центральных приёмов при решении задач подобного типа является построение дерева Фано. Рассмотрим на примерах этот метод.

Задача (стандартная)

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу.

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

Решение:

Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то
расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.

Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).

От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.

Получается структура похожая на дерево!

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

Такой подход позволяет однозначно декодировать сообщение, состоящее из этих букв.

Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.

Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.

Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.

Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствовать наименьшему возможному двоичному числу. Как расположить буквы D и E в данной задаче не принципиально.

Ответ: 1000.

Ещё один важный тип задания 4 из ЕГЭ по информатике нового формата 2021.

Задача (стандартная)

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, К — 010, Л — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?

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

Решение:

Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоить как можно меньшую длину!

Отметим на дереве Фано уже известные буквы (Б, К, Л).

У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?

1 вариант

Если продолжить линию 1-0, то получится такая картина :

Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.

Посчитаем общую длину слова АБСЦИССА.

3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.

2 вариант

Продлим линию 1-1-0 (можно и 0-1-1, не принципиально, т.к. эти ветки имеют одинаковую длину.), то получится:

С мы присваиваем 1-0, т.к. это буква повторяется в сообщении самое большое количество раз, значит, ей присваиваем самый маленький код, чтобы всё сообщение имело наименьшую длину.

Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.

Подсчитаем общее количество символов в сообщении.

3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22

Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.

Ответ: 22.

Задача (не сложная)

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

Решение:

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

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

Ответ: 151646.

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

Этого не знаю. Это просто примерные задачи, которые наиболее часто попадаются в книжках и на сайтах по подготовке к ЕГЭ по информатике.

Здравствуйте, а вот такое задание ПО КАНАЛУ СВЯЗИ ПЕРЕДАЮТСЯ СООБЩЕНИЯ, СОДЕРЖАЩИЕ ТОЛЬКО 4 БУКВЫ : А, Б, В, Г; ДЛЯ ПЕРЕДАЧИ ИСП. ДВОИЧНЫЙ КОД, ДОПУСКАЮЩИЙ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ДЛЯ БУКВ А, Б, В ИСПОЛЬЗУЮТСЯ ТАКИЕ КОДОВЫЕ СЛОВА: А:00011, Б:1001, В: 01100.
УКАЖИТЕ КРАТЧАЙШЕЕ КОДОВОЕ СЛОВО ДЛЯ БУКВЫ Г, ПРИ КОТОРОМ КОД БУДЕТ ДОПУСКАТЬ ОДНОЗНАЧНОЕ ДЕКОДИРОВАНИЕ. ЕСЛИ ТАКИХ КОДОВ НЕСКОЛЬКО, УКАЖИТЕ КОД С НАИМЕНЬШИМ ЧИСЛОВЫМ ЗНАЧЕНИЕМ. В ответе указано число 10. Не могу понять почему. У меня 11.

Ольга Владимировна Сорокина, как я понимаю, суть задания в том, что здесь действует либо прямое, либо обратное условие Фано. (Примечание. Условие Фано означает, что соблюдается одно из двух условий.
Либо никакое кодовое слово не является началом другого кодового слова,
либо никакое кодовое слово не является окончанием другого кодового слова.
Это обеспечивает возможность однозначной расшифровки закодированных
сообщений.)
Поэтому 10 является ответом, так как ни один код для букв не оканчивается на 10 (срабатывает обратное условие Фано)

Источник

Скачать материал

Сейчас обучается 84 человека из 29 регионов

Сейчас обучается 33 человека из 18 регионов

Сейчас обучается 118 человек из 41 региона

Описание презентации по отдельным слайдам:

1 слайд

ЕГЭ-2022
Разбор задания 4 Информатика
Кодирование и декодирование информации
2 слайд

Введение
В данном уроке мы рассмотрим такие понятия как «Условие Фано» и «Префиксный код» , научимся строить бинарные деревья, а так же рассмотрим разные типы задач на тему «Кодирование и декодирование информации».
3 слайд

Теория
Условие Фано и Префиксный код
4 слайд

Условие Фано
Прямое условие Фано.
Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо другого, более длинного кода.
Такой код называют «префиксным».
5 слайд

Условие Фано
Обратное условие Фано.
Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с окончанием (постфиксом) какоголибо другого, более длинного кода.
Такой код называют «постфиксным».
6 слайд

Префиксный код
Префиксный код— код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово a, то для любой непустой строки b слова ab в коде не существует.

Например, код, состоящий из слов 0, 10 и 11, является префиксным, и сообщение 01001101110 можно разбить на слова единственным образом:
0 10 0 11 0 11 10
Код, состоящий из слов 0, 10, 11 и 100, префиксным не является, и то же сообщение можно трактовать несколькими способами.
0 10 0 11 0 11 10
0 100 11 0 11 10
7 слайд

Бинарное дерево
Бинарное дерево— это иерархическая структура данных, в которой каждый узел имеет значение и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне называется корнем. Узлы, не имеющие потомков называются листьями.
8 слайд

Бинарное дерево. Термины
Узел (вершина) — это каждый элемент бинарного дерева;
Ветви — связи между узлами;
Глубина (высота) — наибольший уровень какого-нибудь элемента;
Лист (терминальный узел) — термин применяется, если элемент не имеет потомков;
Внутренние узлы — узлы ветвления;
Степень внутреннего узла — число его потомков (наибольшая степень всех существующих узлов — это степень всего бинарного дерева);
Длина пути к x — количество ветвей, которые необходимо пройти от корня до текущего узла x. Длина пути самого корня равна нулю, а узел на уровне i обладает длиной пути, которая равна i.
9 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
Нарисуем корень нашего дерева из которого будут расти ветви.
10 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.

Вырастим две ветки
* Из одного корня могу выходить только две ветки
11 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
Пронумеруем ветки двоичным кодом слева → направо
0
1
12 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
Вырастим два листика.
В дереве появилось два места для двух букв.
13 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
Как мы видим место больше нет что бы добавить листик дерева.
В этом случаем листик превращаем в узел и растим ещё две ветки.
14 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
Левый лист превращён в узел и теперь он имеет двух потомков
0
1
15 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
И пронумерую ветки двоичным кодом
слева → направо
0
1
0
1
16 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
Теперь есть место для трёх букв.
17 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
Это корень сюда букву ставить нельзя
Это узел сюда букву ставить нельзя
Это листик сюда можно поставить букву
18 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
Места всё ещё не хватает
Правый лист превращу в узел и выращу две ветки.
19 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
Пронумеруем ветки двоичным кодом
слева → направо
0
1
20 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
Выращу два листа
21 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
Пронумерую двоичным кодом ветки
слева → направо
0
1
22 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
Место хватает для 4 букв
0
1
0
1
0
1
23 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
0
1
Места всё ещё не хватает
Правый лист превращу в узел и выращу две ветки
24 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
0
1
Пронумерую двоичным кодом ветки
слева → направо
0
1
25 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
0
1
0
1
0
1
0
Место есть для пяти букв
1
26 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
В
Г
Д
0
1
0
1
0
1
А
Б
0
Заполню листья буквами
А, Б, В, Г, Д
1
27 слайд

Построение Бинарного дерева
Задача: Необходимо закодировать буква А, Б, В, Г, Д так что бы полученный код удовлетворял Условию Фано.
Бинарное дерево закончено
В
Г
Д
0
1
0
1
0
1
А
Б
0
1
28 слайд

Найти Код символа с помощью бинарного дерева
29 слайд

Код символа по бинарному дереву
Для того что бы найти код символа посмотрим на наш корень
В
Г
Д
0
1
0
1
0
1
А
Б
0
1
30 слайд

Код символа по бинарному дереву
В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Что бы добрать до листика А от корня – необходимо двигаться по левой стороне.
31 слайд

Код символа по бинарному дереву
В
Г
Д
0
1
0
1
0
1
А
Б
0
1
От корня спускаюсь в левый узел.
Запишу в таблицу нумерацию ветки от корня к узлу.
32 слайд

Код символа по бинарному дереву
В
Г
Д
0
1
0
1
0
1
А
Б
0
1
От узла спускаюсь ниже на 1 уровень в левый узел.
Запишу в таблицу нумерацию ветки от узла к узлу.
33 слайд

Код символа по бинарному дереву
В
Г
Д
0
1
0
1
0
1
А
Б
0
1
От узла спускаюсь в листик А.
Запишу в таблицу нумерацию ветки от узла к листику А.
34 слайд

Код символа по бинарному дереву
В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Получился маршрут от корня до листика А которые равен 000.
35 слайд

В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Код символа по бинарному дереву
Аналогично найду код символа Б.
36 слайд

В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Код символа по бинарному дереву
37 слайд

В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Код символа по бинарному дереву
38 слайд

В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Код символа по бинарному дереву
39 слайд

В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Код символа по бинарному дереву
Код для буквы В
40 слайд

В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Код символа по бинарному дереву
Код для буквы Г
41 слайд

В
Г
Д
0
1
0
1
0
1
А
Б
0
1
Код символа по бинарному дереву
Код для буквы Г
42 слайд

Код символа по бинарному дереву
43 слайд

Сокращение двоичного кода
Тип задачи №1
44 слайд

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

Задача 1
Код: А – 10; Б – 11; В – 000; Г – 001; Д – 010.

Построим бинарное дерево.
Коды листов известны по условию задачи
46 слайд

Задача 1
Код:
А – 10;
Б – 11;
В – 000;
Г – 001;
Д – 010.

А
Б
0
1
0
1
0
1
В
Г
0
1
Д
0
1
47 слайд

Задача 1
Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
А
Б
0
1
0
1
0
1
В
Г
0
1
Д
0
1
Как видим у этого узла два листочка.
Левый листок Д, а правый листок пустой.
48 слайд

Задача 1
Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
А
Б
0
1
0
1
0
1
В
Г
0
1
Д
0
1
Как видим у этого узла два листочка.
Левый листок Д, а правый листок пустой.
49 слайд

Задача 1
Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
А
Б
0
1
0
1
0
1
В
Г
0
1
Д
0
1

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

Задача 1
Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
А
Б
0
1
0
1
0
1
В
Г
0
1
Д
0
1
51 слайд

Задача 1
Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
А
Б
0
1
0
1
0
1
В
Г
0
1
Д
После порезав ветки узел превратился в листок
52 слайд

Задача 1
Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
А
Б
0
1
0
1
0
1
В
Г
0
1
Д
После порезав ветки узел превратился в листок (одно свободное место)
53 слайд

Задача 1
Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
А
Б
0
1
0
1
0
1
В
Г
0
1
Д
Перемещаем опавшую Д в пустой листок
54 слайд

Задача 1
Как можно сократить длину кодового слова для буквы Д так, чтобы код по-прежнему можно было декодировать однозначно?
Д
А
Б
0
1
0
1
0
1
В
Г
0
1
Теперь
код буквы Д равен 01
55 слайд

Ответ
Длину кодового слова для буквы Д
можно сократить до 01
56 слайд

Выбор кода для одной буквы
Тип задачи №2
57 слайд

Задача 2
По каналу связи передаются сообщения, содержащие только шесть букв: У, Р, А, Е, Г, Э; для передачи используется двоичный код, удовлетворяющий условию Фано.
Буквы Е, Р, А, Г, У имеют коды 01, 000, 100, 101, 110 соответственно. Укажите код наименьшей длины для буквы Э.
Если в качестве кода может быть использовано несколько кодов одинаковой длины, выбрать тот, числовое значение которого меньше.
58 слайд

Задача 2
Буквы Е, Р, А, Г, У имеют коды 01, 000, 100, 101, 110 соответственно.
Е
0
1
0
1
0
1
Р
0
1
А
Г
0
1
У
1
0
59 слайд

Задача 2
Укажите код наименьшей длины для буквы Э.
Е
0
1
0
1
0
1
Р
Э
0
1
А
Г
0
1
У
Э
1
0
Букву Э можно поставить в один из двух листочков
001
111
60 слайд

Задача 2
Сравним два получившихся числа

Для удобства можно перевести в десятичную систему счисления
001 2 = 1 10
111 2 = 7 10
61 слайд

Задача 2
Сравним два получившихся числа
62 слайд

Задача 2
Сравним два получившихся числа

1 меньше 7, следовательно 001 меньше 111
Ответ: код наименьшей длины для буквы Э — 001
63 слайд

Помехоустойчивые коды
Тип задачи №3
64 слайд

Задача 3
По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы: А, Б, В, Г.
Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех.
Для кодирования букв Б, В, Г используются 5-битовые кодовые слова: Б – 00001, В – 01111, Г – 10110.
5-битовый код для буквы А начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы А.
65 слайд

Задача 3
Пример
0 0 0 0 1
кодовое слово
позиция
66 слайд

Задача 3
Сравним позиции кодовых слов Б, В, Г с позициями кодового слова А
67 слайд

Задача 3
Сравним первые позиции
кодовых слов А и Б
1 0
1 = 0 ?
68 слайд

Задача 3
Сравним первые позиции кодовых слов А и В
1 0
1 = 0 ?
69 слайд

Задача 3
Сравним первые позиции кодовых слов А и Г
1 1
1 = 1 ?
70 слайд

Задача 3
Теперь сравниваем последние позиции
71 слайд

Задача 3
0
1
1
0
?
А=Б
0=1
?
А=В
0=1
?
А=Г
0=0
73 слайд

Задача 3
У кодового слова буква Б сошлись две позиции.
По условию: любые два слова из набора отличаются не менее чем в трёх позициях.
У нас уже есть две одинаковые позиции значит остальные три должны быть различные.
74 слайд

Задача 3
У кодового слова буква Б сошлись две позиции.
По условию: любые два слова из набора отличаются не менее чем в трёх позициях.
У нас уже есть две одинаковые позиции значит остальные три должны быть различные.
75 слайд

Задача 3
Если вторая позиция у кодового слова Г равна 0, следовательно вторая позиция у кодового слова А равна НЕ Г (¬ г).
¬0 (НЕ 0)
76 слайд

Задача 3
Если вторая позиция у кодового слова Г равна 0, следовательно вторая позиция у кодового слова А равна НЕ Г (¬ г).
¬0 (НЕ 0)
77 слайд

Задача 3
¬1 (НЕ 1)
78 слайд

Задача 3
¬1 (НЕ 1)
79 слайд

Задача 3
Ответ: кодовое слово для буквы А равно 11000
80 слайд

Выбор кодов для нескольких букв
Тип задачи №4
81 слайд

Задача 4
Для кодирования некоторой последовательности, состоящей из букв П, О, Е, Х, А, Л, И, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.
Для букв О, Е, А, И использовали соответственно кодовые слова 01, 110, 1010, 001.
Найдите наименьшую возможную суммарную длину всех кодовых слов.
82 слайд

Задача 4
Для букв О, Е, А, И использовали соответственно кодовые слова 01, 110, 1010, 001.

О
0
1
0
1
0
1
И
0
1
Е
0
1
0
1
А
0
1
83 слайд

Задача 4
Некоторая последовательность, состоит из букв П, О, Е, Х, А, Л, И
О
0
1
0
1
0
1
П
И
0
1
Е
Л
0
1
Х
0
1
А
0
1
Для букв П Х Л нет кода.
Добавим его самостоятельно.
84 слайд

Задача 4
Некоторая последовательность, состоит из букв П, О, Е, Х, А, Л, И
О
0
1
0
1
0
1
П
И
0
1
Е
Л
0
1
Х
0
1
А
0
1
Оставшийся листик 1011 мы не берём т.к в нём самое большое количество знаков чем в остальных
85 слайд

Задача 4
Допишем оставшиеся коды.
86 слайд

Задача 4
Подсчитаю количество знаков
87 слайд

Задача 4
П+О+Е+Х+А+Л+И = 3+2+3+3+4+3+3 = 21
Ответ: наименьшая возможная суммарная длина всех кодовых слов равна 21
88 слайд

Примечание
Предположим для буквы Л выбрали код 1011 вместо кода 111, тогда
О
0
1
0
1
0
1
П
И
0
1
Е
0
1
Х
0
1
А
Л
0
1
П+О+Е+Х+А+Л+И = 3+2+3+3+4+4+3 = 22
89 слайд

Декодирование
Тип задачи №5
90 слайд

Задача 5
Заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений.
Известно, что все кодовые слова содержат не меньше двух и не больше трёх двоичных знаков, а слову КАПОТ соответствует код 11000111110011. Какой код соответствует слову ТОК?
91 слайд

Задача 5
Рассмотрим внимательно код 11000111110011
С первого взгляда можно сказать что количество 1 больше чем количество 0, из чего можно сделать вывод что левая ветка будет иметь минимум третий уровень, т.к. одна буква шифруется тремя знаками.
Набрасываем бинарное дерево
1
1
0
1
0
0
92 слайд

Задача 5
Про просмотре кода
1 1 0 0 0 1 1 1 1 1 0 0 1 1
В глаза бросается большое скопление 1 в середине.
1
1
0
1
0
0
93 слайд

Задача 5
Предположим что код 111 — П
1 1 0 0 0 1 1 1 1 1 0 0 1 1
Тогда
1 1 0 0 0 1 .1 1 1 .1 0 0 1 1

* Если 111 листок, следовательно 11 и 1 это узел, в которых не может быть букв.

1
1
П
0
1
0
0
94 слайд

Задача 5
От 111 справа на лево распределим ещё две буквы под два символа
1 1 0 . 0 0 1 . 1 1 1 . 1 0 0 1 1
Поскольку кодовое слово начинается на К,
то 110 – К, следовательно 001 – А.
Дорисовываем дерево.
*Если 110 или 001 листок,
следовательно 11 и 1 это узел, в которых не может быть букв.

1
1
К
П
0
1
0
0
0
1
А
0
1
95 слайд

Задача 5
Осталось 5 символов которые можно разложить на 100 и 11, или на 10 и 011
1 1 0 . 0 0 1 . 1 1 1 . 1 0 0 1 1
Листок 100 существует А вот листочка 11 быть не может. Мы уже сказали что это узел, а в узле не может быть буквы. Это вариант вычёркиваем.
1
1
К
П
0
1
0
0
0
1
А
0
1
0
1
96 слайд

0
Задача 5
Остался вариант 10 и 011
1 1 0 . 0 0 1 . 1 1 1 . 1 0 . 0 1 1
Подставлю буквы соответственно О и Т.
О
1
1
К
П
0
1
0
0
1
А
0
1
0
1
Т
97 слайд

Задача 5
Запишем результат в таблицу
98 слайд

Задача 5
С помощью таблицы закодируем слово ТОК

Ответ: слову ТОК соответствует код 01110110
99 слайд

Список литературы
100 слайд

Список литературы
1. Учебник для 11 класса : в 2 ч. Ч. 1 / К. Ю. Поляков, Е. А. Ере- мин. — М. : БИНОМ. Лаборатория знаний, 2020
2. Богомолова О.Б., Усенков Д.Ю. Фано и его «коллеги»: растим дерево. // компьютерные инструменты в школе – 2017 – Выпуск №2 — С. 26-31. Режим доступа: http://ipo.spb.ru/journal/index.php?article/1873/, свободный.
3. Задачи для подготовки ЕГЭ https://kpolyakov.spb.ru/school/ege/generate.htm

Краткое описание документа:

ЕГЭ-2022 информатикаРазбор задания 4 — Кодирование и декодирование информацииВ материале представлены теория, пять видов задач и список одновной литературы, необходимые для решения задания 4 ЕГЭ информатика.

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 153 824 материала в базе

Выберите категорию:
Выберите учебник и тему

Выберите класс:
Тип материала:
- Все материалы
- Статьи
- Научные работы
- Видеоуроки
- Презентации
- Конспекты
- Тесты
- Рабочие программы
- Другие методич. материалы

Найти материалы

Материал подходит для УМК

Другие материалы

29.10.2021
92
0

Вам будут интересны эти курсы:

Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс повышения квалификации «Облачные технологии в образовании»
Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»
Курс профессиональной переподготовки «Информационные технологии в профессиональной деятельности: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс профессиональной переподготовки «Теория и методика обучения информатике в начальной школе»
Курс повышения квалификации «Современные тенденции цифровизации образования»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»
Курс повышения квалификации «Применение интерактивных образовательных платформ на примере платформы Moodle»

Источник

в условии
в решении
в тексте к заданию
в атрибутах

Категория:

Атрибут:

Всего: 388 1–20 | 21–40 | 41–60 | 61–80 …

Добавить в вариант

Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите наибольшую длину цепочки символов, среди которых нет символов K и L, стоящих рядом.

Например, в тексте ABCAABAKLD самая длинная цепочка символов, удовлетворяющая условию  — ABCAABAK, её длина равна 8.

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

Задание 24

Источник: ЕГЭ−2021 по информатике 24.06.2021. Основная волна. Разные задачи

Элементами множеств А, P, Q являются натуральные числа, причём P = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}, Q  =  {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}. Известно, что выражение

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

истинно ( т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10303

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальную длину цепочки вида XYZXYZXYZ… (составленной из фрагментов XYZ, последний фрагмент может быть неполным).

Задание 24

Текстовый файл состоит не более чем из 10⁶ символов A, B и C. Определите максимальную длину цепочки вида ABABAB… (составленной из фрагментов AB, последний фрагмент может быть неполным).

Задание 24

Текстовый файл состоит не более чем из 10⁶ символов L, D и R. Определите максимальную длину цепочки вида LDRLDRLDR… (составленной из фрагментов LDR, последний фрагмент может быть неполным).

Задание 24

Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}.

Известно, что выражение

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

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наибольшее возможное количество элементов в множестве A.

Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q  =  {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}.

Известно, что выражение

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

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.

Задание 24

Источник: Демонстрационная версия ЕГЭ−2021 по информатике

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 75 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 68.

Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 68 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 67.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

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

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

Входные данные.

Задание 26

В первой строке входного файла находятся два числа: S  — размер свободного места на диске (натуральное число, не превышающее 10 000) и N  — количество пользователей (натуральное число, не превышающее 3000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

Пример входного файла:

100 4

При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар  — 50, поэтому ответ для приведённого примера:

2 50

Ответ:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может

добавить в кучу один камень или

увеличить количество камней в куче в четыре раза.

Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 40 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 64.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

добавить в кучу один камень или

увеличить количество камней в куче в четыре раза.

В начальный момент в куче было S камней, 1 ≤ S ≤ 64.

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

добавить в кучу один камень или

увеличить количество камней в куче в четыре раза.

В начальный момент в куче было S камней, 1 ≤ S ≤ 64.

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

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

добавить в кучу один камень или

увеличить количество камней в куче в четыре раза.

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 80.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

добавить в кучу один камень или

увеличить количество камней в куче в четыре раза.

В начальный момент в куче было S камней, 1 ≤ S ≤ 80.

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

добавить в кучу один камень или

увеличить количество камней в куче в четыре раза.

В начальный момент в куче было S камней, 1 ≤ S ≤ 80.

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

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 38. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 38 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 37.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в кучу один камень (действие А) или утроить количество камней в куче, а затем добавить ещё один камень (действие Б). Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 31 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится более 31. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 32 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 31.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в кучу один камень (действие А) или утроить количество камней в куче, а затем добавить ещё один камень (действие Б). Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 31 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится более 31. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 32 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 31.

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в кучу один камень (действие А) или утроить количество камней в куче, а затем убрать из кучи один камень (действие Б). Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 29 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится более 32. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 32.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить в кучу один камень (действие А) или утроить количество камней в куче, а затем убрать из кучи один камень (действие Б). Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 29 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится более 32. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 32.

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в шесть раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 60 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче превышает 365. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 366 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 365.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Игра завершается в тот момент, когда количество камней в куче превышает 361. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 362 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 360.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в 3 раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 30 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 29.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 65 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 64.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 47. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 47 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤46.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Всего: 388 1–20 | 21–40 | 41–60 | 61–80 …

Источник

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: базовый.
Средний процент выполнения: 84.4%
Ответом к заданию 4 по информатике может быть цифра (число) или слово.

Разбор сложных заданий в тг-канале

Задачи для практики

Задача 1

По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 7 букв В и 5 букв Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.

Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: А – 00, Б – 01, В – 10, Г – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 15$·$2+10$·$2+7$·$2+5$·$2=74. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: А – 0, Б – 10, В – 110, Г – 111. Тогда длина закодированного сообщения будет 15$·$1+10$·$2+7$·$3+5$·$3=71. Следовательно, такой вариант нас устраивает, данный код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 71.

Ответ: 71

Задача 2

По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 14 букв Б, 12 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.

Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: А – 00, Б – 01, В – 10, Г – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 15$·$2+14$·$2+12$·$2+4$·$2=90. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: А – 0, Б – 10, В – 110, Г – 111. Тогда длина закодированного сообщения будет 15$·$1+14$·$2+12$·$3+4$·$3=91. Следовательно, такой вариант нас не устраивает, первый код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 90.

Ответ: 90

Задача 3

По каналу связи передаются сообщения, каждое из которых содержит 20 букв Е, 18 букв И, 16 букв К и 10 букв П (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.

Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: Е – 00, И – 01, К – 10, П – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 20$·$2+18$·$2+16$·$2+10$·$2=128. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: Е – 0, И – 10, К – 110, П – 111. Тогда длина закодированного сообщения будет 20$·$1+18$·$2+16$·$3+10$·$3=134. Следовательно, такой вариант нас не устраивает, первый код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 128.

Ответ: 128

Задача 4

По каналу связи передаются сообщения, каждое из которых содержит 18 букв Е, 10 букв И, 8 букв К и 6 букв П (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.

Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.

Решение

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

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

На основе дерева получим кодовые слова 00, 01, 10 и 11. Все слова имеют длину 2. Учитывая количество вхождений каждой из букв в сообщение, получим, что в этом случае длина закодированного сообщения равна 2 · (18 + 10 + 8 + 6) = 84.

На основе дерева получим кодовые слова 0, 01, 110 и 111.

Чтобы общая длина кодового сообщения была наименьшей, следует назначить букве, встречающейся наибольшее число раз, кодовое слово наименьшей длины. Например, Е — 0, И — 01, К — 110 и П — 111.

В этом коде длины кодовых слов для букв Е, И, К и П равны 1, 2, 3 и 3 соответственно. Учитывая количество вхождений каждой из букв в сообщение, получим, что в этом длина закодированного сообщения равна 1 · 18 + 2 · 10 + 3 · 8 + 3 · 6 = 80.

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

Ответ: 80

Задача 5

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

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10 и 110, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 0 или 111. Взять в качестве кодового слова 0 нельзя, т.к. в таком случае невозможно будет найти другие кодовые слова, удовлетворяющие условию Фано для оставшихся сообщений. Таким образом, можем использовать 00, 010, 011, 111. Суммарная длина всех кодовых слов – 16.

Ответ: 16

Задача 6

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

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

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10 и 111, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 0 или 110. Взять в качестве кодового слова 0 нельзя, т.к. в таком случае невозможно будет найти другие кодовые слова, удовлетворяющие условию Фано для оставшихся сообщений. Таким образом, можем использовать 00, 01, 110. Суммарная длина всех кодовых слов – 12.

Ответ: 12

Задача 7

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

Решение

Согласно условию задачи, искомый код должен содержать кодовые слова 1 и 010. Значит, узлы, соответствующие эти кодовым словам, должны быть листьями. На основе этих данных построим дерево.

Однако построенное дерево соответствует коду, содержащему только 4 кодовых слова. По условию задачи требуется пять кодовых слов. Для этого следует продолжить построение дерева для одного из узлов: 00 или 011.

Продолжив построение из узла 00, мы получим кодовые слова 000, 001, 010, 011, 1. Суммарная длина всех кодовых слов равна 3 + 3 + 3 + 3 + 1 = 13.

Продолжив построение из узла 0110, мы получим кодовые слова 00, 010, 0011, 0111, 1. Суммарная длина всех кодовых слов равна 2 + 3 + 4 + 4 + 1 = 14.

Следовательно, наименьшая возможная длина всех кодовых слов равна 13.

Ответ: 13

Задача 8

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

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

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кода буквы Б. Если заменить код на 0, то он будет являться началом кодов букв В, Г и Д. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву Б, закодировав её словом 1. В таком случае нарушения условия Фано не произойдёт.

Ответ: б1

Задача 9

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

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

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

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б и В. Если заменить код на 0, то он будет являться началом кодов букв Г и Д. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 11. В таком случае нарушения условия Фано не произойдёт.

Ответ: в11

Задача 10

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б, Г и Д. Если заменить код на 0, то он будет являться началом кода буквы В. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 00. В таком случае нарушения условия Фано не произойдёт.

Ответ: в00

Задача 11

Решение

Для решения данной задачи построим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого). Префиксный код является однозначно декодируемым. На рисунке представлено дерево, соответствующее заданному коду.

При сокращении кодового слова в дереве нужно заменить один из полученных листьев узлом более высокого уровня. Такая возможность есть только для кодового слова буквы Г. Вместо листа 100 можно взять узел более высокого уровня 10.

В этом случае полученный код: А — 00, Б — 01, В — 110, Г — 10, Д — 111 — будет префиксным и однозначно декодируемым.

Ответ: г10

Задача 12

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 10, Б − 11, В − 000, Г − 001. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10, 11, 000, 001, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 01. Слово 01 можно использовать в качестве кодового, т.к. условие Фано для него выполняется. Это кодовое слово является минимальным, т.к. любой код меньший длины в данном случае не будет удовлетворять условию Фано.

Ответ: 01

Задача 13

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

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 00, 011, 010, 10, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 11. Слово 11 можно использовать в качестве кодового, т.к. условие Фано для него выполняется. Это кодовое слово является минимальным, т.к. любой код меньший длины в данном случае не будет удовлетворять условию Фано.

Ответ: 11

Задача 14

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 000, Б − 001, В − 010, Г − 011. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 000, 001, 010, 011, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 1. Слово 1 можно использовать в качестве кодового, т.к. условие Фано для него выполняется.

Ответ: 1

Задача 15

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

Задача 16

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

Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки кодированных сообщений.

Задача 17

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

Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки кодированных сообщений.

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

Кодирование и расшифровка сообщений

Описание презентации по отдельным слайдам:

Краткое описание документа:

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

Материал подходит для УМК

Другие материалы

Вам будут интересны эти курсы:

Задачи для практики

Задача 1

Решение

Задача 2

Решение

Задача 3

Решение

Задача 4

Решение

Задача 5

Решение

Задача 6

Решение

Задача 7

Решение

Задача 8

Решение

Задача 9

Решение

Задача 10

Решение

Задача 11

Решение

Задача 12

Решение

Задача 13

Решение

Задача 14

Решение

Задача 15

Задача 16

Задача 17

Рекомендуемые курсы подготовки