Анонсы курсов

Сергей Анисов «Если б я был султан…»

Задача Д. Флааса: все женщины Земли линейно упорядочены по уму, доброте и красоте.
Из двух женщин лучше та, которая превосходит соперницу хотя бы по двум параметрам.
Докажите, что можно выбрать трёх женщин так, что любая другая будет проигрывать
в сравнении с кем-то из трёх избранных.

Курс будет посвящён задачам о выборе по нескольким параметрам.
Помимо задачи Флааса, мы разберём теоремы Эрроу и Дасгупты-Маскина о процедурах голосования.
Если останется время, поговорим о статье “Dominating sets in k-majority tournaments” by N.Alon, G.Brightwell, H.Kierstead, A.Kostochka, and P.Winkler), простейшим частным случаем которой и является задача Флааса.


Алексей Яковлевич Белов «Комбинаторика слов»


Глеб Геннадьевич Гусев «Топология — математика в трех лицах: алгебра, геометрия, комбинаторика

Теоретически курс будет посвящен топологии алгебраических поверхностей и многомерных пространств. На практике мы рассмотрим несколько задач и теорем, некоторые из них являются классическими сюжетами, а некоторые – гипотезами и проблемами. В частности, я расскажу о том, как решения системы алгебраических уравнений связаны с вопросами комбинаторной и выпуклой геометрии.

Для понимания курса важно знать о существовании поля комплексных чисел и желательно понимать, что такое многомерное пространство.


Александр Дайняк «”Быстрые” схемы, “сложные” функции и другие понятия теоретической кибернетики»
Современные процессоры состоят из сотен миллионов транзисторов. Каждый транзистор выполняет очень простую операцию, но, комбинируя транзисторы, можно строить сколь угодно нетривиальные схемы. Мы отвлечёмся от физических явлений, который происходят в транзисторах, и займёмся логическим моделированием схем. В курсе будет рассказано о том,

…как из простейших логических элементов строить эффективные схемы для арифметических операций,
…что “почти все” логические операции очень сложные (не могут быть реализованы маленькими схемами),
…как строить почти оптимальные схемы для произвольных операций,
…как доказывать, что построенная схема оптимальна, то есть схему с меньшим числом элементов для той же операции построить не удастся.


Наталья Зевахина, Юрий Саватеев «Формальные грамматики и их лингвистические приложения»

В нашем курсе мы будем рассматривать различные способы задания формальных (т.е. искусственных) языков и описания синтаксиса естественных (т.е. на которых говорят люди) языков. Более подробно мы будем изучать так называемые контекстно-свободные грамматики и категориальные грамматики, основанные на исчислении И. Ламбека.
Курс будет состоять из двух частей — математической и лингвистической.

С точки зрения математики, мы будем изучать, как задавать формальные языки с помощью грамматик Ламбека и какими свойствами эти грамматики обладают. Кроме того, мы докажем, что, несмотря на то, что порождающая способность контекстно-свободной грамматики и грамматики Ламбека совпадает (если язык можно задать контекстно-свободной грамматикой, то его можно задать также грамматикой Ламбека, и наоборот), эти два подхода задают языки “по-разному”.

С точки зрения лингвистики, мы покажем, что грамматики Ламбека являются эффективным инструментом для анализа различных грамматических явлений естественных языков. Мы также будем моделировать синтаксические структуры естественных предложений.

Курс рассчитан на четыре занятия.


Виталий Кошелев «Задача Эрдеша-Секереша о выпуклых многоугольниках на плоскости»

Сколько точек на плоскости будет достаточно, чтобы среди них всегда можно было найти выпуклый многоугольник на заданном числе вершин?

Этот вопрос был впервые поставлен 75 лет назад группой знаменитых венгерских математиков
(и с этим связана отдельная красивая история). Простота постановки задачи привлекала очень большое количество исследователей, но тем не менее, до конца задача не решена до сих пор.
Но за прошедшее время появилось очень много обобщений и близких задач.

Я расскажу о текущих достижениях и, в том числе, о совсем новых результатах


Аким Сергеевич Кумок «Структуры данных»

Все мы хотим писать быстрые и эффективные программы. А эффективность программы на 80% зависит от того, как мы храним данные в компьютере. Например, если мы хотим искать числа в массиве из $N$ элементов, то мы можем каждый раз просматривать весь массив за $N$ операций, а можем отсортировать его и искать числа двоичным поиском за $\log N$ действий. На спецкурсе будут изучаться как классические структуры данных – куча, AVL-дерево и прочие, так и новейшие разработки в этой области – r-AVL trees, Rank-pairing heaps, Self-adjusting trees и другие.


