Колмогоровская сложность и алгоритмическая случайность
Автор: | |
Название: | Колмогоровская сложность и алгоритмическая случайность |
Издательство: | МЦНМО | ISBN: | 978-5-4439-0212-8 |
Год издания: | 2013 | Тираж: | 1000 экз. |
Количество страниц: | 576 стр. | Формат: | 170x242x28 |
Стандарт: | 5 экз. | ||
Цена: | 415 руб. |
Классическая (шенноновская) теория информации измеряет количество информации, заключённой в случайных величинах. В середине 1960-х годов А.Н.Колмогоров (и другие авторы) предложили измерять количество информации в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект. Это определение послужило основой для алгоритмической теории информации, а также для алгоритмической теории вероятностей: объект считается случайным, если его сложность близка к максимальной.
Предлагаемая книга содержит подробное изложение основных понятий алгоритмической теории информации и теории вероятностей, а также наиболее важных работ, выполненных в рамках колмогоровского семинара по сложности определений и сложности вычислений, основанного А.Н.Колмогоровым в начале 1980-х годов.
Книга рассчитана на студентов и аспирантов математических факультетов и факультетов теоретической информатики.