Колмогоровская сложность

Полугодовой спецкурс по выбору кафедры математической логики и теории алгоритмов.

Осенний семестр, 2023 год

Лекции состоятся по четвергам 18:30-20:05 онлайн. Подключение: https://us06web.zoom.us/j/83349943641?pwd=bkFTYm5VY3JSa3ZQYWY1L0VIWmN1UT09

Первая лекция 21 сентября.

Лектор: Н.К. Верещагин  nikolay.vereshchagin@math.msu.ru | Канал в Телеграм | Записи на доске | Записи лекций на YouTube

Примерная программа курса. 

Дневник лекций

Желающие сдать экзамен должны решить вот эти задачи в указанные сроки (скопируйте эту ссылку на Dropbox, поскольку сайт кафедры иногда падает). Сдача задач после срока невозможна.

Оценки за решения домашних задач

Оценки за курс (при условии посещения не менее 9 лекций):
отлично — 80% от максимального количества баллов,
хорошо — 62%, удовлетворительно — 45%. Зачет — 50%.

Для сдачи экзамена тем, кто не посетил 9 лекций, надо дополнительно сдать теорию по этой программе.

Литература.

• Nikolay Vereshchagin, Alexander Shen. Algorithmic statistics: forty years later. https://arxiv.org/abs/1607.08077
• Н.К. Верещагин, В.А. Успенский, А. Шень.
  Колмогоровская сложность и алгоритмическая случайность.
  Издательство МЦНМО. 2013.
  PDF