М.: МЦНМО, 2013. - 576 с. - ISBN 978-5-4439-0212-8, eBook, Русский
Классическая (шенноновская) теория информации измеряет количество
информации, заключённой в случайных величинах. В середине 1960-х
годов А. Н. Колмогоров (и другие авторы) предложили измерять
количество информации в конечных объектах с помощью теории
алгоритмов, определив сложность объекта как минимальную длину
программы, порождающей этот объект.
Это определение послужило основой для алгоритмической теории информации, а также для алгоритмической теории вероятностей: объект считается случайным, если его сложность близка к максимальной.
Предлагаемая книга содержит подробное изложение основных понятий алгоритмической теории информации и теории вероятностей, а также наиболее важных работ, выполненных в рамках «колмогоровского семинара по сложности определений и сложности вычислений», основанного А. Н. Колмогоровым в начале 1980-х годов.
Книга рассчитана на студентов и аспирантов математических факультетов и факультетов теоретической информатики. Краткое содержание:
Простая колмогоровская сложность
Сложность пары и условная сложность
Случайность по Мартин-Лёфу
Априорная вероятность и префиксная сложность
Монотонная и априорная сложности и случайность
Общая классификация сложностей
Шенноновская энтропия и колмогоровская сложность
Некоторые приложения
Частотный и игровой подходы к определению случайности
Неравенства для энтропии, сложности и размера
Общая информация
Алгоритмическая теория информации для нескольких источников
Информация и логика
Алгоритмическая статистика
Приложение 1: Колмогоровская сложность и основания теории вероятностей
Приложение 2: Четыре алгоритмических лица случайности
Это определение послужило основой для алгоритмической теории информации, а также для алгоритмической теории вероятностей: объект считается случайным, если его сложность близка к максимальной.
Предлагаемая книга содержит подробное изложение основных понятий алгоритмической теории информации и теории вероятностей, а также наиболее важных работ, выполненных в рамках «колмогоровского семинара по сложности определений и сложности вычислений», основанного А. Н. Колмогоровым в начале 1980-х годов.
Книга рассчитана на студентов и аспирантов математических факультетов и факультетов теоретической информатики. Краткое содержание:
Простая колмогоровская сложность
Сложность пары и условная сложность
Случайность по Мартин-Лёфу
Априорная вероятность и префиксная сложность
Монотонная и априорная сложности и случайность
Общая классификация сложностей
Шенноновская энтропия и колмогоровская сложность
Некоторые приложения
Частотный и игровой подходы к определению случайности
Неравенства для энтропии, сложности и размера
Общая информация
Алгоритмическая теория информации для нескольких источников
Информация и логика
Алгоритмическая статистика
Приложение 1: Колмогоровская сложность и основания теории вероятностей
Приложение 2: Четыре алгоритмических лица случайности