Андрей Михайлович Райгородский «Линейная алгебра и комбинаторная геометрия»


Александр Александрович Разборов «P и NP»

При дворе короля Артура имеются $n$ рыцарей и $n$ прекрасных дам; про каждую пару известно, симпатичны они друг другу или нет. Можно ли их всех переженить так, чтобы в каждой паре жених и невеста были симпатичны друг другу?

А можно ли их всех рассадить за Круглым Столом так, чтобы симпатичными друг другу оказались все соседи?

Похожи ли эти две задачи? На первый взгляд очень. Оказывается, однако, что с вычислительной точки зрения разница между ними огромна. Для первой задачи имеется эффективный (по научному “полиномиальный”) алгоритм, а для второй без помощи Мерлина, похоже, не обойтись. Доказывать последний факт мы не умеем, но стройная и красивая теория NP-полноты позволяет привести хотя и косвенные, но весьма убедительные аргументы в его пользу. Именно этой теории, позволяющей успешно расклассифицировать необьятное море алгоритмических задач на простые и “предположительно трудные” и посвящён наш курс.


Денис Расковалов

1. «Как работает ранжирование Яндекса?
Языковые модели: база для предсказания релевантности»

На первой части лекции будет рассказано, как работает ранжирование Яндекса, как измерять качество поиска, зачем нужно машинное обучение, за счет чего машина может отвечать на вопросы живых людей. Будет рассказано про то, как знание об устройстве языка, его модель, может быть использована для лучшего понимания машиной человека, а, значит, для улучшения качества поиска.

2. «Пользовательские данные. Как миллионы пользователей помогают друг другу?»

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


Михаил Абрамович Ройтберг «Конечное и бесконечное. Разностные уравнения»

В математике приходится иметь дело с бесконечными объектами. Простейший пример таких объектов — последовательности.
В курсе будут рассмотрены разностные уравнения — уравнения, решениями которых являются последовательности.
Один из первых в истории примеров таких уравнений – уравнение для последовательности чисел Фибоначчи.
Разностные уравнения достаточно просты, чтобы с ними, в основном, можно было разобраться в коротком курсе. А, с другой стороны, на примере разностных уравнений можно познакомиться с важными свойствами дифференциальных уравнений.

Примеры задач, которые имеют отношение к курсу:

1. (для ее решения ходить на курс не нужно 🙂 ) Найти геометрическую прогрессию $\{z_n\}$,
все члены которой при $n > 2$ удовлетворяют уравнению $z_n = 5z_{n-1} – 6z_{n-2}$

2. Последовательность $\{z_n\}$ всеx $n > 3$ удовлетворяет уравнению $6 z_n – 11 z_{n-1} + 6 z_{n-2}– z_{n-3}= 0$, при этом $z_1 = 15; z_2 = 7; z_3 = 4.$ Вычислить $z_{1000}$ с точностью до 27-го знака.

3. Написать общую формулу для n-го члена всех последовательностей {zn}, удовлетворяющих уравнению $z_n – z_{n-1} – z_{n-2} + z_{n-3} = 0$


Алексей Владимирович Савватеев «Четвёртое, и последнее, дно тройной дуэли»

Стреляются трое. Один бьёт наверняка, другой попадает в среднем 4 раза из пяти, третий — через раз. Стреляются по очереди, в строго оговоренном порядке, пока двое не погибнут. Единственный выживший получает Принцессу. Какие шансы на победу у каждого из них?

На первый взгляд кажется, что задачка эта не очень сложная — так, “на полчасика прикинуть”. Чёрта с два! Не верите — сами попробуйте!

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

У этой задачи очень длинная предыстория. “Окончательно верное” решение, как нам кажется, было получено нами в 2010 году — но кто знает, может и мы ошиблись? Придите и проверьте нас!


Владимир Шарич «Основная теорема алгебры комплексных чисел»

Любой многочлен с комплексными коэффициентами имеет комплексный корень.
Согласно источникам, математики начали догадываться об этом в 17 веке;
доказывали в 18 и окончательно доказали в 19 веке с изобретением аппарата матанализа.
Лекция будет посвящена обзору истории развития вопроса и некоторых известных доказательств:

1) самое короткое доказательство

2) доказательство методом крайнего

3) доказательство дамой с собачкой

4) доказательство расширениями полей.

Правдоподобные факты, за которыми стоят совершенно необходимые для полноты нудные рассуждения, будут использоваться без строгого обоснования.