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

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

Тип 4 № 15915

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, И — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?

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

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

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

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

Заметим, что после кодирования всех букв, входящих в слово ГРАММ, должен остаться хотя бы один свободный код для кодирования буквы Я, которая не входит в данное слово, но может передаваться по каналу связи. Проверить наличие свободного кода можно, построив дерево кодов, как показано в задаче 18553.

ЕГЭ по информатике 2021 — Задание 4 (Условие Фано)

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ: 151646.

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

МЦКО по информатике 10 класс. Диагностика на апрель 2022 демоверсия (задания и ответы)

Диагностическая работа МЦКО проводится 27 апреля 2022 г. с целью определения уровня подготовки обучающихся 10-х классов по информатике и ИКТ и выявления элементов содержания, вызывающих наибольшие затруднения.

Купить официальные варианты МЦКО 2021-2022 учебного года: Купить

1. Структура и содержание диагностической работы
Каждый вариант диагностической работы состоит из 20 заданий: 14 заданий с кратким ответом, 5 заданий с выбором ответа и 1 задания с развёрнутым ответом. Содержание диагностической работы охватывает учебный материал, освоенный к моменту проведения диагностики, включённый в основные учебно-методические комплекты по географии, используемые в Москве в 5–10-х классах.

2. Время выполнения работы
На выполнение работы отводится 65 минут.

3. Условия проведения диагностической работы
При организации и проведении работы необходимо строгое соблюдение технологии независимой диагностики. Обучающиеся должны быть обеспечены непрограммируемыми калькуляторами. В состав проверочной работы включены карты и статистическая таблица. Диагностическая работа проводится в компьютерной форме.

Официальная демоверсия МЦКО: Скачать в PDF (+ доп.файлы)

Смотреть работу МЦКО онлайн на сайте:

Сложные задания:

3. По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, З, О, Ы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 1110, О – 01,
З – 110. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВЫЗОВ?

4. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) Затем справа дописываются два разряда: символы 10, если число N чётное, и 11, если нечётное.
3) Если количество единиц получилось чётным, то справа дописывается цифра 0, иначе справа дописывается цифра 1. Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого автомат получает число R, большее 53. В ответе найденное число N запишите в десятичной системе.

6. Музыкальный фрагмент был записан в формате стерео (двухканальная запись), оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла – 120 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате моно (одноканальная запись) и оцифрован с разрешением в 2 раза ниже и частотой дискретизации в 3 раза выше, чем в первый раз. Сжатие данных также не производилось. Укажите размер файла в Мбайт, полученного при повторной записи.

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

8. С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «три» в тексте пьесы М. Горького «На дне» в файле 8.docx. Слова должны начинаться со строчной буквы. Другие формы слова «три», такие как «тридцать», «триумф» и т. д., учитывать не следует. В ответе укажите только число.

9. В некоторой фирме каждый сотрудник получает электронный пропуск, на котором записан личный код, состоящий из двух частей. Первая часть кода содержит 8 символов, каждый из которых может быть одной из 26 строчных латинских букв. Вторая часть кода содержит 6 символов, каждый из которых может быть одной из десятичных цифр. При этом в базе данных сервера формируется запись, содержащая этот код и дополнительную информацию о пользователе. Для представления кода используют посимвольное кодирование, все символы в пределах одной части кода кодируют одинаковым минимально возможным для этой части количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Для хранения данных о 64 пользователях потребовалось 2 Кбайт. Сколько байтов выделено для хранения дополнительной информации об одном пользователе? В ответе запишите только целое число – количество байтов.

14. В файле 14.txt содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно. Определите и запишите в ответе сначала количество пар элементов последовательности, в которых оба числа делятся на 4 без остатка, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности. Например, для последовательности из пяти элементов: 6; 4; 8; –12; 6 – ответ: 2 12. В ответ запишите два числа, не разделяя их запятыми и пробелами.

Какое наименьшее количество двоичных знаков потребуется для кодирования слова МОЛОКОСОС?

Какое наименьшее число контейнеров и какого типа потребуется для перевозки краски
Изготовлено К банок краски. Для перевозки есть контейнеры размером 0,5*0,5 метров и 0,8*0,8 метров.

Какое количество теплоты потребуется для нагревания водорода
Какое количество теплоты потребуется для нагревания водорода массой m=0,3кг от температуры Т1=300К.

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

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

Ну, если префиксный Хэмминга, то

М — 0000, Л — 0001, К — 001, С — 01, О — 1

0000100011001101101 — 19 бит

Добавлено через 41 минуту
переделал:
25 бит (строя дерево Хаффмана):

К 001
Л 0000
М 00010
Н 100
О 01
П 00011
Р 11
С 101

Добавлено через 1 час 37 минут
извиняюсь 26 бит
просчитался))

Добавлено через 2 часа 55 минут
кто нибудь проверьте и скажите правильно ли я решил?

Сообщение было отмечено goldolov_na как решение

Решение

Определить, какое количество рулонов каждого типа потребуется для оклейки комнаты
Здравствуйте. Нужно подправить задачку, вот условие: В распоряжении ремонтной бригады имеются.

Какое наименьшее количество плит понадобится для замощения площади?
Театральная площадь в столице Берляндии представляет собой прямоугольник n × m.

Какое минимальное количество времени потребуется, чтобы открыть чемодан?
Женя — большой любитель путешествий, поэтому в качестве подарка на Новый Год родители решили.

Определить какое наименьшее количество плит понадобится для замощения площади
Хао форумчанам! На днях столкнулся с задачкой, которую вроде бы решил, но Online judge system при.

Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?
Спичечная модель Профессор Самоделкин решил изготовить объемную модель кубиков из спичек.