Дневник лекций 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

Частотный подход к определению случайных последовательностей. Правила выбора и случайные по Мизесу-Черчу последовательности. Соотношение случайности по Мизесу-Черчу и случайности по Мартин-Лефу.