Комбинаторика слов появляется в алгебре, динамических системах и биоинформатике.
Пусть 𝑊 – бесконечное слово над бинарным алфавитом 𝐴 = {𝑎, 𝑏}. Тогда
2. Слово не периодично и является сбалансированным, то есть для любых двух
подслов 𝑢, 𝑣 ⊂ 𝑊 одинаковой длины выполняется неравенство ||𝑣|𝑎−|𝑢|𝑎|ď 1, где
|𝑤|𝑎 обозначает количество вхождений символа 𝑎 в слово 𝑤.
(Если для любых двух подслов 𝑢, 𝑣 ⊂ 𝑊 одинаковой длины выполняется равен-
ство ||𝑣|𝑎−|𝑢|𝑎|= 0 то 𝑊 периодично)
3. Слово 𝑊 = (𝑤𝑛) является механическим словом с иррациональным 𝛼. Это
значит следующее. Возьмем единичную окружность 𝑆1 с дугой длины 𝛼 и ее после-
довательный сдвиг на то же самое 𝛼. При попадании на эту дугу пишем 𝑎, иначе 𝑏.
Оказывается, эти условия «почти» эквивалентны в том смысле что есть только счетное число сверхслов, удовлетворяющих одному условию, но не удовлетворяющих другому.
Воронов Всеволод Александрович (КМЦ АГУ) – «Неархимедовы абсолютные значения и задачи о раскрасках пространства»
Можно ли разрезать квадрат на нечетное число треугольников равной площади? Можно ли покрасить плоскость в три цвета таким образом, чтобы ни один из цветов не был сосредоточен на одной прямой, и на любой прямой встречались точки не более двух цветов? Ответы на эти вопросы были даны около 40 лет назад, причем, несмотря на внешнюю простоту формулировки, решения опираются на теорию так называемых неархимедовых абсолютных значений. О том, что они из себя представляют, и каким образом их можно пытаться применить в других задачах о раскрасках плоскости, сферы, пространства и т.п., мы поговорим на курсе. В случаях, которые мы собираемся рассматривать, не потребуется знаний, выходящих за пределы школьной программы.
Как построить безопасную систему авторизации на сервере? Примитивная схема состоит в том, что сервер хранит пароль и сравнивает с ним присланную пользователем строку. Тут есть риск кражи пароля и с сервера, и при перехвате сообщения.
Неустроева Елизавета Андреевна (ФПМИ МФТИ) – «Теория Рамсея и теорема Ван дер Вардена»
В теории Рамсея решаются задачи о том, каким условиям должен удовлетворять объект, чтобы в нем появился определенный внутренний порядок. Например, сколько человек достаточно позвать на вечеринку, чтобы среди них нашлись или трое попарно знакомых, или трое попарно незнакомых (кстати, а сколько?). Менее очевидный пример — теорема Ван дер Вардена, утверждающая, что при любой раскраске натуральных чисел в два цвета найдётся сколь угодно длинная арифметическая прогрессия.
Мы обсудим несколько задач теории Рамсея, докажем теорему Ван дер Вардена и ее обобщение, выясним, как нахождение чисел Ван дер Вардена связано с DPLL-алгоритмом определения выполнимости булевых формул.
Никаких специальных знаний не нужно, все необходимые определения обсудим 🙂
Райгородский Андрей Михайлович (ФПМИ МФТИ, мехмат МГУ) – «Одна недавняя новая задача»
В лекции я расскажу об одной совсем свежей задаче с Московской олимпиады и о ее связи с целым пластом теории графов и гиперграфов – от топологических до вероятностных методов и обратно
Савватеев Алексей Владимирович (ФПМИ МФТИ) – «Дока-
зательная геометрия»
На рубеже XVIII-XIX веков произошла «первая математическая революция» (вторая происходит на рубеже XX-XXI веков на наших с вами глазах). А именно, был решен целый ряд задач, стоявших с античных времён. Среди них: как найти общую формулу для корней уравнения пятой (и более высокой) степени; как построить с помощью циркуля и линейки куб, вдвое бОльший данного; как разделить данный угол на три равные части; и некоторые другие проблемы. Общей характерной чертой полученных решений было то, что они содержали доказательства невозможности требуемого в задачах. На этом пути произошло становление науки, которую я бы назвал «доказательной геометрией». Речь идёт о сведении геометрических формулировок к задачам из области чистой алгебры, и затем, после наращивания «военной техники», прихода к противоречию с логикой изучаемых алгебраических конструкций.
Савватеев Михаил Алексеевич (ФПМИ МФТИ) : «Dynamic Connectivity Problem»
Представим себе, что у вас есть граф, и вы хотите делать с ним операции 3 типов:
1. Добавить ребро.
2. Удалить ребро.
3. Проверить, лежат ли 2 вершины в одной компоненте связности.
Оказывается, что в общем (да и в частных) случаях это очень сложно…
В конце же (если хватит времени) обсудим на каком-то уровне и общий алгоритм DCP-online 🙂 Для понимания желательно, чтобы запись 𝑂(𝑛 log(𝑛)) не сильно смущала вас.
Садовников Александр Владимирович (Сириус): «Введение в машинное обучение»
В рамках курса вы познакомитесь с азами машинного обучения — науки, которая лежит в основе современных технологий искусственного интеллекта. Машинное обучение исследует алгоритмы, которые буквально учатся решать поставленную задачу на основе реальных примеров.
Из курса вы научитесь формулировать задачу в терминах машинного обучения, поймёте, из каких этапов состоит её решение и какие математические модели для этого используются. В частности, познакомитесь с одними из самых распространённых моделей — моделями линейной и логистической регрессии.
Сколькими способами можно раскрасить грани кубика в три цвета, если кубик разрешается вращать? Попытка решить эту задачу “в лоб” упирается в довольно неприятный перебор, который трудно сделать аккуратно. Однако есть и более простой способ: оказывается, для каждого из возможных вращений кубика надо взять количество “неподвижных точек” — раскрасок, которые это вращение переводит в себя — и взять у полученных чисел среднее арифметическое; это и будет искомое число раскрасок.
Это пример применения формулы Бернсайда, с помощью которой можно вычислить количество орбит действия группы на конечном множестве. Что такое группа, в каком смысле она где-то действует и кто такие эти самые орбиты — это все я расскажу в курсе. Далее мы получим мощное обобщение формулы Бернсайда: теорему Пойя о перечислении, благодаря которой разберемся (в примере с кубом), как считать раскраски с предписанным числом граней каждого цвета. Разумеется, раскрашивать в разные цвета мы будем не только куб, но и другие многогранники, и графы, и ожерелья, и много чего еще.
Планируется две лекции. Предварительных знаний не требуется, хотя навык обращения с перестановками будет полезен.
Соколов Артемий Алексеевич (ЦПМ, ФПМИ МФТИ) : «Ветвящиеся процессы Гальтона–Ватсона»
Представьте, что у вас есть частица, которая распадается на случайное количество других таких же частиц. А эти частицы, вслед за этим, распадаются еще на несколько других частиц, и так далее. Понятно, что в каждый момент количество предсказать точно не получится, оно будет сильно зависеть от того, чтобы было на прошлых шагах.
Как изучать такой процесс? Как понять, выродится он или нет, и если да, то с какой вероятностью?
На эти и многие другие вопросы мы будем отвечать в этом курсе. Представления о вероятности полезны, но не обязательны