Дневник лекций 2010 года
17-May-2010
Доказательство закона повторного логарифма с помощью монотонной
сложности (или априорной вероятности на дереве).
3-May-2010
Перечислимые снизу распределения вероятности на пространстве конечных
и бесконечных последовательностей нулей и единиц. Существование
максимального перечислимого снизу распределения. Априорная вероятность.
Сравнение монотонной сложности и логарифма априорной вероятности.
Теорема Гача о их несовпадении (без доказательства).
Критерий случайности последовательности в терминах монотонной сложности
и априорной вероятности.
26-Apr-2010
Доказательство усиленного закона больших чисел с помощью колмогоровской
сложности. Теорема Хартли-Литтлвуда (оценка O(\sqrt{\log n/n}))
отклонения вероятности от
частоты для случайных по МЛ последовательностей.
Монотонная сложность и сложность разрешения. Их монотонность. Сравнение
с обычной и префиксной сложностями. Характеризация вычислимых
последовательностей в их терминах. Комбинаторная характеризация сложности
разрешения.
19-Apr-2010
Условная префиксная сложность. Релятивизация неравенств с
префиксной сложностью.
Условные перечислимые снизу полумеры и совпадение условной
префиксной сложности и минус логарифма априорной вероятности.
Теорема о префиксной сложности пары слов.
12-Apr-2010
Существование вычислимой относительно 0′ случайной последовательности.
Теорема о совпадении префиксной сложности и минус логарифма
априорной вероятности.
Характеризация случайных по МЛ последовательностей в терминах префиксной
сложности.
5-Apr-2010
(Читал Андрей Ромащенко) Перечислимые снизу полумеры на натуральных числах.
Полумеры, задаваемые вероятностными алгоритмами. Совпадение этих классов.
Существование максимальной полумеры (априорной вероятности).
Префиксно корректные функции, существование оптимальной префиксно корректной
функции, префиксная сложность.
29-Mar-2010
Наибольшее конструктивно нулевое множество (для произвольной вычислимой
меры).
Свойства случайных по равномерной мере
последовательностей: вычислимые последовательности
не случайны (но существуют случайные невычислимые последовательности),
устойчивость понятия случайности относительно конечных изменений,
вычислимая подпоследовательность случайной последовательности случайна.
Неслучайность характеристических функций перечислимых множеств.
22-Mar-2010
Вероятностные меры на пространстве
бесконечных последовательностей нулей и единиц.
Вычислимые действительные числа и вычислимые меры.
Множества меры нуль (нулевые множества).
Конструктивно нулевые множества.
Случайные по Мартин-Лёфу последовательности.
Усиленный закон больших чисел. Стремление к 1/2 доли единиц в случайной
по Мартин-Лёфу последовательности (для равномерной меры).
15-Mar-2010
Доказательства неравенств с помощью диаграмм.
Различные неравенства для общей информации.
Теорема Шеннона о совершенном шифре.
Применения колмогоровской сложности: бесконечность множества простых
чисел, квадратичная нижняя оценка для времени распознавания палиндромов
на одноленточных машинах Тьюринга, квадрат мощности дискретного
трехмерного множества не превосходит произведения мощностей трех
его плоских проекций.
1-Mar-2010
Невозможность избавиться от добавочного члена
log n в теореме Колмогорова-Левина (в обоих неравенствах).
Информаци в x об y и ее свойства.
Релятивизация неравенств для колмогоровской сложности.
Базисное неравенство. Общая информация тройки слов и пример,
когда она отрицательна.
27-Feb-2010
Колмогоровская сложность других объектов. Колмогоровская сложность
пары слов (верхняя оценка). Невозможность сделать постоянным
добавочный член в этом неравенстве.
Условная сложность. Ее свойства. Теорема Колмогорова-Левина.
15-Feb-2010
Определение простой колмогоровской сложности.
Неувеличение сложности при алгоритмических преобразованиях.
Сложность слова и его длина. Количество слов малой
сложности и существование несжимаемых слов.
Невычислимость колмогоровской сложности. Ограниченность вычислимых
нижних оценок колмогоровской сложности.
Перечислимость сверху колмогоровской сложности.
Эквивалентное определение колмогоровской сложности как
наименьшей перечислимой сверху функции с условием нормировки.