Список заданий по ДМ-сем2

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 2 семестр

1. Докажите, что для монеты энтропия максимальна в случае честной монеты
2. Докажите, что для n исходов энтропия максимальна если они все равновероятны
3. Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $H(x) + C$ где $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, а $C$ - константа, не зависящая от слова $x$ (но зависящая от выбранного языка программирования)
4. Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c H(x)$
5. Пусть заданы полные системы событий $A = \{a_1, ..., a_n\}$ и $B = \{b_1, ..., b_m\}$. Определим условную энтропию $H(A | B)$ как $-\sum\limits_{i = 1}^m P(b_i) \sum\limits_{j = 1}^n P(a_j | b_i) \log P(a_j | b_i))$. Докажите, что $H(A | B) + H(B) = H(B | A) + H(A)$
6. Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
7. Что можно сказать про $H(A | A)$?

</wikitex>