Колмогоровская сложность и алгоритмическая случайность
- Автор(ы)
- Успенский В.А, Верещагин Н.К, Шень А
- Год
- 2013
- Издательство
- МЦНМО
- Язык
- rus
- ISBN
- 978-5-4439-0212-8
- Библиографическая ссылка
- М.: МЦНМО, 2013. | 576 с.
- Теги
- Компьютеры и информационные технологии Программирование
Аннотация
Колмогоровская сложность и алгоритмическая случайность Год издания : 2013 Авторы : Верещагин Н.К., Успенский В.А., Шень А. Жанр или тематика : Учебное пособие Издательство : М.: Изд. МЦНМО ISBN : 978-5-4439-0212-8 Язык : Русский Формат : PDF Качество : Издательский макет или текст (eBook) Интерактивное оглавление : Да Количество страниц : 577 Тираж : 1000 экз. Описание : Классическая (шенноновская) теория информации измеряет количество информации, заключённой в случайных величинах. В середине 1960-х годов А.Н. Колмогоров (и другие авторы) предложили измерять количество информации в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект. Это определение послужило основой для алгоритмической теории информации, а также для алгоритмической теории вероятностей: объект считается случайным, если его сложность близка к максимальной. Предлагаемая книга содержит подробное изложение основных понятий алгоритмической теории информации и теории вероятностей, а также наиболее важных работ, выполненных в рамках «колмогоровского семинара по сложности определений и сложности вычислений», основанного А. Н. Колмогоровым в начале 1980-х годов. Книга рассчитана на студентов и аспирантов математических факультетов и факультетов теоретической информатики. Примеры страниц Оглавление Предисловие 4 О чём эта книга? 8 1. Простая колмогоровская сложность 23 1.1. Определение и основные свойства 23 1.2. Алгоритмические свойства 29 1.2.1. Простые слова и простые множества 30 1.2.2. Сложность больших чисел 31 2. Сложность пары и условная сложность 39 2.1. Сложность пары 39 2.2. Условная сложность 42 2.3. Количество информации 54 3. Случайность по Мартин-Лёфу 62 3.1. Пространство и меры 62 3.2. Усиленный закон больших чисел 65 3.3. Эффективно нулевые множества 69 3.4. Свойства случайных последовательностей 77 3.5. Дефект случайности 82 4. Априорная вероятность и префиксная сложность 87 4.1. Вероятностные машины и полумеры на N 87 4.2. Наибольшая полумера 92 4.3. Префиксные машины 94 4.4. Отступление: машины с самоограниченным входом 98 4.4.1. Беспрефиксные функции 99 4.4.2. Префиксно корректные функции 101 4.4.3. Непрерывные вычислимые отображения 103 4.5. Основная теорема о префиксной сложности 105 4.6. Свойства префиксной сложности 111 4.7. Условная префиксная сложность и сложность пары 118 4.7.1. Условная префиксная сложность 118 4.7.2. Свойства условной префиксной сложности 120 4.7.3. Префиксная сложность пары 122 4.7.4. Обычная и префиксная сложности 129 5. Монотонная и априорная сложности и случайность 132 5.1. Вероятностные машины и полумеры на дереве 132 5.2. Наибольшая перечислимая полумера на дереве 139 5.3. Свойства априорной сложности 140 5.4. Вычислимые отображения 144 5.4.1. Непрерывные отображения 145 5.4.2. Монотонные машины с неблокирующим чтением 146 5.4.3. Перечислимость множества вычислимых отображений 147 5.5. Монотонная сложность 148 5.5.1. Доказательство тео