Алгоритмическая теория информации пытается измерить количество информации в данном сообщении как число битов в наиболее сжатом его описании (колмогоровская сложность). Будут изучены

• определение и свойства сложности;
• условная сложность и сложность пары;
• связь с комбинаторикой и шенноновской теорией информации;
• сложность и случайность, эффективные теоремы теории вероятностей и случайные последовательности;
• вероятностные доказательства и их сложностное изложение;
• сложность и априорная вероятность (префиксная, монотонная сложности).

В.А. Успенский, Н.К. Верещагин, А. Шень, Колмогоровская сложность (черновик книги)

Видео лекций: https://www.lektorium.tv/course/22751