Колмогоровская сложность (А.С. Милованов, осень 2021)
Лектор - А.С. Милованов
Время и место: понедельник, 17:05-18:30, первое занятие - 13 сентября, http://meet.google.com/fpv-khtf-ofk
Описание
Понятие колмогоровской сложности появилось в 1960-е годы на стыке теории алгоритмов, теории информации и теории вероятностей. Идея А.Н. Колмогорова состояла в том, чтобы измерять количество информации, заключенной в индивидуальных конечных объектах. Оказалось, что это возможно (хотя лишь с точностью до аддитивной
константы). Неформальное определение колмогоровской сложности слова x такое: это минимальная длина программы, которая на пустом входе выдаёт x. (Такое определение зависит от выбора языка программирования, но на самом деле эта зависимость небольшая.) В курсе будут рассказаны основные понятия этой теории (случайность по Мартин-Лёфу, априорная вероятность, и т.д.), а также будут рассказаны некоторые приложения (например, в комбинаторике и теории автоматов). Хотя колмогоровская сложность невычислима, и поэтому не может использоваться на практике непосредственно, она являлась родительницей многих идей теории обучения.