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

Алексей Яковлевич Белов «Геометрия и комбинаторика определяющих соотношений»

Произведение элементов пишут в виде слова, изображаемого отрезком. А что значит умножить элементы по кругу? Какой смысл имеет мозаика, составленная из таких кругов? Понимание такого рода вещей приводит к решению ряда открытых вопросов. Например, допустим, мы хотим задать конечным числом соотношений полугруппу, в которой степень любого элемента равна нулю.

Конечным числом запрещенных подслов на прямой нельзя добиться того, чтобы были сколь угодно длинные слова без запрещенных подслов и в то же время не было таких периодических слов. В то же время на плоскости существуют конечные системы запретов, допускающие только апериодические замощения. Но как умножать с разных сторон? Эти и другие вопросы предполагается обсудить. Курс рассчитан на 4-5 лекций. Он основан на совместной деятельности с И.Ивановым-Погодаевым и И.Рипсом.


Владимир Брагин «Combinatorial Nullstellensatz»
Я расскажу о применении алгебраического метода, а именно многочленов от нескольких переменных, в задачах по комбинаторике. Задача о том, что из $2p-1$ целого числа можно выбрать $p$ чисел, сумма которых делится на $p$ (Теорема Эрдеша-Гинзбурга-Зива), очень легко решается этими идеями. И это только самый простой пример.

Основным инструментом послужит известная теорема, которая носит немецкое название combinatorial Nullstellensatz. Несложными следствиями из неё будут теоремы Коши-Дэвенпорта, теорема Шевалле-Варнинга и прочие.


Виталий Волк «Компьютерная лингвистика»
В современном мире все большее значение имеет автоматическая работа с текстами на разных языках – можно вспомнить, например, поиск в Яндексе и Google или автоматический голос Siri, встроенный в последние модели айфонов. К сожалению, оказывается, что для решения такого рода задач мало уметь программировать – хорошо бы понимать, какие бывают языки и как они устроены. В рамках курса планируется обсудить, что знает о языке современная наука и, главное, как эти знания используются в приложениях. Примерный список “прикладных” тем: устройство поисковых систем, машинный перевод, извлечение данных из больших объемов текста(=Data Mining), вопросно-ответные системы. Планируется, что слушатели к концу смогут сами что-то написать. Предварительных знаний, впрочем, не требуется.


Виталий Гольдштейн «Суффиксные структуры данных»
Нет, это не связано со школьными суффиксами, приставками и корнями слова. Это связано с тем, как быстро и эффективно искать подстроки в огромных текстах. Мы поговорим о том, как проверить школьников на списывание программ, а так же как быстро найти, сколько раз встречается подстрока “алгоритм” в произведениях Л. Н. Толстого.


Глеб Геннадьевич Гусев «Системы уравнений с единственным решением»
Каков вид у полиномиального уравнения, имеющего один корень? Линейный: $ax=b$. А каков должен быть вид у системы из $n$ полиномиальных уравнений от $n$ неизвестных, чтобы у нее было одно решение? На этой неделе мы доказали теорему, которая отвечает на этот вопрос в терминах многомерной комбинаторной геометрии — об этом я и буду рассказывать.

Доказательство использует известные и сравнительно новые факты из геометрии многогранников Ньютона и их смешанных объемов. Некоторые из них могут оказаться полезны для решения других (пока открытых) вопросов. Когда у системы уравнений ожидается 2 решения? А когда — 3? Предоставляю слушателям частично ответить на эти вопросы.


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

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

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


Андрей Владимирович Леонидов «Теория протекания для школьников»
Современные технологии нефтедобычи, распространение слухов, проводимость случайных электрических цепей, устойчивость сетевых структур по отношению к авариям и атакам, распространение эпидемий – вот неполный список задач, относящихся к «ведению» теории протекания. Для понимания лекций достаточно наличия интуитивных представлений о вероятности.


Даниил Владимирович Мусатов «Занимательная криптография»

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

Оказывается, такой сервер не нужен: можно построить протокол обмена сообщениями, устойчивый против жульничества. Современная криптография занимается построением подобных протоколов для различных ситуаций. Как нескольким серверам выбрать главный, даже если один-два могут сломаться? Как устроить электронные выборы, чтобы обеспечить и тайну голосования, и честность подсчёта голосов? Как построить систему электронных денег, защищённую от финансовых махинаций?

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


Виталий Павленко «Поглощающие марковские цепи»
Коробочка случайно выдаёт по букве из алфавита $\{A, B, C, D\}$, выписывая некоторую строку. Если коробочка когда-нибудь выпишет подслова “$AB$”, “$CABD$” или “$DBA$”, то она навсегда остановится и ничего больше печатать не будет. Какова ожидаемая длина строки, которую сгенерирует коробочка?
Чтобы решить эту задачу, нам надо будет составить автомат, который соответствует этому (поглощающему марковскому) процессу, и посчитать для него среднее время поглощения. Для подсчёта среднего времени поглощения мы познакомимся с матричным умножением, научимся искать обратную матрицу методом Гаусса, а также освоим такую идею, как линейность математического ожидания. Автомат, который в данной задаче строится — это просто автомат Ахо–Корасика, который является одним из эффективных подходов к задаче множественного поиска подстрок в тексте. Идею построения этого автомата я также расскажу, если будет достаточно слушателей, не знакомых с этим.
Несложный, но интересный анализ поглощающих марковских процессов находит применение в некоторых экономических исследованиях, о чём я также надеюсь упомянуть.


