Список заданий по ДМ-сем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 : 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)$
+
# Пусть заданы полные системы событий $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 семестр

  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>