1.3 Примеры решения задач по теме «Математическая теория информации»

Задача 1

В велокроссе участвуют `130` спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объём сообщения, записанного устройством, после того как промежуточный финиш прошли `75` велосипедистов?

Решение

Первым делом нужно определить, сколько бит необходимо для кодирования `130` номеров спортсменов. Поскольку номера записываются в некотором устройстве, количество бит для кодирования каждого номера обязательно должно быть целым: `H=log_2  130`.  После округления результата в большую сторону получим число `8`. Следовательно, для кодирования `1` номера необходим `1` байт. Таким образом, информационный объём сообщения, записанного устройством, составляет `75` байт.


Задача 2

В некоторой стране автомобильный номер состоит из `7` символов. В качестве символов используют `18` различных букв и десятичные цифры в любом порядке.

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

Определите объём памяти, отводимый этой программой для записи `60` номеров.

Решение

Первое действие аналогично предыдущей задаче – нужно установить, каким количеством бит кодируется `1` символ. Всего используется `18` букв и `10` десятичных цифр, то есть `28` символов. По формуле  Хартли `H=log_2  28`.  После  округления  получается `5` бит на `1` символ. Вторым действием нужно узнать, какой объём памяти занимает `1` номер. Поскольку номер состоит из `7` символов, а каждый символ кодируется `5` битами, нам потребуется `35` бит памяти для хранения `1` номера. Однако по условию каждый номер должен записываться целым количеством байтов, а в каждом байте `8` бит. Ближайшее сверху к `35` число, делящееся на `8` – это число `40`, следовательно, на каждый номер отводится `5` байт. Таким образом, для записи `60` номеров программе потребуется `60*5 = 300` байт памяти.

Задача 3

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

Решение

Главная ловушка этой задачи заключается в следующем неверном ходе мыслей: «Раз одной рукой передаётся `3` сигнала, значит, двумя в `2` раза больше, то есть `6`». На самом деле число исходов с добавлением новой руки увеличивается в `3` раза, поскольку можно продублировать все положения первой руки для каждого из `3` возможных положений второй. Таким образом, в ответе получается `9` сигналов.

Задача 4

В течение `5` секунд было передано сообщение, объём ко-торого составил `375` байт. Каков размер алфавита, с помощью кото-рого записано сообщение, если скорость его передачи составила `200` символов в секунду?

Решение

Первым делом найдём скорость передачи этого сообщения: `375//5 = 75` байт в секунду. Далее, нам известно, что в секунду передавалось `200` символов, которые занимают `75` байт памяти. Поэтому следующим действием найдём объём памяти, отводимый под `1` символ, переведя ответ в биты (ибо уже из входных чисел очевидно, что под каждый символ отводится менее `1` байта): `75^(**)8//200 = 600//200 = 3`. Таким образом, под каждый символ отводится `3` бита.

Применяя формулу Хартли, находим, что алфавит состоит из `8` символов.