Задачи по курсу «Информационные системы»

Задачи по курсу «Информационные системы»

1. Статистически независимые ансамбли.

Пусть X и Y состоят из двух элементов каждый: X={x , x },Y={y , y }. На декартовом произведении XY задано распределение p, про которое известно, что p(x ,y )= , p(x ,y )= , p(x ,y )= . Являются ли ансамбли {X, p } и {Y, p } статистически независимыми?

1. Математическое ожидание случайной величины.

Пусть задано XY и p – некоторое распределение на XY. Пусть - случайная величина, заданная на X. Пусть Y = {y ,…,y } и p – распределение на Y. Тогда для любого y из Y такого, что p (y) 0, существует M( |y) – условное математическое ожидание величины при условии y. Положим M( |y )= m для i (1:n). Найти M =?.

1. Моменты случайных величин.

Пусть = M() - k-тый момент случайной величины , пусть M =0. Доказать, что для всякого четного k > 0, , имеет место неравенство:

P (| | ) .

1. Энтропия счетного множества сообщений.

Пусть X={x , x , …}- множество, состоящее из счетного числа элементов. Приведите пример распределения вероятностей на X такого, чтобы энтропия ансамбля {X,p}

H(X) = - была ограниченной.

1. Условная энтропия ансамбля.

Пусть заданы два ансамбля X и Y. Пусть ансамбль Y однозначно определяет ансамбль X, т.е. при каждом фиксированном y Y существует x X, что p(x|y)=1.

Найти: H(X|Y) =?.

1. Энтропия конечных множеств сообще ний.

Пусть X={x ,x ,x ,x ,x ,x }, p(x )=p(x )=p(x )= , p(x )=p(x )=p(x )= ,

Y={y ,y ,y }, p(y )=p(y )=p(y )= , показать, что H(X)>H(Y).

1. Марковский источник сообщений.

Пусть дискретный источник порождает случайный процесс, для которого p(x |x ,x ,…,x )=p(x |x …x ), где s<n. Такой источник называется Марковским источником порядка s. Показать, что H(X|X )=H(X|X ) для всех n s, где H(X|X )=H(X |X ,…,X ).

1. Стационарный Марковский источник сообщений.

Покажите, что энтропия на сообщение стационарного Марковского источника порядка s равна H(X|X ).

1. Пределы условных и средних энтропий.

Из теорем о пределе условных энтропий и средних энтропий известно, что

H (X|X ) = H (X|X ) и H(X )/k =H (X|X ). Определить для k 1 какая из двух величин больше H(X|X ) или .

1. Ошибка кодирования равномерным кодом.

Пусть R<H(X). Показать, что <n, что p 1- для любого равномерного кода, кодирующего дискретный источник без памяти со скоростью R.

1. Оптимальное кодирование.

Пусть дан ансамбль X={x ,x ,x ,x }, p(x )= ,p(x )= ,p(x )= ,p(x )= . Задан неравномерный код k(x )=10, k(x )=01, k(x )=000, k(x )=111. Докажите, что он неоптимальный.

1. Дискретный источник без памяти.

Пусть задан дискретный источник без памяти U . Энтропия ансамбля X равна 2.5 бит. Пусть 1000 сообщений этого источника кодируются десятичным равномерным кодом. Каково наименьшее количество кодовых символов, которые могут появиться на выходе кодера?

1. Эргодический дискретный источник.

Пусть задан эргодический дискретный источник, выбирающий сообщения из множества X={x ,x }. Требуется оценить вероятность появления сообщения x в последовательности длины m, если p(x )=p, и p(x )=1-p.

1. Кодирование по методу Хаффмана.

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

1. Ансамбль десятичных цифр.

Пусть Х – ансамбль равновероятных десятичных цифр от 0 до 9. H(X) 3.32. Найти длину равномерного двоичного кода, однозначно кодирующего этот ансамбль.

1. Кодирование десятичного ансамбля.

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

1. Кодирование десятичных блоков.

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

1. Кодирование блоков десятичных цифр.

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

1. Кодирование длин серий.

Пусть ансамбль X={x ,…,x , x } определяется следующим образом. Событию x , где 1 i N соответствует появление во входном потоке двоичных данных последовательности 000…001, состоящей из i-1 нуля и единицы. Событию x

соответствует появление во входном потоке N нулей. В этом случае, предполагается, что вероятность появления 1 во входном потоке равна p . Пусть q = 1-p. Если считать источник сообщений дискретным источником без памяти, то вероятности появления сообщений ансамбля X следующие: p(x )=p.q для i N, p(x )=q . Эти сообщения можно закодировать в алфавите {0,1} таким образом, что k(x ) = 0, а все другие сообщения кодируются словами длины к+1, начинающимися с 1. При этом N 2 . Доказать, что такое кодирование однозначно.

1. Математическое ожидание длины сегмента при кодировании длин серий.

Пусть задано кодирование длин серий предыдущего задания. Найти математическое ожидание длины сегмента при кодировании этих длин серий. (Ответ: m= +Nq =(1-q )/p).

1. Среднее количество кодовых символов сегмента при кодировании длинами серий.

Пусть задано кодирование длин серий предыдущего задания. Найти среднюю длину кодовых слов, кодирующих сегменты. (Ответ: m=k (1-q ) +1).

1. Среднее количество кодовых символов на сообщение при кодировании длинами серий.

Пусть задано кодирование длин серий предыдущего задания. Найти среднее количество кодовых символов на сообщение при кодировании этими длинами серий. (Ответ: r=kp+ ).

1. Кодирование длинами серий и кодирование методом Хаффмана.

Пусть задано кодирование длин серий предыдущего задания. Пусть p=0.1, N=8, k=3.Показать, что скорость кодирования при кодировании длин серий более чем на 1% меньше, чем при кодировании методом Хаффмана блоков длины 4.

Дата добавления: 2015-09-29