| Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ»
|
| (А. М. Райгородский) | 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.1 | 184
|
| 7.4. «Просто» и «сложно» предсказуемые конечные последовательности | 187
|
| 7.4.1. Доказательство предложения 7.4 | 192
|
| 7.4.2. Доказательство предложения 7.5 | 194
|
| Часть 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 году аналогичный проект стартовал в Пскове.
И это только начало! Мы мотивируем наших лучших студентов хотя бы на время возвращаться в регионы, в олимпиадное, кружковое и проектное движение для поддержки высокого уровня этого движения во всей нашей стране. Мы с удовольствием делимся с региональными вузами нашими программами в рамках сетевых образовательных проектов, инициируемых Физтехом и призванных помогать регионам удерживать у себя достаточно сильных абитуриентов.
И конечно, мы очень рады представить наше новое начинание — «Учебник Школы прикладной математики и информатики МФТИ».
В серии книг наши ведущие специалисты поделятся своими знаниями и методическими наработками со студентами, аспирантами, учеными, педагогами и просто со всеми, кто любит математику и ее приложения, хочет оказаться на гребне знаний и увидеть далекую перспективу. Как я часто говорю в своих выступлениях: «Присоединяйтесь к нам!»
А. М. Райгородский, директор Школы прикладной математики и информатики МФТИ,
заведующий кафедрой дискретной математики, профессор,
доктор физико-математических наук.
