Билеты по курсу «Математические основы  машинного обучения», Вьюгин ВВ, Семестр 2, 2020г.

Билеты по по курсу "Онлайн методы машинного обучения" Семестр 2 (2020г.) 

Билеты по курсу "Колмогоровская сложность и ее приложения", 2019, Семестр 1

-------------------------------------------------------------------------------------------------------------------------------------------------

"Колмогоровская сложность и ее приложения", 2019, Семестр 1

Задачи 3 Link

Программа и билеты для зачета 

I. Элементы вероятностной теории информации.

1. Алфавиты, коды. Однозначно декодируемые коды, безпрефиксные коды. Неравенство и теорема Крафта. Теорема Макмиллана.

2. Энтропия Шеннона и ее свойства. Энтропия пары случайных величин, условная энтропия и их свойства. Правило цепи.

3. Относительная энтропия (расхождение Кульбака-Лейблера), ее свойства. Количество информации, связь с энтропией.

4. Энтропия стационарного стохастического процесса. Опыты с текстами естественного языка.

5. Алгоритм универсального сжатия информации Зива—Лемпеля. Лемма Каца. Упрощенный вариант теоремы об оптимальности сжатия.

II. Определение колмогоровской сложности и ее свойства.

1. Алфавиты, конструктивные объекты, кодирование натуральных чисел, пар, троек строк. Понятие алгоритма, вычислимые функции, Формализация понятия алгоритма: вычислимые функции, машины Тьюринга и др. Идея построения универсальной машины Тьюринга. Универсальная функция. Перечислимые и разрешимые множества. Пример перечислимого и неразрешимого множества. Проблема остановки.

2. Простая колмогоровская сложность. Теорема инвариантности (теорема существования). Простейшие свойства колмогоровской сложности. Невычислимость сложности. Верхние оценки сложности. Теорема о неполноте.

3. Сложность пары конечных объектов. Условная сложность. Теорема Колмогорова -- Левина о сложности пары.

4. Количество информации. Свойство симметричности функции информации.

5. Несжимаемые последовательности и их свойства. Связь сложности и энтропии Шеннона. Простейший закон больших чисел.

II. Бесконечные случайные последовательности и колмогоровская сложность

1. Конструктивный анализ теории вероятностей. Пространство бесконечных двоичных последовательностей, задание мер на нем. Вычислимые меры. Эффективно нулевые множества. Существование максимального по включению эффективно-нулевого множества. Случайность по Мартин-Лефу. Примеры эффективно нулевых множеств..

2. Логика теории вероятностей. Законы теории вероятностей, их формулировки для индивидуальных случайных последовательностей. Доказательство усиленного закона больших чисел для случайных по Мартин-Лефу последовательностей.  

3. Безпрефиксные методы кодирования. Префиксная сложность, ее существование и свойства. Обобщенное  неравенство Крафта.