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

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

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

Скачай курс
в приложении

Перейти в приложение
Открыть мобильную версию сайта

© 2013 — 2023. Stepik

Наши условия использования и конфиденциальности

Get it on Google Play

Public user contributions licensed under cc-wiki license with attribution required

Самостоятельная работа по информатике по теме «Префиксные коды» (10 класс)

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

1. По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, З, И, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 101, В — 010, И — 00. Какое наименьшее количество двоичных знаков потребуется для кодирования слова НЕВЕЗЕНИЕ?

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

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

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

Какой набор букв закодирован двоичной строкой 1000110110110? Все буквы в последовательности — разные.

3. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 1; Б — 0100; В — 000; Г — 011; Д — 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?

1) для буквы Г — 11

2) для буквы В — 00

3) для буквы Г — 01

4) это невозможно

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

1) это невозможно

2) для буквы А — 0

3) для буквы В — 00

4) для буквы Д — 01

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

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

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

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

1.Буква А повторяется в слове КАТАРАКТА чаще всего, поэтому закодируем её кодовым словом 1. Следующую букву невозможно закодировать кодовым словом длиной 2, так как будет невозможно закодировать другие буквы так, чтобы выполнялось условие Фано. Букву К закодируем кодовым словом длиной 3, например, 000. Буквы Р и В закодируем кодовыми словами 0011 и 0010. Тогда количество двоичных знаков, которые потребуются для кодирования слова КАТАРАКТА равно 4 · 1 + 2 · 3 + 2 · 3 + 4 = 20.

1. Буква Е повторяется в слове НЕВЕЗЕНИЕ чаще всего, поэтому закодируем её кодовым словом 11. Буква Н повторяется в слове НЕВЕЗЕНИЕ 2 раза, поэтому закодируем её кодовым словом 100. Букву З закодировать кодовым словом длины 3 нельзя, поскольку не останется кодовых слов для оставшихся букв, которые удовлетворяли бы условию Фано. Поэтому букву З закодируем кодовым словом 0110. Тогда количество двоичных знаков, которые потребуются для кодирования слова НЕВЕЗЕНИЕ равно 4 · 1 + 2 · 5 + 3 · 3 = 23.

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

Разбор задачи № 5. Кодирование и декодирование. Условие Фано

Теория по задаче

Разбор текущей задачи

Условие задачи

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

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

26 февраля 2023 Информатика ЕГЭ 2023 тренировочный пробник с ответами

егэ 2023 информатика

В задании 27 для файла А дано количество пунктов, при котором между пунктами сбора мусора будет четное количество контейнеров, а для файла В — нечетное. В разборе решение для файла В работало так, как будто между пунктами сбора мусора четное количество, что давало неверный ответ.

Сейчас сделано следующее: файл остался прежним, на сайте и в pdf версии актуальные ответы. Представленное в разборе решение 27В является верным только для варианта с четным количеством контейнеров.

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

Видео решение варианта

Таймкоды

00:00 Анализ результатов
04:49 Задание 1
07:42 Задание 2
13:54 Задание 3
17:29 Задание 4
21:24 Задание 5
32:09 Задание 6
35:33 Задание 7
37:53 Задание 8
44:45 Задание 9
56:32 Задание 10
57:31 Задание 11
59:20 Задание 12
1:04:37 Задание 13
1:07:54 Задание 14
1:09:45 Задание 15
1:12:56 Задание 16
1:18:03 Задание 17
1:21:48 Задание 18
1:24:49 Задание 19
1:30:35 Задание 20
1:32:05 Задание 21
1:32:47 Задание 22
1:37:42 Задание 23
1:45:40 О курсе
1:46:35 Задание 24
1:55:28 Задание 25
2:00:15 Задание 26
2:06:49 Задание 27А
2:23:20 Задание 27В
2:33:07 Заключение

1. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта B в пункт C и из пункта F в пункт G. В ответе запишите целое число.

2. Логическая функция F задаётся выражением (w ≡ y) \/ ((¬x → z) ∧ (¬z → y)). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид. В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать: yx

