\documentstyle[12pt,russcorr]{article}
\textwidth 15cm
\oddsidemargin 0cm

\newcommand{\forces}{|\hskip-.4em\vdash}

\newcounter{вопрос}
\newcommand{\вопрос}{\refstepcounter{вопрос}%
\noindent\theвопрос. }

\newcounter{задача}
\newcommand{\задача}{\refstepcounter{задача}%
\noindent\theзадача. }

\begin{document}
{\large Программа экзамена по спецкурсу \лк Колмогоровская сложность\пк}

\bigskip
\bigskip

\вопрос  Теорема Соломонова---Колмогорова об оптимальном способе описания.

\вопрос  Основные свойства колмогоровской энтропии

\вопрос  Алгоритмические свойства колмогоровской энтропии

\вопрос  Теорема о полноте по Тьюрингу надграфика колмогоровской
энтропии в классе перечислимых множеств

\вопрос  Программно-независимое определение колмогоровской энтропии

\вопрос  Теорема Соломонова --- Колмогорова об оптимальном условном
способе описания.

\вопрос  Основные свойства условной энтропии

\вопрос  Количество слов длины $n$ и энтропии не менее $n$

\вопрос Теорема о выражении сложности пары слов через сложности ее
компонентов

\вопрос  Теорема Соломонова --- Колмогорова об оптимальном префиксном
способе описания.

\вопрос Префиксная энтропия слова и его длина

\вопрос  Вычислимость префиксных функций на машинах с блокирующим входом

\вопрос  Перечислимые  снизу полумеры на $\{0,1\}^*$,
эквивалентность двух определений.

\вопрос  Существование универсальной перечислимой снизу полумеры
$\{0,1\}^*$.

\вопрос  Теорема о связи
универсальной перечислимой снизу полумеры и префиксной энтропии

\вопрос   Теорема о выражении префиксной энтропии пары слов через
префиксную энтропию ее компонентов

\вопрос  Невозможность определения понятия случайной бесконечной
последовательности с помощью обычной колмогоровской энтропии

\вопрос Теорема существования максимального конструктивно нулевого множества

\вопрос Доказательство усиленного закона больших чисел

\вопрос Свойства случайных по Мартин-Лёфу последовательностей

\вопрос Префиксная энтропия начальных фрагментов
случайных по Мартин-Лёфу последовательностей.

\вопрос Энтропия разрешения, монотонная энтропия.

\вопрос Перечислимые снизу полумеры на $\Omega$ и априорная энтропия.

\вопрос Соотношение между пятью видами энтропии.

\вопрос
Характеризация случайных по Мартин-Лёфу последовательностей
в терминах априорной и монотонной энтропий.

\вопрос Случайность по
Мартин-Лёфу по произвольной вычислимой мере и её         характеризация
в сложностных терминах.

\вопрос Неравенство $KM(x)\le-\log_2\mu(x)+O(1)$ (где
$\mu$ --- вычислимая мера на $\Omega$).

\вопрос Верхняя оценка на величину $n$-ого простого числа
(с использованием колмогоровской сложности).

\вопрос Сравнение $k$- и $k+1$-головочных конечных автоматов
(с использованием колмогоровской сложности).

\вопрос Нижняя оценка $cn^2$ времени распознавания симметрии на
одноленточных машинах Тьюринга
(с использованием колмогоровской сложности).

\вопрос Верхняя оценка объёма трёхмерного тела
(с использованием колмогоровской сложности).

\вопрос Доказательство усиленного закона больших чисел
(с использованием колмогоровской сложности).

\вопрос Доказательство верхней оценки в законе повторного логарифма
(с использованием колмогоровской сложности).

\вопрос Энтропия Шеннона и её свойства.

\вопрос Связь шенноновской и колмогоровской энтропий.

\вопрос Теория предсказаний по Соломонову.

\вопрос Стохастические по Чёрчу и по Колмогорову --- Лавлэнду
последовательности, включения: (стохастические по Чёрчу)
$\supseteq$ (стохастические по Колмогорову --- Лавлэнду) $\supseteq$
(случайные по Мартин-Лёфу).

\вопрос Пример Вилля: стохастическая по Чёрчу последовательность,
не случайная по Мартин-Лёфу.

\вопрос Теорема Ан. Мучника о нестохастичности по Колмогорову ---
Лавлэнду последовательностей с малой сложностью.

\вопрос Пример ван Ламбальгена:
стохастическая по Колмогорову --- Лавлэнду, но не случайная по
Мартин-Лёфу последовательность.




\bigskip
\bigskip
Задачи

\вопрос  Доказать, что $m+K(m)< n+K(n)+O(1)$ при всех натуральных $m<n$

\вопрос Доказать, что $2K(a,b,c)<K(a,b)+K(a,c)+K(b,c)+O(\log K(a,b,c))$.

\вопрос Доказать, что если множество $\{n\mid \omega_n=1\}$ перечислимо,
то $K(\omega_{1..n})<2\log n+O(1)$, $K(\omega_{1..n}|n)<\log n+O(1)$.

\вопрос  Доказать, что если $K(xy)=2n+O(1)$ и $|x|=|y|=n$,
то $K(x)=n+O(1)$ и $K(y)=n+O(1)$

\вопрос Доказать, что среднее значение $K(i)$ при $i=1,\dots,n$ равно
$\log n+O(1)$

\вопрос Доказать, что если $K(\omega_{1..n}|n)=O(1)$, то
последовательность $\omega$ вычислима.

\вопрос  Доказать, что среди вычислимых распределений вероятностей
на $\{0,1\}^*$ нет максимального.

\вопрос  Доказать, что для почти всех последовательностей
найдётся $c$, для которого $K(\omega_{1..n})>n-c$ для
бесконечно многих $n$.

\вопрос Пусть последовательность $\omega_1,\omega_2,\omega_3,\omega_4\dots$
случайна по Мартин-Лёфу.
Показать, что тогда последовательность
$\omega_1\oplus\omega_2,\omega_3\oplus\omega_4\dots$
также случайна по Мартин-Лёфу.

\вопрос Доказать, что если $x$ двоичное слово длины $n$ и
энтропии не менее $n-m$, то количество 1 в $x$
отличается от $n/2$ на величину не менее $n^{1/4}2^{-m/2+O(1)}$.

\вопрос Доказать, что если $x$ случайное слово (то есть
энтропия $x$ близка к его длине), то и любое подслово
$x$ случайно (указать подходящие оценки).






\end{document}