Надо много учиться, чтобы осознать, что знаешь мало.
Мишель де Монтень

Задание № 8 (в 2020 году это было задание № 10)

Спецификация контрольных измерительных материалов единого государственного экзамена по информатике и ИКТ

Проверяемые элементы содержания	Уровень сложности задания	Макс. балл за выполнение задания	Примерное время выполнения задания (мин.)
Знания о методах измерения количества информации	Базовый	1	4

Теория

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

Материалы единой коллекции ЦОР (цифровых образовательных ресурсов):
Материалы с сайта Фоксфорд
- Алфавитный подход к измерению количества информации (Обратите внимание на то, что мощность алфавита здесь обозначается как М, а не как N, и количество символов в сообщении обозначили как N, а не k)

Практика

Разберем примеры заданий из ЕГЭ

1. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.

Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА ……
Запишите слово, которое стоит на 240-м месте от начала списка.

Для более понятного восприятия задания можно заменить буквы используемого алфавита на цифры: А - 0, О - 1, У - 2. Таким образом, видим, что перед нами записаны числа в троичной системе счисления и все числа идут в порядке возрастания:

1. 00000
2. 00001
3. 00002
4. 00010 ...
На 240-м месте будет находиться троичное число соответствующее десятичному числу 239, т.к. на первом месте находится число 0. Осталось только перевести 239 в троичную систему счисления и записать вместо цифр буквы. 239₁₀ = 22212₃ = УУУОУ

Ответ: УУУОУ

2. Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?

Эта задача является классическим примером двоичного кодирования, где в качестве алфавита используется два знака - точка и тире. Для нахождения количества возможных комбинаций из двух знаков N и длиной двоичного кода i можно воспользоваться формулой N = 2ⁱ. В данной задаче код длиной не менее четырёх и не более пяти сигналов (знаков), т.е. 4 или 5, поэтому ответом будет 2⁴ + 2⁵ =48

Ответ: 48

3. Для передачи аварийных сигналов договорились использовать специальные цветные сигнальные ракеты, запускаемые последовательно. Одна последовательность ракет – один сигнал; в каком порядке идут цвета – существенно. Какое количество различных сигналов можно передать при помощи запуска ровно пяти таких сигнальных ракет, если в запасе имеются ракеты трёх различных цветов (ракет каждого вида неограниченное количество, цвет ракет в последовательности может повторяться)?

В отличие от предыдущей задачи здесь используется не два знака при кодировании, а 3 (три цвета ракет) - троичное кодирование, поэтому количество возможных комбинаций из трех знаков N и длиной кода i находим по формуле N = 3ⁱ. В нашей задаче длина кода - это количество выпущенных ракет, т.е. 5. Таким образом, ответ - 3⁵ = 243

Ответ: 243

4. Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы.

Вот начало списка:
1. КККК
2. КККЛ
3. КККР
4. КККТ
……
Запишите слово, которое стоит под номером 67.

Это задание очень похоже на первое, только здесь используется четверичная система счисления. Опять для удобства заменим буквы на цифры К - 0, Л - 1, Р - 2, Т - 3. Под номером 67 стоит четверичное число соответствующее десятичному числу 66. 66₁₀ = 1002₄ = ЛККР

Ответ: ЛККР

5. Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Такой тип задач относится к комбинаторным. Но попробуем разобраться с помощью простых рассуждений.

Буква К может стоять только в одной из 3-х позиций, это К * *, * К *, * * К (здесь звездочкой обозначена какая-то другая буква). Если К стоит на первом месте, то на втором может стоять любая из оставшихся четырех букв Ш, О, Л или А, т.е. 4 различных варианта. На третьей позиции также может стоять любая из четырех букв Ш, О, Л или А, т.е. еще 4 различных варианта. Получается, что для данной позиции К всего может быть 16 вариантов расстановок других букв (4 * 4 = 16). Рассуждая также для двух других позиций К, мы получим еще 2 раза по 16 вариантов. А всего будет 48 (т.е. 4 * 4 * 3).