Дневник лекций 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
Частотный подход к определению случайных последовательностей.
Правила выбора и случайные по Мизесу-Черчу последовательности.
Соотношение случайности по Мизесу-Черчу и случайности
по Мартин-Лефу.