Список заданий по ДМ-сем2 — различия между версиями
| Строка 6: | Строка 6: | ||
# Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $H(x) + C$ где $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, а $C$ - константа, не зависящая от слова $x$ (но зависящая от выбранного языка программирования) | # Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $H(x) + C$ где $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, а $C$ - константа, не зависящая от слова $x$ (но зависящая от выбранного языка программирования) | ||
# Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c H(x)$ | # Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c H(x)$ | ||
| − | # Пусть заданы полные системы событий $A = \{a_1, ..., a_n\}$ и $B = \{b_1, ..., b_m\}$. Определим условную энтропию $H(A | B)$ как $-\sum\limits_{i = 1}^m | + | # Пусть заданы полные системы событий $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)$ |
# Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$? | # Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$? | ||
# Что можно сказать про $H(A | A)$? | # Что можно сказать про $H(A | A)$? | ||
</wikitex> | </wikitex> | ||
Версия 16:23, 13 февраля 2014
<wikitex>
Дискретная математика, алгоритмы и структуры данных, 2 семестр
- Докажите, что для монеты энтропия максимальна в случае честной монеты
- Докажите, что для n исходов энтропия максимальна если они все равновероятны
- Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $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)$ как $-\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)$
- Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
- Что можно сказать про $H(A | A)$?
</wikitex>