3. В файле приведён фрагмент базы данных Chinook Database, описывающей цифровой медиа магазин. База данных состоит из четырех таблиц. Таблица «Группы» содержит информацию о музыкальных коллективах: ID, название. Таблица «Альбомы» содержит информацию о студийных музыкальных альбомах: ID, название, ID группы. Таблица «Жанр» содержит информацию о музыкальных жанрах: ID, название. Таблица «Треки» содержит информацию о музыкальных файлах: ID, название, ID альбома, ID жанра, длительность (в миллисекундах), размер файла (в байтах). На рисунке приведена схема базы данных. Используя информацию из приведённой базы данных, определите суммарный размер треков группы «Foo Fighters”, написанных в жанре «Рок». Полученное число выразите в МБ. В ответе укажите только целую часть полученного значения.

4. По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, И, К, Л, О, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: И – 0, Я – 1001, A — 1010. Для четырех оставшихся букв З, К, Л и О кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КОЛЛИЗИЯ, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

5. По каналу связи передаются трехзначные числа. Для каждой пары таких чисел строится контрольная сумма, необходимая для обнаружения ошибок при передаче. Контрольная сумма строится следующим образом: 1. записывается сумма разрядов сотен исходных чисел 2. справа дописывается сумма разрядов десятков исходных чисел 3. слева дописывается сумма разрядов единиц исходных чисел 4. контрольная сумма — это три цифры полученного числа: число тысяч, сотен и десятков. Пример: передаются числа 473 и 934. Сумма разрядов сотен равна 13, сумма разрядов десятков равна 10, сумма разрядов единиц 7. Получаем число 71310, контрольная сумма 131. Определите, при каком наибольшем значении первого числа пары контрольная сумма будет равна 2?

6. Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, и Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм: Повтори 6 [Вперёд 10 Направо 90] Вперёд 2 Направо 90 Повтори 2 [Вперёд 15 Направо 90 Вперёд 4 Направо 90] Определите, сколько точек с целочисленными координатами будут находиться внутри пересечения фигур, ограниченных заданными алгоритмом линиями, включая точки на границах этого пересечения.

7. Музыкальный фрагмент был записан в формате стерео (двухканальная запись), оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла без учёта размера заголовка файла – 48 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате моно и оцифрован с разрешением в 1,5 раза выше и частотой дискретизации в 3 раза меньше, чем в первый раз. Размер полученного файла без учёта размера заголовка файла – 6 Мбайт. При повторной оцифровке использовалось сжатие. Определите коэффициент сжатия (отношение размеров несжатого и сжатого файла).

8. Все пятибуквенные слова, в составе которых могут быть только русские буквы К, О, Ф, Е, записаны в алфавитном порядке и пронумерованы начиная с 1. Ниже приведено начало списка. 1. ЕЕЕЕЕ 2. ЕЕЕЕК 3. ЕЕЕЕО 4. ЕЕЕЕФ 5. ЕЕЕКЕ … Определите сумму номеров первого и последнего слов в списке, в которых только одна буква О и при этом никакая согласная буква не стоит рядом с буквой О.

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

10. Текст произведения Николая Васильевича Гоголя «Мертвые души» представлен в виде файлов различных форматов. Откройте один из файлов и определите, сколько раз встречается в тексте слова с сочетанием букв «род», например, «борода», «городом». Отдельные слова «род» и «Род» учитывать не следует. В ответе запишите только число.

11. При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 196 символов и содержащий только десятичные цифры и символы из 1550-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 2048 пользователях потребовалось 604 Кбайта. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

12. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. 1. заменить (v, w) 2. нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось(12) ИЛИ нашлось(21) ЕСЛИ нашлось(12) ТО заменить(12, 21) ИНАЧЕ заменить(21, 111) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ На вход программы поступает строка из n цифр, содержащая равное количество цифр 1, 2, расположенных в произвольном порядке. При каком минимальном значении n в строке, полученной в результате работы программы, количество цифр 1 будет больше 100?

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

