Подробное описание документа

Верещагин Н. К., Успенский В. А., Шень А.
   Колмогоровская сложность и алгоритмическая случайность / Верещагин Н. К., Успенский В. А., Шень А. - М. : Изд-во МЦНМО, 2013. - 575 с. : ил. - Библиогр.: с. 546-558. - ISBN 978-5-4439-0212-8.

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