Кафедра математической логики и теории алгоритмов

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

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