Задание №8 на ЕГЭ по информатике. Измерение количества информации. Основы комбинаторики.

Автор материалов - Лада Борисовна Есакова.

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

Чтобы найти информационный объем сообщения I, нужно количество символов этого сообщения N умножить на количество бит, выделяемых для кодирования одного символа

K : I = N * K.

Количество символов в некотором алфавите называется мощностью алфавита.

Несложно понять, что количество слов длиной N, составленных из символов (букв) алфавита мощностью M равно M^N.

При компьютерном кодировании мощность алфавита равна 2, значит количество слов длиной N равно 2^N.

Подсчет количества буквенных цепочек

Пример 1.

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Запишите слово, которое стоит на 210-м месте от начала списка.

Решение:

Заменим буквы А, О, У на 0, 1, 2 и выпишем начало списка:

1. 00000

2. 00001

3. 00002

4. 00010

...

Полученная запись есть числа, записанные в троичной системе счисления в порядке возрастания. Тогда на 210 месте будет стоять число 209 (т. к. первое число 0). Переведём число 209 в троичную систему: 209₁₀ = 21202₃

Заменим обратно цифры на буквы и получим УОУАУ.

Ответ: УОУАУ

Пример 2.

Сколько слов длины 6, начинающихся с согласной буквы, можно составить из букв Г, О, Д? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Решение:

На первом месте может стоять две буквы: Г или Д, на остальных — три буквы.

Слов, начинающихся на Г, 3⁵. Слов, начинающихся на Д, тоже 3⁵.Таким образом, можно составить 2 · 3⁵ = 486 слов.

Ответ: 486

Пример 3.

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

Решение:

Пусть С стоит в слове на первом месте. Тогда на каждое из оставшихся 4 мест можно поставить независимо одну из 3 букв. То есть всего 3*3*3*3 = 81 вариант. Таким образом, С можно по очереди поставить на все 5 мест, в каждом случае получая 81 вариант. Итого получается 81 * 5 = 405 слов.

Ответ: 405

Количество информации при двоичном (компьютерном) кодировании

Пример 4.

Объем сообщения – 7,5 Кбайт. Известно, что данное сообщение содержит 7680 символов. Какова мощность алфавита?

Решение:

Объем сообщения I, написанного в исходном алфавите мощности M, содержащего N символов, равен: I = log₂M * N

I = 7680 * log₂M

Log₂M = (7,5 * 2¹³ бит) / 7680 =(7,5 * 2¹³⁾ /(15 * 2⁹) = 8

M = 2⁸ = 256

Ответ: 256

Количество информации при различных (не компьютерных) способах кодирования

Пример 5.

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

Решение:

Мы имеем алфавит из двух букв: точка и тире. Из двух букв можно составить 2⁴ четырёхбуквенных слова и 2⁵ пятибуквенных слов.

Значит, всего можно закодировать 16 + 32 = 48 различных символов.

Ответ: 48