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

М.: МЦНМО, 2010.— 556 с.
Классическая (шенноновская) теория информации измеряет количество информации в случайных величинах. В середине 1960-х годов
А. Н. Колмогоров (и другие авторы) предложили измерять количество информации в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект.
Это определение послужило основой для алгоритмической теории информации, а также для алгоритмической теории вероятностей: объект считается случайным, если его сложность близка к максимальной.
Предлагаемая книга содержит подробное изложение основных понятий
алгоритмической теории информации и теории вероятностей, а также наиболее
важных работ, выполненных в рамках «колмогоровского семинара по сложности определений и сложности вычислений», основанного А.Н. Колмогоровым
в начале 1980-х годов.
Книга рассчитана на студентов и аспирантов математических факультетов
и факультетов теоретической информатики.