Дневник лекций 2011 года
12-Sep-2011
Определение простой колмогоровской сложности.
Сложность слова и его длина. Количество слов малой сложности и существование несжимаемых слов.
Невычислимость колмогоровской сложности. Ограниченность вычислимых нижних оценок колмогоровской сложности.
Перечислимость сверху колмогоровской сложности.
19-Sep-2011
Эквивалентное определение колмогоровской сложности как наименьшей перечислимой сверху функции с условием нормировки.
Неувеличение сложности при алгоритмических преобразованиях.
Колмогоровская сложность других объектов. Колмогоровская сложность пары слов (верхняя оценка). Невозможность сделать постоянным добавочный член в этом неравенстве.
Условная сложность (определение).
26-Sep-2011
Изменение условной сложности при алгоритмических преобразованиях.
Количество слов малой сложности.
Теорема Колмогорова — Левина о сложности пары слов.
Понятие информации, ее свойства и коммутативность. Невозрастание информации при алгоритмических преобразованиях.
Невозрастание информации при вероятностных преобразованиях.
3-Oct-2011
Релятивизация и новые информационные неравенства и равенства.
Базисное неравенство. Шенноновские неравенства.
Общая информация тройки слов и пример, когда она отрицательна.
Применение диаграмм для получения новых шенноновских неравенств.
Теорема Шеннона о совершенном шифре, монотонность информации, неравенство для сложности тройки. Комбинаторный аналог последнего неравенства и его вывод из колмогоровского неравенства.
10-Oct-2011
Применения колмогоровской сложности: бесконечность множества простых чисел, квадратичная нижняя оценка для времени копирования и распознавания симметрии на одноленточных машинах Тьюринга и теорема Ибарры-Кима о k-головочных конечных автоматах.
17-Oct-2011
Меры на пространстве бесконечных 0-1-последовательностей.
Равномерная мера (мера Лебега), бернулливевы меры.
Доказательство усиленного закона больших чисел для бернуллиевых мер.
24-Oct-2011
Определение конструктивно нулевого множества относительно данной меры. Определение случайной по Мартин-Лёфу последовательности.
Формулировка теоремы Мартин-Лёфа о максимальном к-н множестве.
31-Oct-2011
Доказательство теоремы Мартин-Лёфа о максимальном к-н множестве.
Критерий Соловея случайности последовательности.
Случайные последовательности относительно равномерной меры: неслучайность вычислимых последовательностей, устойчивость относительно конечных изменений и взятия вычислимой подпоследовательности.
Неслучайность всех перечислимых и ко-перечислимых множеств.
Существование вычислимой относительно 0′ случайной последовательности.
7-Nov-2011
Перечислимые снизу меры на натуральных числах: два определения и их эквивалентность.
Префиксные и префиксно корректные функции. Формулировка основной теоремы о префиксной сложности.
14-Nov-2011
Существование оптимальных функций в классе префиксно корректных и беспрефиксных функций. Машины с самоограниченным входом.
Свойства префиксных сложностей.
Доказательство основной теоремы о префиксной сложности.
Верхняя оценка префиксной сложности пары.
21-Nov-2011
Условная префиксная сложность, условная априорная вероятность и связь между ними.
Формула, выражающая префиксную сложность пары через префиксные сложности ее компонентов.
Простая сложность строки при известной ее простой сложности.
Выражение простой сложности через префиксную сложность.
Формула Баувенса для простой сложности пары.
28-Nov-2011
Перечислимые снизу тесты случайности. Универсальный (наибольший)
тест.
Выражение универсального теста через префиксную сложность (теорема Гача-Левина), как суммы и как максимума.
Следствие — последовательность x_1x_2… случайна по Мартин-Лёфу относительно равномерной меры тогда и только тогда, когда n-KP(x_1…x_n) ограничено сверху.
5-Dec-2011
Перечислимые снизу меры на дереве. Эквивалентное определение с помощью вероятностных машин.
12-Dec-2011
Сравнение префиксной сложности слова с суммой длины и ее (длины) префиксной сложности.
Наибольшие перечислимые снизу меры на дереве. Априорная сложность и ее свойства. Характеризация вычислимых последовательностей в терминах априорной сложности начальных фрагментов.
Монотонная сложность и ее свойства.