Курс
http://lpcs.math.msu.su/~ver/teaching/kolm-comp/index.html
Курс по колмогоровской сложности
Дневник лекций в весеннем семестре 2008 года
Программа курса 2008 Postcript.
Программа курса 1999 TeX, DVI, Postcript.
http://lpcs.math.msu.su/~ver/teaching/kolm-comp/2008-log.html
Дневник лекций 2008 года
18-Feb-2008
Определение простой колмогоровской сложности. Неувеличение сложности при алгоритмических преобразованиях. Сложность слова и его длина. Количество слов малой сложности и существование несжимаемых слов.
Невычислимость колмогоровской сложности. Перечислимость сверху колмогоровской сложности. Эквивалентное определение колмогоровской сложности как наименьшей перечислимой сверху функции с условием нормировки.
24-Feb-2008
Колмогоровская сложность произвольных конструктивных объектов. Сложность пары объектов не превосходит суммы их сложностей.
Простейшие применения колмогоровской сложности: доказательство бесконечности множества простых чисел и квадратичная нижняя оценка для числа шагов одноленточной машины Тьюринга, распознающей палиндромы.
Условная колмогоровская сложность и ее свойства. Сложность пары слов равна сложности первого слова плюс условная сложность второго слова при известном первом слове (теорема Колмогорова--Левина).
3-Mar-2008
Релятивизация. Основное неравенство. Неравенство 2 KS(x,y,z) < KS(x,y)+KS(x,z)+KS(y,z) и его комбинаторная интерпретация. Комбинаторная интерпретация других неравенств.
Определение количества информации в одном объекте о другом. Его простейшие свойства. Коммутативность информации. Пример двух слов с невыделяемой общей информацией (без доказательства). Определение количества общей информации трех слов и пример трех слов, для которых эта величина отрицательна.
10-Mar-2008
Случайные слова (по данному распределению вероятности). Дефект случайности. Его свойства.
17-Mar-2008
Меры на пространстве бесконечных последовательностей нулей и единиц. Множества меры нуль. Конструктивно нулевые множества. Закон больших чисел. Случайные по Мартин-Лёфу последовательности.
24-Mar-2008
Вычислимые действительные числа. Вычислимые функции (отображающие слова в дейтсвительные числа). Вычислимые меры на пространстве бесконечных последовательностей нулей и единиц. Теорема Мартин-Лёфа о существовании наибольшего конструктивного множества.
31-Mar-2008
Префиксно корректные и беспрефиксные функции. Теорема о существовании оптимальной декодирущей функции в классе префиксно корректных и классе беспрефиксных функций. Префиксная сложность (два вида).
Свойства префиксной сложности. Условная префиксная сложность и префиксная сложность пары строк.
7-Apr-2008
Перечислимые снизу меры на натуральных числах. Эквивалентное определение с помощью вероятностных машин. Априорная вероятность.
Основная теорема о префиксной сложности.
14-Apr-2008
Условная префиксная сложность. Перечислимые снизу семейства мер на натуральных числах и условная априорная вероятность.
Теорема Левина-Шнорра о префиксной сложности начальных фрагментов случайной по Мартин-Лёфу последовательности.
Теорема о префиксной сложности пары (она равна сумме префиксной сложности первой компоненты и условной сложности второй компоненты при известной первой компоненте и ее префиксной сложности).
21-Apr-2008
Вероятностные машины и перечислимые снизу меры на дереве. Априорная мера на дереве. Априорная сложность.
Свойства априорной сложности. Определение априорной сложности как наименьшей перечислимой функции в некотором классе функций.
28-Apr-2008
Критерий случайности по Мартин-Лёфу в терминах априорной сложности начальных отрезков последовательности.
Непрерывные вычислимые операторы на пространстве конечных и бесконечных последовательностей. Монотонная сложность.
5-May-2008
Свойства монотонной сложности (перечислимость сверху, монотонность) Сравнение монотонной сложности с префиксной, априорной и обычной сложностями. Сравнение префиксной сложности с минус логарифмом вычислимой вероятностной меры на дереве. Критерий Левина--Шнорра случайности по вычислимой мере в терминах монотонной сложности.
Сложность разрешения и ее свойства. Комбинаторное определение сложности разрешения. Соотношение с другими сложностями.
12-May-2008
Частотный подход к определению случайных последовательностей. Правила выбора и случайные по Мизесу-Черчу последовательности. Соотношение случайности по Мизесу-Черчу и случайности по Мартин-Лефу.
\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}