Алексей Яковлевич Белов-Канель (ФИВТ МФТИ, Bar-Ilan University) «Теория информации, конечные автоматы, лабиринты и математическое моделирование обучающего поведения»
Что такое количество информации? Это понятие имеет как олимпиадные аспекты (взвешивание и т.д.) так и житейские. Какую информацию несет утверждение что в Сахаре 15 июля дождя не будет? Как ее измерять? Что такое обучаемое поведение? Метод приспособления? Все эти понятия оказываются весьма нетривиальными и глубокими.
Примерный план курса:
- Понятие конечного автомата. Конечные автоматы в математике, computer science, биологии. Примеры. Автомат Мура.
- Система среда-организм как пара взаимодействующих конечных автоматов. Целесообразность.
- Обучаемость. Модель обучаемого поведения.
- Методы приспособления.
- Применение к биологии поведения.
- Тестирование. Система организм-среда и математическая модель тестирования.
Всеволод Воронов (ИДСТУ СО РАН) «Геометрия целых квадратичных форм»
Целой бинарной квадратичной формой называют полином вида ax^2+bxy+cy^2, где a, b, c – целые. Некое таинственное преобразование превращает квадратичную форму в разбиение плоскости бесконечным деревом, размеченное значениями формы. Мы проследим за свойствами этого преобразования в зависимости от того, может ли форма принимать значения разного знака. Будет рассказано о некоторых недавно решенных задачах на тему представления натуральных чисел квадратичными формами.
Олег Герман (мехмат МГУ) «Динамика на окружности. Начало.»
Теорема о трёх длинах, она же бывшая гипотеза Штейнгауза, утверждает следующее. Допустим, некто очень аккуратный начал разрезать круглый торт на сегменты равной угловой величины. Сделав один круг, этот некто, увлекшись, стал разрезать уже полученные сегменты торта, шагая с тем же шагом, что и раньше. Оказывается (и в этом и заключается теорема), в какой бы момент наш некто ни прекратил своё издевательство над тортом, будет не более трёх различных значений угловых размеров получившихся в итоге кусков.
Эту теорему можно доказывать самыми разными способами. Мы поговорим о методах, использующих аппарат цепных дробей, а также о самых простых методах линейной алгебры и теории решёток.
Сергей Олегович Горчинский (матфак ВШЭ) «Коники: геометрия, арифметика, алгебра»
Коники – это кривые на плоскости, заданные как нули многочлена второй степени от двух переменных. При изучении этого простейшего объекта встречаются различные идеи из алгебраической геометрии, арифметической геометрии и алгебры. Эти объекты можно классифицировать на вещественной или комплексной, обычной или проективной плоскости. При этом самый абстрактный случай, проективной комплексной плоскости, оказывается самым простым. Геометрия коник помогает находить пифагоровы тройки, также мы расскажем в этом контексте и о кривых старших степеней. Вопрос о существовании точек на кониках с рациональными координатами может быть решен при помощи рассмотрения p-адических чисел (теорема Минковского-Хассе), о которых будет также немного рассказано.
Алексей Драль (МФТИ) – «Небольшой рассказ про Большие данные»
Даниил Мусатов (ФИВТ МФТИ, Яндекс) «Вычислительные задачи поиска»
Во многих практических задачах мало узнать, что решение существует – надо его найти. Возникает вопрос: насколько сложнее может быть поиск нужного объекта по сравнению с доказательством его существования? Сложность можно измерять по-разному, мы сосредоточимся на времени работы алгоритма. Оказывается, ответ сильно зависит от задачи: в каких-то задачах алгоритм для поиска строится при помощи алгоритма для проверки существования и работает примерно такое же время. В других поиск может быть сложнее. Особенно интересны случаи, когда задача существования всегда тривиальна из-за какой-нибудь теоремы. Это может быть принцип Дирихле, лемма о рукопожатиях (число вершин нечётной степени чётно) или что-то ещё. На основе разных принципов возникают различные классы задач. В некоторых классах возникает большое количество полных, т.е. “самых сложных” задач. Особенно богат на них класс PPAD, связанный с теоремами о неподвижных точках. План мини-курса:
1. Вычислительные задачи и их сводимости друг к другу. Класс NP, NP-полнота.
2. Задачи поиска для NP-полных задач и для задачи об изоморфизме графов. Тотальные задачи поиска. Классы TFNP, PLS, PPA, PPAD, PPP и др.
3. Полные задачи в классе PPAD.
Роман Просанов (мехмат МГУ) «Многомерные многогранники»
Возьмём какой-нибудь многогранник (обычный, трёхмерный, к которым вы привыкли). Назовём комбинаторной структурой многогранника число его вершин, рёбер и граней; сколько рёбер содержит каждая грань; какие грани являются смежными; сколько рёбер исходит из каждой вершины и прочее. Два многогранника называются комбинаторно эквивалентными, если они имеют одну и ту же комбинаторную структуру (например, куб и любой параллелепипед комбинаторно эквивалентны).
Интересный вопрос: а для любого ли многогранника существует комбинаторно эквивалентный ему многогранник, все вершины которого имеют рациональные координаты? Казалось бы, мы можем достаточно свободно двигать вершины (хоть и с некоторыми ограничениями), сохраняя при этом комбинаторную структуру многогранника. Так что, вроде бы, достаточно естественно ожидать, что их всегда можно подвигать как-то так, чтобы они все стали рациональными, но комбинаторная структура не изменилась.
Оказывается, что для трёхмерного пространства это действительно так, но если рассмотреть аналоги многогранников в многомерных пространствах, то с интуицией такого рода надо быть осторожнее. На лекциях я расскажу, что такое многомерные многогранники, как их можно хоть немного представлять, и почему они могут обладать неожиданными свойствами. Основной целью курса будет доказательство того, что существует восьмимерный нерациональный многогранник.
Андрей Михайлович Райгородский (ФИВТ МФТИ, мехмат МГУ, Яндекс) «Хроматическое число случайного графа»
Алексей Савватеев (Университет Дмитрия Пожарского) «Школьная теория групп»
Я считаю, что теорию групп нужно изучать в средних классах – примерно тогда же, когда вводится символьное обозначение (буквы x,y,z и т.п.).
Потому что ступень абстракции, ведущая к общему понятию группы от систем остатков по данному модулю (с одной стороны) и перестановок (с другой), не выше, чем ступень абстракции от чисел 3,4,5 к символам.
Перестановки же легко понять и освоить уже во втором-третьем классе, точно так же, как и системы остатков по данному модулю (основанию).
В миникурсе я ликвидирую пробелы школьного образования, относящиеся к теории групп (и к конкретным примерам групп). Будут установлены базовые факты про вычеты, доказана малая теорема Ферма, исследованы подгруппы групп перестановок на трёх и четырёх символах, введено понятие нормальной подгруппы данной группы и простоты группы.
Если будет время, то мы далее докажем, что группа чётных перестановок на пяти символах – простая (что откроет желающим дорогу к изучению вопросов о разрешимости алгебраических уравнений в радикалах), теорему Шаля и др.
Данила Черкашин (матмех СПбГУ) «Раскраски гиперграфов»
Гиперграф – это пара (V, E), где V — это множество вершин, а E — множество ребер, каждое ребро e ∈ E состоит из произвольного количества вершин; n-однородный гиперграф (или просто n-граф) – это гиперграф, в котором любое ребро имеет размер n (то есть граф это 2-однородный гиперграф).
Мы будем изучать условия, при которых существуют хорошие раскраски множества. Под хорошей раскраской может подразумеваться одна из следующих раскрасок: раскраска в r цветов без одноцветных ребер; раскраска в r цветов, такая что в каждом ребре присуствуют все цвета; или раскраска в которой цветов примерно поровну.
Наша основная цель — понять при каком минимальном количестве ребер существует n-граф, не обладающий хорошей раскраской. К сожалению, при n > 5 узнать точный ответ не представляется возможным, поэтому мы поговорим о наилучших имеющихся оценках.
Михаил Ягудин (мехмат МГУ) «Оптимальная остановка»
Типичная задача наилучшего выбора — разборчивая невеста: невеста ищет себе жениха среди N претендентов. Она общается с кандидатами в случайном порядке, в результате общения невеста должна либо отказать ухажёру, либо принять его предложение. Цель — выбрать лучшего претендента.
Оптимальная стратегия следующая: отклонить 1/e ≈ 37% кандидатов, а затем выбрать первого, кто будет лучше всех предыдущих.
Этот результат легко интерпретировать: если вам 16 и до 40 лет вы хотите связать себя узами брака, то следующие 8 лет следует потратить на поиск «принцессы на белом коне», а потом без раздумий предложить руку и сердце той, кто будет лучше предыдущих.
В рамках курса поговорим о:
– задачах о вступительных взносах или как правильно парковаться;
– минимизации сожаления или как играть с «одноруким бандитом».
Но не будем обсуждать задачу о разборчивой невесте, чтобы получить зачёт, следует пересказать брошюру С. М. Гусейна-Заде «Разборчивая невеста».
[Разборчивая невеста]
math.ru/lib/files/pdf/mp-seria/book.25.pdf