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

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


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

Колмогорову принадлежит одно из наиболее замечательных определений математики — сложности объекта, как минимальной длины его описания. Основы теории колмогоровской сложности объектов были построены А.Н. Колмогоровым во время его поездки в Индию в 1964 году. Поставленная в его индийской статье проблема была решена 40 лет спустя Ан.А. Мучником и А.Л. Семеновым, за что они получили премию Колмогорова Российской академии наук. Подход Колмогорова является основой сегодняшних представлений о количестве информации и меры случайности. Этот подход, как и проблематику сложности вычислений развивают сегодня Н. К. Верещагин, А. Шень и их ученики. Многие важные проблемы о колмогоровской сложности понятны и интересны даже младшекурсникам. Вот примеры таких (нерешенных) проблем: задача о кошках и муравьяхзадача о разделении ресурсов в иерархической структурезадача об он-лайн паросочетанияхзадача об избегании окрашенных мест.