Владимир Андреевич Успенский
Четыре алгоритмических лица случайности
В.А.Успенский планирует провести одну лекцию.
Имеются записки!
Составленная из нулей и единиц цепочка 100010111011110100000111 выглядит более случайной, чем цепочка 010101010101010101010101. Возможно ли разделить все цепочки нулей и единиц на случайный и не случайные? Для конечных цепочек эта задача вряд ли осуществима. Однако можно пытаться решать её для бесконечных цепочек, т.е. для последовательностей. Иными словами, можно пытаться найти строгое математическое определение для понятия "случайная последовательностей нулей и единиц".
Традиционная теория вероятностей не только не приближается к решению этой задачи, но даже не может её сформулировать в своих терминах. На помощь приходит теория алгоритмов. Может показаться парадоксальным, что понятие случайности уточняется на основе такого чуждого случайности понятия, как алгоритм, — тем не менее, это так: все известные до сих пор определения случайности индивидуального объекта (в нашем примере — индивидуальной последовательности нулей и единиц) опираются на понятие алгоритма.
Чтобы найти требуемое определение, поступают так. Формулируют некое характеристическое свойство, которым обладают случайные (в неформальном, интуитивном смысле) последовательности. А затем последовательности, обладающие этим свойством, и объявляют, по определению, случайными.
Какими же свойствами обладает случайная последовательность нулей и единиц?
Во-первых, она частотноустойчива. Вот что это означает для того простейшего случая, когда нули и единицы равновероятны — а только такой случай мы и будем рассматривать: частота нулей, как и частота единиц, стремится к одной второй. При этом указанная устойчивость частот выполняется не только для последовательности в целом, но и для любой её законной, разумной подпоследовательности.
Во-вторых, она хаотична. Это означает, что чередование нулей и единиц не может быть описано никаким разумным правилом.
В-третьих, она типична. Это означает, что она принадлежит любому разумному большинству.
В-четвёртых, она непредсказуема. Это означает, что играя против неё на деньги (то есть пытаясь угадать члены последовательности и делая ставки), последовательность невозможно обыграть, какой бы разумной стратегией не пользоваться.
Слово "разумный", встречающееся в описаниях перечисленных четырёх свойств, разумеется, нуждается в уточнении. Теория алгоритмов как раз и предлагает такие уточнения, наполняя это слово точным смыслом --- своим для каждого из наших четырёх свойств. Тем самым возникают четыре алгоритмических свойства: частотная устойчивость, хаотичность, типичность, непредсказуемость. Каждое из них представляет своё собственное алгоритмическое лицо случайности, и каждое из них с большими или меньшими основаниями может претендовать на роль строгого математического определения для понятия случайности. Можно сказать и так: возникают четыре точно очерченных класса последовательностей, каждый из которых претендует на то, чтобы служить истинным классом случайных последовательностей; некоторые из этих претензий более оправданы, чем другие.
Для понимания лекции требуются следующие знания:
- 1. общие элементарные представления о множествах и функциях;
- 2. понимание термина "алгоритм";
- 3. для отдельного фрагмента лекции — понимание того, что такое сумма ряда с положительными членами.
Программа курсов и семинаров МЦНМО-НМУ в весеннем семестре 2024/2025 года
Расписание занятий в этом семестре
Курсы, читавшиеся в НМУ в разные годы (All Courses)
Если не указано иное, то начало занятий 7 февраля 2025.
Все обязательные курсы, почти все спецкурсы и некоторые доклады на спецсеминарах будут записываться на видео. Они будут доступны на общедоступном ресурсе.
К ВИДЕО-записям курсов этого семестра
Обязательные курсы
Первый курс
- Константин Валерьевич Логинов
- Алгебра-2
- читается по понедельникам с 17:30, очно+трансляция.
- Георгий Черных
- Топология-1
- читается по четвергам с 17:30, очно+трансляция.
- Олег Карлович Шейнман
- Математический анализ-2
- читается по пятницам с 17:30, очно+трансляция.
Второй курс
- Тарас Евгеньевич Панов
- Топология-3
- читается по понедельникам с 17:30 (семинары с 19:20), очно+трансляция
- Алексей Викторович Пенской
- Дифференциальная геометрия
- читается по средам с 17:30 (семинары с 19:20), очно+трансляция
- Алексей Игоревич Ильин
- Алгебра-4 (Группы и алгебры Ли)
- читается по четвергам с 17:30, очно+трансляция.
Список спецкурсов и спецсеминаров в весеннем семестре 2024/2025 года
- Михаил Юрьевич Розенблюм
- Алгебраическая теория чисел: введения. Продолжение годового спецкурса
- Денис Николаевич Терешкин
- Аддитивные и абелевы категории. Спецкурс рекомендован для 3-5 курсов.
- Константин Валерьевич Логинов
- Введение в ограниченность многообразий Фано. Спецкурс рекомендован для 3-5 курсов.
- Георгий Игоревич Шарыгин
- Циклические гомологии и их применения. Спецкурс рекомендован для 3-5 курсов.
- Андроник Арамович Арутюнов
- Грубая геометрия. Спецкурс в формате лекция + семинар, рекомендован для 3-5 курсов.
- Андрей Дмитриевич Рябичев
- Введение в поверхности бесконечного типа. Спецкурс рекомендован для 3-5 курсов.
- Георгий Борисович Шабат
- Тэта-функции и решетки. Часть 2. Спецкурс рекомендован для 3-5 курсов.
- Тарас Евгеньевич Панов
- Торическая топология, комбинаторика и теория гомотопий. Спецсеминар
- Георгий Игоревич Шарыгин и др.
- Деформационное квантование и квантовые группы. Спецсеминар
- А.М.Вербовецкий и И.С.Красильщик
- Когомологические аспекты геометрии дифференциальных уравнений,
руководители А.М.Вербовецкий и И.С.Красильщик - Николай Германович Мощевитин
- Диофантовы приближения. Спецсеминар рекомендован для 3-5 курсов
- Владимир Олегович Медведев
- Геометрия общей теории относительности. Спецкурс совместно с матфаком ВШЭ, рекомендован для 3-5 курсов.
- Алексей Викторович Пенской
- Риманова геометрия. Спецкурс совместно с матфаком ВШЭ, рекомендован для 3-5 курсов.
- Александр Борисович Калмынин
- Методы решета. Спецкурс рекомендован для 3-5 курсов.
- Алексей Викторович Пенской
- Спектральная геометрия. Спецсеминар рекомендован для 3-5 курсов.