Дневник лекций 2014 года

8-Sep-2014

Определение простой колмогоровской сложности. Невозрастание сложности при алгоритмических преобразованиях.
Сложность слова и его длина. Количество слов малой сложности и существование несжимаемых слов.

Невычислимость колмогоровской сложности. Ограниченность вычислимых нижних оценок колмогоровской сложности.
Перечислимость сверху колмогоровской сложности.

15-Sep-2014

Сложность других конструктивных объектов. Неравенство для сложности пары слов.

Условная сложность. Неравенство для сложности пары слов для условной сложности.

29-Sep-2014

Теорема Колмогорова — Левина.
Невозможность избавиться от логарифмической добавки в этой теореме.

Релятивизация и новые неравенства. Базисное неравенство.
Неравенство Лумиса-Уитни и его доказательство с помощью колмогоровской сложности.

6-Oct-2014

Информация в x об y.
Графическое изображение информации.
Графическое изображение сложностного профиля тройки слов. Общая информация тройки слов.

Меры на пространстве бесконечных последовательностей из нулей и единиц.

13-Oct-2014

Доказательство закона больших чисел для равномерной и произвольной бернулиевских мер.

Определение конструктивно нулевых множеств и случайности по Мартин-Лёфу. Неслучайность вычислимых последовательностей по равномерной мере.

20-Oct-2014

Вычислимые меры.
Наибольшее конструктивно нулевое множество для данной вычислимой меры.

Устойчивость случайности относительно конечных изменений (для равномерной
меры).

Префиксная сложность. Определение и два ее вида.

27-Oct-2014

Вычислимая относительно 0′ последовательность, не случайная по равномерной мере.

Случайность по Соловею.

Перечислимые снизу полумеры на словах. Эквивалентное определение с помощью вероятностных машин.

10-Nov-2014

Основная теорема о префиксной сложности. Свойства префиксной сложности (перечислимость сверху, сложность и длина, неувеличение при алгоритмических преобразованиях). Неравенство для префиксной сложности пары.

17-Nov-2014

Условная префиксная сложность с беспрефиксными и префиксно корректными функциями. Условные полумеры. Основная теорема об условной префиксной сложности (всё без доказательства).

Теорема Колмогорова — Левина о сложности пары для префиксной сложности.

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

24-Nov-2014

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

Применения колмогоровской сложности: бесконечность множества простых чисел, квадратичная нижняя оценка для задачи копирования, различение k и k+1 головочных конечных автоматов (не успели довести доказательство до конца).

1-Dec-2014

Доказательство теоремы об автоматах до конца.

Априорная вероятность на дереве, априорная сложность и ее свойства.

8-Dec-2014

Монотонная сложность и ее свойства.

Теорема Левина — Шнорра.