Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Колмогоровская сложность и теория информации

Спецкурс читает Н. К. Верещагин или А. Х. Шень.

Колмогоровскую сложность слова в данном алфавите можно определить как длину кратчайшей программы, печатающей слово. Цель спецкурса — изложение основ теории колмогоровской сложности и её многочисленных применений (к обоснованию теории вероятностей, к получению оценок времени работы алгоритмов и т. д.).

Подробную программу и конспекты лекций можно посмотреть на веб-странице Н.К.Верещагина.