\documentclass[a4paper,12pt]{article}
\usepackage{amsmath,amsthm,russcorr}


\tolerance=1000
\parskip=1ex

\begin{document}
\large

Свойство ``uniquely decodable''
полезно, если мы хотим хранить или
пересылать несколько блоков информации
и хотим писать их кратчайшие коды
без разделителей
(разделитель можно было бы использовать
как обычный символ для кодирования).

Бывают коды ``uniquely decodable'',
но не ``prefix''.
С другой стороны,
по теореме Мак-Миллана--Крафта
``uniquely decodable'' код
заменяется на ``prefix'' код
с теми же длинами.

Преимущество ``prefix'' кодов в том,
что для отделения первого кода
не нужно читать всю последовательность.

\newpage

Для перехода от

$$
(w_1+\cdots+w_k)^n \le
\sum_{l\le nL}\; \sum_{\ell(v)=l} v
$$
к
$$
\left(2^{-\ell(w_1)}+\cdots+2^{-\ell(w_k)}
\right)^n \le
nL\cdot 1
$$
в словах $w_i$, $v$
вместо каждой буквы
подставляется число $1/2$.
(Подстановка чисел вместо букв
эффективно применялась
в исследованиях контекстно-свободных
языков.)

\newpage
\refstepcounter{page}

По каждой паре $n,i$ строится
программа перечисления множества
$S_{n,i}$.
(Слова длины $n$ распределяются в
$S_{n,i}$ в произвольном порядке.)

$\forall^\infty i...$:\\
конечное множество исключительных $i$
обеспечивается за счет $O(1)$.

$x$ принадлежит множеству
$\{z\mid KP(z) < n+i\}$.
Достаточно доказать, что для него
найдется код в $S_{n,i}$.

\newpage

$\alpha(q)$ is enumerable from
below semimeasure:

$$
\sum_q \alpha(q) =
\sum_{z}\sum_{q=KP(z)+1}^\infty 2^{-q}
= \sum_z 2^{-KP(z)}
$$

Как известно,
$2^{-KP(q)}$~---
наибольшая с точностью до
мультипликативной константы
перечислимая снизу полумера.

Hence, $\alpha(q) \le 2^{-KP(q)+O(1)}$\\
Подставим $q=m+1$:
$$
\alpha(m+1)= \sum_{KP(z) < m+1} 2^{-(m+1)}\le
2^{-KP(m+1)+O(1)}
$$
Умножив на $2^{m+1}$, получим\\
$\bigl|\{z\mid KP(z) < m + 1\}\bigr| \le 2^{m-KP(m)+O(1)}$

\bigskip

$2^{KP(i) - 2KP(j) +O(1)}\le 1$,\\
так как
$KP(i)\le KP(j) + KP(KP(j)) + O(1)$

\newpage

Из доказанной теоремы следует, что
$$
KP(x)\ge
KS(x) + KP(KP(x))- O(\log\log\ell(x))
$$

Если $y$ --- (непрефиксный) код $x$,
а $z$ --- префиксный код $y$,
то $zy$ --- префиксный код $x$.\\
Поэтому
$KP(x) \le KS(x) + KP(KS(x)) + O(1)$

\newpage

Функции $KS$ и $KP$ ведут себя сложно.
Они близки друг к другу
с точностью до логарифма,
но с точностью до константы
возрастание одной функции
иногда соответствует убыванию другой
(теорема Мучника).

\end{document}