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