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

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

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

Чтобы найти информационный объем сообщения 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

Пример 6.

Све­то­вое табло со­сто­ит из лам­по­чек. Каж­дая лам­поч­ка может на­хо­дить­ся в одном из трех со­сто­я­ний («вклю­че­но», «вы­клю­че­но» или «ми­га­ет»). Какое наи­мень­шее ко­ли­че­ство лам­по­чек долж­но на­хо­дить­ся на табло, чтобы с его по­мо­щью можно было пе­ре­дать 18 раз­лич­ных сиг­на­лов?

Решение:

Мощность алфавита M =3 («вклю­че­но», «вы­клю­че­но» или «ми­га­ет»).

Количество различных сигналов 18 <= M^N= 3^N. (Поскольку равенство не выполняется, N берем с избытком, иначе не сможем закодировать все сигналы). N = 3.

Ответ: 3