теория информации

[gepa]

нужна помощь в решении задач:
1. В урне n шаров, из которых m белых. Последовательно без возвращения извлекаются 2 шара. Пусть А и В - вероятностные схемы с двумя исходами, соответствующие результатам испытаний при первом и втором извлечении шаров.
Найти энтропии Н(А), Н(В), Н(А,В)

2. Существует ли префиксный код со 100 кодовыми словами, у которого длина i-го слова была бы равна i? Будет ли этот код оптимальным?
3. Для матрицы G=$\left( \begin{array}{ccccc} 1 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \end{array} \right)$ построить таблицу стандартного разложения
4. Для двоичного линейного кода G, задаваемого проверочной матрицей Н=$\left( \begin{array}{ccccccccc} 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \end{array} \right)$ найти образующие смежных классов, содержащих слова:
$a_1 = (111101000)$
$a_2 = (110101011)$
$a_3 = (100010001)$
$a_4 = (010010010) $
5.Подсчитать пропускную способность n одинаковых ДСК, соединенных последовательно

заранее спасибо за любую помощь...

[Бодигрим]

gepa в сообщении #218858 писал(а):

1. В урне n шаров, из которых m белых. Последовательно без возвращения извлекаются 2 шара. Пусть А и В - вероятностные схемы с двумя исходами, соответствующие результатам испытаний при первом и втором извлечении шаров.Найти энтропии Н(А), Н(В), Н(А,В)

Постройте указанные в условии вероятностные схемы и найдите вероятности исходов. После чего их останется лишь подставить в формулы для энтропии. Кстати, что вы обозначаете через $H(A,B)$?

[gepa]

Бодигрим в сообщении #218863 писал(а):

gepa в сообщении #218858 писал(а):

1. В урне n шаров, из которых m белых. Последовательно без возвращения извлекаются 2 шара. Пусть А и В - вероятностные схемы с двумя исходами, соответствующие результатам испытаний при первом и втором извлечении шаров.Найти энтропии Н(А), Н(В), Н(А,В)

Постройте указанные в условии вероятностные схемы и найдите вероятности исходов. После чего их останется лишь подставить в формулы для энтропии. Кстати, что вы обозначаете через $H(A,B)$?

энтропия объединенной вероятностной схемы АВ
для нее есть фор-ла $-\sum p(ij)Log(p(ij)) $т.е. сумма по всем ij
только вопрос в том, как будет в данном случае будет выглядеть p(ij)

[Бодигрим]

Цитата:

только вопрос в том, как будет в данном случае будет выглядеть p(ij) :?:

Ну это к вам вопрос, вообще-то. Вы пытаетесь что-то спросить об обозначениях в вами же приведенной формуле - не находите это абсурдом?

Ладно, об объединенной вероятностной схеме и о том, что же обозначено через $p_{ij}$, поговорим позже. Давайте начнем с самого простого. Возьмем схему А. Какова вероятность извлечь из урны в исходном состоянии (т. е. при первом извлечении шаров) белый шар? Не-белый шар?

[gepa]

Бодигрим в сообщении #218869 писал(а):

Цитата:

только вопрос в том, как будет в данном случае будет выглядеть p(ij)

Ну это к вам вопрос, вообще-то. Вы пытаетесь что-то спросить об обозначениях в вами же приведенной формуле - не находите это абсурдом?

Ладно, об объединенной вероятностной схеме и о том, что же обозначено через $p_{ij}$, поговорим позже. Давайте начнем с самого простого. Возьмем схему А. Какова вероятность извлечь из урны в исходном состоянии (т. е. при первом извлечении шаров) белый шар? Не-белый шар?

вероятность извлечь белый шар $\frac m n$, не белый $1-\frac m n$,
в вероятностной схеме В при втором извлечении $\frac {m} {n-1} $...

[Бодигрим]

gepa в сообщении #218875 писал(а):

вероятность извлечь белый шар $\frac m n$, не белый $1-\frac m n$,

Угу. И чему теперь равна энтропия?

gepa в сообщении #218875 писал(а):

в вероятностной схеме В при втором извлечении $\frac {m} {n-1} $...

Почему? Вы полагаете, что белых шаров обязательно останется все $m$ штук?

[gepa]

Н(А)=$-\frac m n * Log \frac m n$
во втрой схеме
тогда если 1-ый шар не белый, и при условии, что у нас остается n-1 шаров, то вероятность вытащить белый шар$\frac m {n-1}$, а если мы уже вытащили белый шар, то $\frac {m-1} {n-1}$

P(B)=$\frac {m(m-1)} {(n-1)^2} $

H(B)=$-\frac {m(m-1)} {(n-1)^2}*Log(\frac {m(m-1)} {(n-1)^2}) $

[Бодигрим]

gepa в сообщении #218882 писал(а):

Н(А)=$-\frac m n * Log \frac m n$

Эм, по какой формуле вы считали? Знак суммы не потеряли?

-- 14:00 01.06.2009 --

