Алексей Яковлевич Белов «Роботы в лабиринтах»
Виталий Гольдштейн «Алгоритмы вычисления выпуклой оболочки множества точек»
Глеб Гусев «Смешанные объемы: топологический взгляд на алгебру и геометрию»
Дмитрий Дагаев «Экспериментальная экономика»
Представьте, что Вы прогуливаетесь по улице со своим лучшим другом. Вдруг к Вам подходит один добрый человек и дарит 100 рублей. Затем он неожиданно просит Вас разделить эти 100 рублей с Вашим другом. При этом разрешается отдать товарищу любую сумму: от 0 до 100 рублей. Сколько денег Вы отдадите?
На первый взгляд описанная ситуация кажется нелепой. На самом деле экономисты с помощью такого эксперимента, получившего название «Dictator game», исследуют вопрос о распространенности альтруизма в обществе. С точки зрения классической экономической теории, опирающейся на предпосылку о рациональном поведении людей, человек, оказавшись на месте «диктатора» должен забрать все 100 рублей себе. Однако на практике люди предпочитают делиться некоторой незначительной суммой со своим другом. Получается, что люди нерациональны? Или человек получает определенную полезность от альтруистического поведения?
Экспериментальная экономика занимается проверкой гипотез, сформулированных экономистами-теоретиками с помощью формальных моделей. В данном курсе мы не только поговорим о некоторых известных экономических экспериментах, но и попробуем провести несколько небольших исследований.
Виталий Кошелев «Задача Эрдеша-Секереша о выпуклых многоугольниках на плоскости»
Сколько точек на плоскости будет достаточно, чтобы среди них всегда можно было найти выпуклый многоугольник на заданном числе вершин?
Этот вопрос был впервые поставлен 75 лет назад группой знаменитых венгерских математиков (и с этим связана отдельная красивая история). Простота постановки задачи привлекала очень большое количество исследователей, но тем не менее, до конца задача не решена до сих пор. Но за прошедшее время появилось очень много обобщений и близких задач. Я расскажу о текущих достижениях и, в том числе, о совсем новых результатах.
Даниил Мусатов «Арифметика игр»
Все мы привыкли проводить различные операции с числами: складывать, умножать, сравнивать и т.д. Оказывается, те же операции можно проводить и с играми.
Мы будем изучать комбинаторные игры, т.е. игры с правилами вида: “Двое ходят по очереди, проигрывает тот, кто не может сделать ход”. Мы научимся сопоставлять каждой такой игре (а точнее, позиции в ней) определённое значение, причём отнюдь не всегда это будет число. Мы познакомимся с такими значениями, как нимберсы, бесконечно малые, “горячие” числа и прочими, и научимся их складывать и сравнивать. Теория будет проиллюстрирована замечательными примерами, такими как хакенбуш, игры с кучами камней (ним и другие), чехарда на клетчатой бумаге, раскраска географической карты, заполнение доминошками шахматной доски и т.п. В качестве зачёта нужно будет посчитать значения для нескольких игр из этого списка (задания будут индивидуальными).
Рекомендуется взять ручки красного, синего и зелёного цветов.
Андрей Михайлович Райгородский «Системы представителей»
Денис Расковалов «Архитектура веб-поиска»
Михаил Абрамович Ройтберг «Языки. Графы. Автоматы»
Три понятия, вынесенные в заголовок, – ключевые для теоретической информатики (aka computer science). Ближе познакомиться с ними полезно и приятно.
В цикле из трех занятий будут представлены три этюда. Тема первого – конечные автоматы и связанные с ними графы, регулярные выражения и регулярные языки. Тема второго – задача поиска оптимального пути в ориентированном ациклическом графе и ее обобщения: кольца (это не циклы!), гиперграфы, немного физики. Тема третьего: контекстно-свободные языки и некоторые связанные с ними алгоритмические проблемы.
Примеры задач:
- Даны натуральные числа $М$, $k$ $(k < M)$. Множество чисел $\{x1, \ldots, x_t\}$ называется $k$-разложением числа $M$, если
1)$x_1 \leqslant k$; 2) $x_1 + \ldots + x_t=M$
Весом $k$-разложения называется произведение его элементов.
Найти сумму весов всех $k$-разложений числа М.
Далее некоторые слова могут быть непонятными) - Дано регулярное выражение. Построить минимальный автомат, который распознает соответствующий регулярный язык.
- Привести пример языка, который не является контекстно-свободным.
Предварительных знаний, выходящих за пределы средней школы, не требуется.
Алексей Владимирович Савватеев «Избранные сюжеты из теории игр»
Михаил Тихомиров «Эффективные вычисления»
Взяв ручку и листок бумаги, любой из вас без труда вычислит 10-е или 20-е число Фибоначчи. Вооружившись компьютером, можно автоматизировать процесс и дойти до миллионного или даже миллиардного номера. Однако можно ли за разумное время найти (хотя бы в каком-нибудь приближении) $10^18$-ый член последовательности?.. Оказывается, существует даже несколько способов это сделать, и в разных случаях разумнее использовать тот или иной из них.
Мы обсудим некоторые красивые вычислительные методы, которые позволяют за хорошее время решать большой круг задач из разных областей: комбинаторика, теория графов, геометрия, теория вероятностей и другие. Для закрепления материала лекций будут выдаваться задачи для самостоятельного решения (как чисто теоретические, так и алгоритмические). Знакомство с алгоритмами и опыт программирования желателен, но не обязателен.
Григорий Ривенович Челноков «Комбинаторика линейных неравенств»
В бензоколонках на кольцевой автодороге длинной 100 км бензина в сумме хватит на то, чтобы проехать 100 км. Тогда начав с некоторой бензоколонки машина с пустым баком сможет проехать полный круг. Докажите, что из 30 бутербродов с колбасой умный жадина всегда сможет выбрать 12 так, чтобы получить хотя бы по одной трети всего хлеба, масла и колбасы.
Докажите, что вершинам полного ориентированного графа можно так приписать неотрицательные числа с суммой 2, что для каждой вершины сумма чисел в ней и во всех, куда из нее ведут стрелкит будет не меньше 1.
Данный курс посвещен задачам, условия которых “хорошо” формулируются на языке линейных неравенств, методам их решения и полезным теоремам. Курс расчитан на слушателей с олимпиадной подготовкой, привыкших решать задачи самостоятельно, однако не требует сколь-нибудь серьезного теоретического багажа. На примере разбираемых задач будет особенно ясно, насколько условна грань между задачами математических олимпиад и задачами современной математики.