Определение простой колмогоровской сложности. Сложность слова и его длина. Количество слов малой сложности и существование несжимаемых слов.
Невычислимость колмогоровской сложности. Ограниченность вычислимых нижних оценок колмогоровской сложности. Перечислимость сверху колмогоровской сложности.
Эквивалентное определение колмогоровской сложности как наименьшей перечислимой сверху функции с условием нормировки. Неувеличение сложности при алгоритмических преобразованиях.
Колмогоровская сложность других объектов. Колмогоровская сложность пары слов (верхняя оценка). Невозможность сделать постоянным добавочный член в этом неравенстве.
Условная сложность (определение).
Изменение условной сложности при алгоритмических преобразованиях. Количество слов малой сложности.
Теорема Колмогорова - Левина о сложности пары слов.
Понятие информации, ее свойства и коммутативность. Невозрастание информации при алгоритмических преобразованиях. Невозрастание информации при вероятностных преобразованиях.
Релятивизация и новые информационные неравенства и равенства. Базисное неравенство. Шенноновские неравенства.
Общая информация тройки слов и пример, когда она отрицательна. Применение диаграмм для получения новых шенноновских неравенств.
Теорема Шеннона о совершенном шифре, монотонность информации, неравенство для сложности тройки. Комбинаторный аналог последнего неравенства и его вывод из колмогоровского неравенства.
Применения колмогоровской сложности: бесконечность множества простых чисел, квадратичная нижняя оценка для времени копирования и распознавания симметрии на одноленточных машинах Тьюринга и теорема Ибарры-Кима о k-головочных конечных автоматах.
Меры на пространстве бесконечных 0-1-последовательностей. Равномерная мера (мера Лебега), бернулливевы меры. Доказательство усиленного закона больших чисел для бернуллиевых мер.
Определение конструктивно нулевого множества относительно данной меры. Определение случайной по Мартин-Лёфу последовательности. Формулировка теоремы Мартин-Лёфа о максимальном к-н множестве.
Доказательство теоремы Мартин-Лёфа о максимальном к-н множестве. Критерий Соловея случайности последовательности.
Случайные последовательности относительно равномерной меры: неслучайность вычислимых последовательностей, устойчивость относительно конечных изменений и взятия вычислимой подпоследовательности. Неслучайность всех перечислимых и ко-перечислимых множеств. Существование вычислимой относительно 0' случайной последовательности.
Перечислимые снизу меры на натуральных числах: два определения и их эквивалентность.
Префиксные и префиксно корректные функции. Формулировка основной теоремы о префиксной сложности.
Существование оптимальных функций в классе префиксно корректных и беспрефиксных функций. Машины с самоограниченным входом.
Свойства префиксных сложностей. Доказательство основной теоремы о префиксной сложности. Верхняя оценка префиксной сложности пары.
Условная префиксная сложность, условная априорная вероятность и связь между ними. Формула, выражающая префиксную сложность пары через префиксные сложности ее компонентов.
Простая сложность строки при известной ее простой сложности. Выражение простой сложности через префиксную сложность. Формула Баувенса для простой сложности пары.
Перечислимые снизу тесты случайности. Универсальный (наибольший) тест.
Выражение универсального теста через префиксную сложность (теорема Гача-Левина), как суммы и как максимума. Следствие --- последовательность x_1x_2... случайна по Мартин-Лёфу относительно равномерной меры тогда и только тогда, когда n-KP(x_1...x_n) ограничено сверху.
Перечислимые снизу меры на дереве. Эквивалентное определение с помощью вероятностных машин.
Сравнение префиксной сложности слова с суммой длины и ее (длины) префиксной сложности.
Наибольшие перечислимые снизу меры на дереве. Априорная сложность и ее свойства. Характеризация вычислимых последовательностей в терминах априорной сложности начальных фрагментов.
Монотонная сложность и ее свойства.