Изменения
Нет описания правки
# Колмогоровская сложность конкатенации. Докажите, что $K(xy) \le K(x) + K(y) + O(1)$.
# Колмогоровская сложность пары. Докажите, что $K(\langle x, y\rangle) \le K(x) + K(y) + O(\log |x|)$.
# Колмогоровская сложность и энтропия Шеннона. Для слова $x$, в котором $i$-й символ алфавита встречается $f_i$ раз обозначим как $H(x)$ величину, равную энтропии случайного источника с распределением $p_i = f_i/|x|$. Докажите, что $K(x) \le nH(x) + O(1\log n)$.
# Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
# Петя хочет пойти в кино с вероятностью ровно 1/13, а у него есть только честная монета. Может ли он осуществить свой замысел?