Юрий Притыкин «Алгоритмы сравнения последовательностей символов в биоинформатике»
Мы вспомним, какие последовательности символов возникают в биологии, и обсудим алгоритмы их сравнения. Для разных целей и вопросов требования к качеству и скорости таких алгоритмов могут различаться, как и само понятие качества, и мы попробуем рассмотреть хотя бы несколько примеров.


Юрий Притыкин «Алгоритмы анализа графов в биоинформатике»
Граф — это хорошая абстракция для многих типов данных, которые получают биологи, таких как сети белково-белковых взаимодействий, регуляторные геномные сети, физические и химические взаимодействия аминокислот внутри белка, и т. п. Мы рассмотрим несколько примеров алгоритмов, основанных на довольно простых идеях, которые тем не менее оказываются по существу и помогают лучше разобраться в реальных биологических данных.


Филипп Анатольевич Пушняков “Введение в теорию мажоризации”
В данном курсе будут изложены основы общего и универсального метода доказательства неравенств — теории мажоризации. Первые занятия будут посвящены неравенству Караматы и его приложениям (в том числе, решению задач с международных олимпиад). Далее планируется знакомство с неравенством Мюрхеда и его применениями. Если останется время, то планируется доказательство монгольского неравенства.


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

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


Алексей Владимирович Савватеев «Диофантовы уравнения»
Кронекер сказал: “Бог создал натуральные числа, всё остальное — дело рук человеческих”. Но всё, к чему прикоснулся человек, уже тронуто человеческою порчею. Натуральные числа – совершеннейший из объектов, с которыми мы имеем дело как в математике, так и в жизни вообще. Соотношения между ними удивительны и неожиданны, а уравнения, связывающие натуральные числа (которые называются диофантовыми уравнениями), как правило, очень сложны для решения, даже если выглядят на вид совсем тривиальными (достаточно вспомнить Великую теорему Ферма!). Также, если останется время, мы коснёмся вопроса приближения действительных чисел рациональными, и важными следствиями для трансцендентности знаменитых чисел $\pi$ и $e$.


Андрей Сандлер «Анализ и программирование игровых алгоритмов»

В течение курса предлагается придумать и реализовать на любом удобном языке программирования алгоритм для игры “Война вирусов“. По итогам занятий планируется провести турнир, в котором сразятся все алгоритмы, прошедшие проверку. Победители будут награждены памятными призами. Так как турнир подразумевает соревнование, то на занятиях планируется не разбирать какую-либо конкретную стратегию, а освещать общие вопросы теории алгоритмов, например, обход в ширину или поиск путей в графе, которые могут пригодиться при написании кода игры. Занятия также будут предусматривать проверку уже написанного кода проверяющей системой. Простые примеры игры на Pascal и Ruby можно взять здесь и здесь, технические правила изложены тут.
Если кто-то захочет писать код на языке, отличном от предложенных, просьба сообщить об этом на электронную почту andrei.sandler@phystech.edu, чтобы я добавил компилятор или интерпретатор этого языка в систему. Будет хорошо, если в школу вы приедете уже с некоторой работающей версией игры (можно посылать их мне на почту для проверки).


Дмитрий Валерьевич Трещев «Что такое динамические системы?»
В настоящее время теория динамических систем занимает в математике одно из ключевых мест наряду с традиционными разделами (алгебра, геометрия, анализ и др.) Она тесно связана с этими и другими областями математики, имеет истоки, мотивировки и приложения в физике, химии, биологии,экономике.

К сожалению, школьный курс математики практически не затрагивает вопросы теории динамических систем. Олимпиадные задачи, хотя и используют ряд идей из динамики, тоже не могут дать сколько-нибудь систематического представления об этой области.

Я попробую дать некоторое представление о предмете исследования, основных задачах и достижениях в этом разделе математики.


Данила Черкашин. “4СС и его друзья”

Посвящается Марии Ведерниковой

Содержание данного курса никак не связано с четырьмя сторонами света, суперэкономическими билдами за террана, и, более того, не проводится никаких параллелей с Балтоном. Речь пойдет о знаменитой проблеме четырех красок ( 4 Color Conjecture ), волнующей умы математиков с 1878 года (вообще говоря, поставили ее в 1852, но к математикам она попала не сразу). Пожалуй, это самая знаменитая задача теории графов.

На данный момент существует доказательство , являющееся чуть более чем полностью компьютерным перебором . Его мы никак касаться не будем. Также, например, кто-то считает (допустим-то, русскоязычная Вики), что теорема имеет и нормальное доказательство. К сожалению, это не так.
Но имеется множество интересных продвижений и всяческих связанных с
проблемой красивых теорем. О них мы и поговорим.

Курс доступен широкой публике – от зелёных школьников до А.Я.
Канель-Белова, которому, думаю, будет очень интересно содержание
последней лекции.

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

Примерный план занятий:
1. Очевидные утверждения. Раскраска в 5 цветов. Теорема Тейта.
2. Удаление разрезов размера не более 4.
3. Списочные раскраски графов. Теорема Томассена.
4. Алгебраический подход Матиясевича.
Большую часть материала можно найти по ссылке.

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


Владимир Златкович Шарич «Элементарные рекурренты»
В курсе будут рассмотрены классические специальные числа, удовлетворяющие рекуррентным соотношениям. Самые известные среди них – числа Фибоначчи, Каталана и Стирлинга. кроме этого, будут продемонстрированы некоторые методы работы (рассуждений) с такими числами.
Курс рассчитан на школьников, желающих усилить свою элементарную комбинаторную эрудицию. Он предполагается одним из простых курсов ликбезовского характера.