14. В выражении 451×18 + 79×218 x обозначает некоторую цифру из алфавита системы счисления c основанием 18. Определите наименьшее значение x, при котором значение данного выражения кратно 27. Для найденного x вычислите частное от деления данного выражения на 27 и запишите его в ответе в десятичной системе счисления.

15. На числовой прямой даны три отрезка: D = [15; 40], C = [21; 63] и А = [7; E]. Укажите наименьшее возможное целое значение E такое, что формула (x ∈ D) → ((¬(x ∈ C) /\ ¬(x ∈ A)) → ¬(x ∈ D)) истинна (то есть принимает значение 1 при любом значении переменной х).

16. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями F(n) = 1 при n > 3000; F(n) = F(n + 1) — n + 1, если n ≤ 3000 и при этом n чётно; F(n) = F(n + 2) — 2 × n + 2, если n ≤ 3000 и при этом n нечётно. Чему равно значение выражения 2 × F(39) — 2 × F(34)?

17. В файле содержится последовательность целых чисел. Элементы последовательности могут принимать значения от -10 000 до 10 000 включительно. Определите количество элементов последовательности, которые делятся на 3, не делятся на 7, 17 и являются делителем максимального элемента последовательности, оканчивающегося на 2. В ответе запишите количество найденных чисел, затем максимальное найденное число.

19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в любую из куч один или три камня либо увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается в тот момент, когда количество камней в одной из куч становится не менее 479. Победителем считается игрок, сделавший последний ход, т.е. первым получивший в одной из куч 479 камней или больше. В начальный момент в первой куче было 239 камней, во второй куче было S камней; 1 ≤ S ≤ 478. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

20. Для игры, описанной в предыдущем задании, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.

21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

22. В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.

23. Исполнитель Три Команды преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 2 3. Умножить на 3 Первая команда увеличивает число на экране на 1, вторая увеличивает число на 2, третья умножает его на 3. Программа для исполнителя Три Команды – это последовательность команд. Сколько существует программ, состоящих не более чем из 3 команд, для которых при исходном числе 4 результатом является четное число?

24. Текстовый файл состоит не более чем из 1 200 000 символов X, Y, и Z. Определите максимальное количество идущих подряд пар символов вида согласная + гласная среди которых нет подстроки XYZY. Для выполнения этого задания следует написать программу. Примечание. Букву Y считайте всегда гласной.

25. Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: – символ «?» означает ровно одну произвольную цифру; – символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих 108 , найдите все числа, соответствующие маске *15*7424, которые делятся без остатка только на одно из чисел 111, 113, 127. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на одно из чисел 111, 113, 127, на которое число делится без остатка.

26. Строительная организация возводит два высотных здания, находящихся на расстоянии M друг от друга. Из-за коммунальной аварии потребовалось срочно протянуть трубу от одного здания к другому. В распоряжении организации имеется N труб единичной длины. Известен диаметр каждой трубы. Трубы можно скреплять между собой только при условии, что их диаметр отличается не более чем на 3 единицы. Определите максимальную пропускную способность полученной трассы. Пропускная способность — это минимальный диаметр среди всех труб, из которых построена трасса. Для найденного значения пропускной способности определите самый большой диаметр трубы, который может быть получен в данной трассе при условии, что компания хочет сэкономить на трубах и возьмет трубы как можно меньшего диаметра. Входные данные В первой строке входного файла находятся два числа: N – количество имеющихся труб (натуральное число, не превышающее 20 000) и M — расстояние между зданиями (натуральное число, не превышающее 20 000). Каждая из следующих N строк содержит натуральные числа, не превышающие 1000: диаметры труб.

27. На каждом километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна N километров. Нулевой километр и N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров. Из каждого пункта мусор вывозит отдельный мусоровоз. Стоимость доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до ближайшего центра переработки. На автодороге расположено два центр переработки отходов, каждый в одном из пунктов сбора мусора. Расстояние между центрами переработки одинаково, независимо от направления движения по кольцевой автодороге. Центры переработки расположены таким образом, что общая стоимость доставки мусора из всех пунктов минимальна.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *