Юрий Львович Притыкин и Михаил Александрович Раскин

Последовательности, близкие к периодическим.

Ю.Л.Притыкин, М.А.Раскин планируют провести 4 занятия.

Наш предмет — комбинаторика слов (наука о конечных и бесконечных последовательностях букв конечного алфавита), но мы затронем и динамические системы (точнее, символическую динамику), логику, алгоритмы... Непонятные слова (например, конечный автомат или логическая теория) будут объясняться наглядно на примерах, то есть никаких особых предварительных знаний не предполагается — курс для всех желающих. Будет подготовлен список задач для решения.

Простейшими (с разных точек зрения) бесконечными последовательностями над конечным алфавитом являются периодические. Мы рассмотрим несколько вариантов обобщения — вот (пока формальный) объединяющий мотив сюжетов, планируемых для рассказа.

Начнем мы с примеров.

Последовательность почти периодична, если каждое входящее в неё подслово входит бесконечно много раз с ограниченными расстояниями между соседними вхождениями. Почти периодические последовательности (называемые также равномерно рекуррентными) изначально возникли как "дискретизация" динамических систем. Простейший пример — последовательность "a, если дробная часть n√2 больше 1/2, и b иначе" из букв a и b почти периодична.

Другой пример: естественной комбинаторной характеристикой последовательности является подсловная сложность — количество входящих в неё слов длины n как функция от n. Эта функция ограничена тогда и только тогда, когда последовательность периодична с некоторого места. Минимальная возможная подсловная сложность непериодической последовательности есть f(n) = n+1 — такие последовательности называются последовательностями Штурма, все они почти периодичны. Пример — известная последовательность Фибоначчи 010010100100101001010...

Еще пример: последовательность Туэ-Морса 0110100110010110... (кстати, не являющаяся последовательностью Штурма) также почти периодична.

Для введённых классов последовательностей интересно проследить за свойствами замкнутости относительно различных преобразований. Наиболее широкий класс из тех, что мы рассмотрим — конечные преобразователи (конечный автомат, читающий символы последовательности по одному и иногда пишущий что-то на выход). Интересная параллель здесь с логическими теориями на множестве натуральных чисел — параллель примерно такая же, как в случае конечных автоматов, распознающих конечные слова, и эквивалентного описания через регулярные выражения.

Затем мы рассмотрим другие свойства последовательностей, похожие на периодичность.

Периодическую последовательность можно описать как последовательность, порождаемую машиной с конечной памятью. Если немного обобщить класс рассматриваемых машин и разрешить им читать ранее написанные символы снова, получим класс так называемых автоматных последовательностей. Другое эквивалентное определение — конечный автомат читает число n, записанное в некоторой фиксированной системе счисления, и выдаёт n-й символ последовательности. Для таких последовательностей мы также рассмотрим их любопытные свойства, в том числе свойства замкнутости, связи с теорией чисел.

Периодическая последовательность получается покрытием натурального ряда копией одного конечного слова без перекрытий. Если перекрытия в таких покрытиях разрешить, получается интересный комбинаторный объект — квазипериодические последовательности.

Слова Тёплица (изначально возникшие для описания топологических пространств) получаются, если заполнять натуральный ряд символами, позиции которых образуют арифметические прогрессии.

Программа курсов и семинаров МЦНМО-НМУ в весеннем семестре 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 курсов.