Комбинаторные алгоритмы для программистов

          

Комбинаторные задачи теории информации


Информация - сведения, неизвестные до их получения, или данные, или значения, приписанные данным.

Теория информации - математическая дисциплина, изучающая количественные свойства информации.

Задачу, похожую на только что решенную, приходится решать в теории информации. Предположим, что сообщение передается с помощью сигналов нескольких типов. Длительность передачи сигнала первого типа равна

Комбинаторные задачи теории информации
, второго типа -
Комбинаторные задачи теории информации
-го типа -
Комбинаторные задачи теории информации
единиц времени.

Задача 6. Сколько различных сообщений можно передать с помощью этих сигналов за

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

Обозначим число сообщений, которые можно передать за время

Комбинаторные задачи теории информации
через
Комбинаторные задачи теории информации
. Рассуждая точно так же, как и в задаче о марках, получаем, что
Комбинаторные задачи теории информации
удовлетворяет соотношению
Комбинаторные задачи теории информации

(5.8)

При этом снова
Комбинаторные задачи теории информации
, если
Комбинаторные задачи теории информации
и
Комбинаторные задачи теории информации
Комбинаторные задачи теории информации


Содержание раздела