Читать онлайн «Колмогоровская сложность и алгоритмическая случайность»

Н. К. Верещагин, В. А. Успенский, А. Шень Колмогоровская сложность и алгоритмическая случайность K(y, z) z) K(x, K(x, y) 2 K(x, y, z)  K(x, y) + K(x, z) + K(y, z)  î. ë. ÷ÅÒÅÝÁÇÉÎ ÷. á. õÓÐÅÎÓËÉÊ á. ûÅÎØ ëïìíïçïòï÷óëáñ óìïöîïóôø é áìçïòéôíéþåóëáñ óìõþáêîïóôø íÏÓË×Á éÚÄÁÔÅÌØÓÔ×Ï íãîíï 2013 УДК 510. 5 ББК 22. 12 В77 Верещагин Н. К. и др. В77 Колмогоровская сложность и алгоритмическая случайность / Н. К. Верещагин, В. А. Успенский, А. Шень. | М. : МЦНМО, 2013. | 576 с. ISBN 978-5-4439-0212-8 Классическая (шенноновская) теория информации измеряет количество ин- формации, заключённой в случайных величинах. В середине 1960-х годов А. Н. Колмогоров (и другие авторы) предложили измерять количество информа- ции в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект. Это определение послужило основой для алгоритмической теории информации, а также для алгоритмической теории вероятностей: объект считается случайным, если его сложность близка к максимальной. Предлагаемая книга содержит подробное изложение основных понятий ал- горитмической теории информации и теории вероятностей, а также наиболее важных работ, выполненных в рамках «колмогоровского семинара по сложно- сти определений и сложности вычислений», основанного А. Н. Колмогоровым в начале 1980-х годов. Книга рассчитана на студентов и аспирантов математических факультетов и факультетов теоретической информатики. ББК 22. 12 В оформлении форзацев использованы фрагменты рукописи статьи А. Н. Колмогорова [64]. Николай Константинович Верещагин Владимир Андреевич Успенский Александр Шень КОЛМОГОРОВСКАЯ СЛОЖНОСТЬ И АЛГОРИТМИЧЕСКАЯ СЛУЧАЙНОСТЬ Издательство Московского центра непрерывного математического образования 119002, Москва, Большой Власьевский пер. , 11. Тел. (499) 241-74-83 Подписано в печать 02. 11. 2012 г. Формат 70×100 1/16. Бумага офсетная. Печать офсетная. Печ. л. 36. Тираж 1000. Заказ . Отпечатано в ППП «Типография "Наука\». 121099, Москва, Шубинский пер. , д. 6. ISBN 978-5-4439-0212-8 c Н. К. Верещагин, В. А. Успенский, А. Шень, 2013. Памяти Андрея Мучника  Предисловие Понятие колмогоровской сложности (или, как ещё говорят, алгоритмической энтропии ) появилось в 1960-е годы на стыке теории алгоритмов, теории инфор- мации и теории вероятностей.