Обложка Вьюгин В.В. Колмогоровская сложность и ее приложения
Id: 290251
649 руб. Новинка недели!

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

URSS. 2022. 256 с. ISBN 978-5-9710-9882-9.
Типографская бумага
Энтропия Шеннона • Колмогоровская сложность • Случайность по Мартин-Лёфу • Префиксная и монотонная модификации колмогоровской сложности • Универсальное прогнозирование • Алгоритмический анализ утверждений теории вероятностей.

Аннотация

Книга предназначена для первоначального знакомства с основами теории колмогоровской сложности и алгоритмической случайности. В первой части приводятся элементы шенноновской теории информации и кодирования. Во второй части приведены основные понятия и теоремы колмогоровского подхода к обоснованию теории вероятностей и теории информации на основе теории алгоритмов. Вводятся и изучаются понятия различных видов колмогоровской сложности:... (Подробнее)


Оглавление
Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ»
(А. М. Райгородский)7
Введение9
Часть I Элементы вероятностной теории информации17
Глава 1. Кодирование18
1.1. Коды19
1.2. Энтропия Шеннона и коды22
1.3. Энтропия стационарного процесса30
1.4. Задачи и упражнения32
Глава 2. Универсальное сжатие информации34
2.1. Алгоритм Зива–Лемпеля34
Часть II Алгоритмическая теория информации41
Глава 3. Простая колмогоровская сложность42
3.1. Основные понятия теории алгоритмов42
3.1.1. Конструктивные объекты43
3.1.2. Алгоритмы47
3.2. Определение колмогоровской сложности52
3.3. Несжимаемые последовательности59
3.4. (α, β)-стохастические по Колмогорову последовательности64
3.5. Сложность пары70
3.6. Количество информации72
3.7. Задачи и упражнения74
Глава 4. Случайность по Мартин-Лёфу78
4.1. Тесты Мартин-Лёфа78
4.2. Универсальный тест Мартин-Лёфа84
4.3. Задачи и упражнения90
Глава 5. Специальные виды алгоритмической сложности93
5.1. Префиксное декодирование94
5.1.1. Префиксная сложность94
5.1.2. Модель вычисления99
5.1.3. Априорная полумера на дискретном множестве101
5.1.4. Двойственность106
5.1.5. Префиксная сложность пары112
5.2. Монотонные способы декодирования115
5.2.1. Монотонная сложность115
5.2.2. Теорема Левина–Шнорра120
5.3. Вычислимые меры123
5.4. Случайность относительно разбиения129
5.5. Задачи и упражнения134
Глава 6. Универсальное прогнозирование139
6.1. Универсальная полумера на дереве всех двоичных последовательностей139
6.2. Универсальный предиктор152
6.2.1. Правило Лапласа154
6.2.2. Универсальный предиктор Соломонова157
6.3. Задачи и упражнения162
Глава 7. Предсказательная сложность166
7.1. Вычислимые прогнозирующие системы166
7.2. Смешиваемые функции потерь168
7.3. Определение предсказательной сложности177
7.3.1. Доказательство леммы 7.1184
7.4. «Просто» и «сложно» предсказуемые конечные последовательности187
7.4.1. Доказательство предложения 7.4192
7.4.2. Доказательство предложения 7.5194
Часть III Алгоритмический анализ утверждений теории вероятностей200
Глава 8. Сложностное доказательство закона повторного логарифма202
Глава 9. Эргодическая теорема Биркгофа208
9.1. Эргодическая теория209
9.2. Алгоритмически эффективная сходимость213
9.3. Алгоритмически эффективный вариант эргодической теоремы для эргодических преобразований217
9.4. Отсутствие вычислимой оценки скорости сходимости в эргодической теореме220
9.5. Интегральные тесты случайности224
9.6. Эргодическая теорема для случайных по Мартин-Л?ефу последовательностей227
9.7. Задачи и упражнения235
Часть IV Приложение237
Глава 10. Дополнительные сведения238
10.1. Вычислимые вещественные функции238
10.2. Колмогоровская сложность и структуры статистической физики245
Литература250

Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ»

Физтех-школа прикладной математики и информатики (ФПМИ) — это активно развивающееся подразделение МФТИ, возникшее в результате успешного объединения двух факультетов — факультета управления и прикладной математики и факультета инноваций и высоких технологий.

Сейчас ФПМИ занимает лидерские позиции в России и в мире, давая своим студентам как традиционно мощное физтеховское фундаментальное образование, так и столь же традиционные для МФТИ выходы на самые современные прикладные задачи, возникающие в высокотехнологичной индустрии.

Разумеется, ФПМИ старается быть открытой всем. Например, в интернет-проекте «Лекторий ФПМИ» выложены записи многих лекций, читаемых в нашей Школе. В 2017 году был создан региональный научно-образовательный «Кавказский математический центр» в Майкопе, который получает постоянную поддержку от ФПМИ. А в 2021 году аналогичный проект стартовал в Пскове.

И это только начало! Мы мотивируем наших лучших студентов хотя бы на время возвращаться в регионы, в олимпиадное, кружковое и проектное движение для поддержки высокого уровня этого движения во всей нашей стране. Мы с удовольствием делимся с региональными вузами нашими программами в рамках сетевых образовательных проектов, инициируемых Физтехом и призванных помогать регионам удерживать у себя достаточно сильных абитуриентов.

И конечно, мы очень рады представить наше новое начинание — «Учебник Школы прикладной математики и информатики МФТИ».

В серии книг наши ведущие специалисты поделятся своими знаниями и методическими наработками со студентами, аспирантами, учеными, педагогами и просто со всеми, кто любит математику и ее приложения, хочет оказаться на гребне знаний и увидеть далекую перспективу. Как я часто говорю в своих выступлениях: «Присоединяйтесь к нам!»

А. М. Райгородский, директор Школы прикладной математики и информатики МФТИ,

заведующий кафедрой дискретной математики, профессор,

доктор физико-математических наук.


Об авторе
Вьюгин Владимир Вячеславович
Доктор физико-математических наук, профессор. Окончил механико-математический факультет МГУ имени М. В. Ломоносова по специальности «Математика» в 1971 г. В 1975 г. защитил в МГУ кандидатскую, а в 2001 г. — докторскую диссертацию в области физико-математических наук. С 1996 г. главный научный сотрудник в Институте проблем передачи информации РАН. Заведующий Лабораторией теории передачи информации и управления. Также преподает в Московском физико-техническом институте в должности профессора школы прикладной математики и информатики.

Научные интересы: приложения колмогоровской теории алгоритмической сложности к логическим основам теории вероятностей, математические основы машинного обучения и прогнозирования.