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



             

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


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

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

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

t_1
, второго типа -
t_2,\ldots,k
-го типа -
t_k
единиц времени.

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

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

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

T
через
f(T)
. Рассуждая точно так же, как и в задаче о марках, получаем, что
f(T)
удовлетворяет соотношению
f(T)=f(T-t_1)+\ldots+f(T-t_k).

(5.8)

При этом снова
f(T) = 0
, если
T < 0
и
f(0) = 1$.




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