gepa в сообщении #218882 писал(а):

во втрой схеме
тогда если 1-ый шар не белый, и при условии, что у нас остается n-1 шаров, то вероятность вытащить белый шар$\frac m {n-1}$, а если мы уже вытащили белый шар, то $\frac {m-1} {n-1}$

Это верно.

gepa в сообщении #218882 писал(а):

P(B)=$\frac {m(m-1)} {(n-1)^2} $

А вот это уже не верно. Гигантов русской демократии спасет формула полной вероятности.

[gepa]

точно, у нас же 2 события, либо белый, либо не белый, тогда получаем Н(А)=$-\frac m n *Log \frac m n - (1 - \frac m n )Log (1-\frac m n)$ можно преобразовать.. $-\frac {n+m*Log(1-\frac m n )+m*Log(\frac m n)} {n}$

[Бодигрим]

Да, теперь правильно. Я бы еще упростил до

$$ \log n-{m\log m + (n-m)\log(n-m)\over n}, $$

но это дело вкуса.

[gepa]

а во втором случае тогда Р(В)=$ \frac m n * \frac {m-1} {n-1} + \frac m n *(1- \frac {m-1} {n-1}) + (1- \frac m n) * \frac m {n-1} +(1- \frac m n) * (1-\frac m {n-1}) $
H(B)=$ -m n * \frac {m-1} {n-1}*Log(m n * \frac {m-1} {n-1}) - \frac m n *(1- \frac {m-1} {n-1})*Log(\frac m n *(1- \frac {m-1} {n-1})) - (1- \frac m n) * \frac m {n-1}*Log((1- \frac m n) * \frac m {n-1}) - (1- \frac m n) * (1-\frac m {n-1}) *Log ((1- \frac m n) * (1-\frac m {n-1}) )$
....... надеюсь это верно
теперь осталось разобраться с p(ij) и остальным задачами...

[Бодигрим]

gepa в сообщении #218906 писал(а):

а во втором случае тогда Р(В)=$ \frac m n * \frac {m-1} {n-1} + \frac m n *(1- \frac {m-1} {n-1}) + (1- \frac m n) * \frac m {n-1} +(1- \frac m n) * (1-\frac m {n-1}) $

Это не так, хотя бы потому что

$$ \frac m n \cdot \frac {m-1} {n-1} + \frac m n \cdot\left(1- \frac {m-1} {n-1}\right) + \left(1- \frac m n\right) \cdot \frac m {n-1} +\left(1- \frac m n\right) \cdot \left(1-\frac m {n-1}\right)=1$$

Здесь у вас суммируются четыре вероятности, отвечающие каждому из четырех возможных исходов: "на первом шаге вытянули белый/не-белый" $\times$ "на втором - белый/не белый". Вам нужно суммировать только те две вероятности, которые вместе составляют событие "на первом шаге - безразлично, что вытянули, на втором шаге вытянули белый".

[gepa]

Бодигрим в сообщении #218909 писал(а):

gepa в сообщении #218906 писал(а):

а во втором случае тогда Р(В)=$ \frac m n * \frac {m-1} {n-1} + \frac m n *(1- \frac {m-1} {n-1}) + (1- \frac m n) * \frac m {n-1} +(1- \frac m n) * (1-\frac m {n-1}) $

Это не так, хотя бы потому что

$$ \frac m n \cdot \frac {m-1} {n-1} + \frac m n \cdot\left(1- \frac {m-1} {n-1}\right) + \left(1- \frac m n\right) \cdot \frac m {n-1} +\left(1- \frac m n\right) \cdot \left(1-\frac m {n-1}\right)=1$$

Здесь у вас суммируются четыре вероятности, отвечающие каждому из четырех возможных исходов: "на первом шаге вытянули белый/не-белый" $\times$ "на втором - белый/не белый". Вам нужно суммировать только те две вероятности, которые вместе составляют событие "на первом шаге - безразлично, что вытянули, на втором шаге вытянули белый".

т.е. $\frac {m-1} {n-1} + \frac {m} {n-1}$ ?
а энтропию мы считаем тогда по этим 2м вероятностям?

[Бодигрим]

Правильная вероятность: $P_1=\frac m n \cdot \frac {m-1} {n-1} + \left(1- \frac m n\right) \cdot \frac m {n-1} $. Т. е. "на первом - белый, на втором - белый" + "на пеовом черный, на втором белый". Ну и вторая вероятность $P_2=1-P_1$. Дальше считаем энтропию по обычной формуле.

[gepa]

Бодигрим в сообщении #218957 писал(а):

Правильная вероятность: $P_1=\frac m n \cdot \frac {m-1} {n-1} + \left(1- \frac m n\right) \cdot \frac m {n-1} $. Т. е. "на первом - белый, на втором - белый" + "на пеовом черный, на втором белый". Ну и вторая вероятность $P_2=1-P_1$. Дальше считаем энтропию по обычной формуле.

понятно, спасибо)