RUSSIAN

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

By Успенский В.А. , Верещагин Н.К. , Шень А.

Book information

Publisher
МЦНМО
Year
2013
ISBN
978-5-4439-0212-8
Language
russian
Format
PDF
Filesize
4 MB (4012168 bytes)
Edition
1-е
Pages
575\575
Topic
Mathematics Logic
Library
homelab
Scanned
portrait
Time added
2014-06-12 06:00:00

Description

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

Similar books