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

Алексей Яковлевич Белов-Канель (ФИВТ МФТИ, Bar-Ilan University, Shenzhen University) — «Тринадцатая проблема Гильберта и теория информации»

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

Тринадцатая проблема Гильберта утверждает:

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

Для алгебраических функций ответ неизвестен. Интересно, что хотя уравнение пятой степени не решается в радикалах, его можно свести к виду x^5-ax-1=0. Гильберт рассматривал тринадцатую проблему как своего рода обобщение проблемы разрешимости в радикалах.

Для класса разрывных функций это утверждение верно, для непрерывных функций — тоже верно (результат А.Н.Колмогорова и В.И.Арнольда), для гладких и бесконечно дифференцируемых функций есть контрпримеры, связанные с теорией информации. (Формула есть способ передачи информации).

Все эти вопросы предплагается обсудить.




Николай Владимирович Богачев (ФИВТ МФТИ) — «Калейдоскопы и группы отражений»

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

Описанный выше калейдоскоп двумерен, но, отбросив в сторону формальности, можно говорить и о многомерных калейдоскопах, и даже о неевклидовых, то есть на сфере и в пространствах Лобачевского. Все калейдоскопы на сфере и в евклидовых пространствах были найдены в 1934 году знаменитым британским математиком Г. Кокстером, и лишь спустя чуть более 30 лет Э.Б. Винбергу удалось построить эффективную теорию, позволяющую работать с калейдоскопами в пространствах Лобачевского. Я расскажу о том, как обстоят дела с поиском калейдоскопов в пространствах Лобачевского, и об открытых до сих пор проблемах 50-летней давности, связанных с ними.




Михаил Сергеевич Бурцев (ФПМИ МФТИ)

  1. Глубокое обучение — очередной подход к проблеме Искусственного Интеллекта. Нейросети, алгоритм обратного распространения ошибки. Сверточные и рекуррентные архитектуры нейросетей. Обучение с подкреплением.
  2. Разговорный искусственный интеллект. Современные методы создания интеллектуальных диалоговых систем.



Олег Николаевич Герман (мехмат МГУ) — «Вокруг третьей проблемы Гильберта»

В 1902 году Г.Э.Дьюдени обнаружил, что правильный треугольник разбивается на четыре части, из которых можно сложить квадрат. За пару лет до этого М.Ден доказал, что с тетраэдром и кубом такой фокус не пройдёт, решив таким образом третью гипотезу своего учителя Д.Гильберта. В рамках курса мы как следует поговорим о понятии «равносоставленности» и связанных с ним явлениях. В частности, мы поговорим об иррациональности и трансцендентности, об инварианте Дена для многогранников, о парадоксе Серпинского-Мазуркевича и, если останется достаточно времени, о восхитительном парадоксе Банаха-Тарского об удвоении шара.




Михаил Григорьев (ФИВТ МФТИ) — TBA




Антон Сергеевич Гусев (мехмат МГУ) — «Cops and robbers»

Полицейские и воры — это игра на графе. Пусть есть два игрока, один из которых играет за множество полицейских, а второй за единственного грабителя. Далее происходит пошаговая игра. Сначала каждый коп занимает по вершине графа, а затем то же самое проделывает вор. Далее они по очереди могут перемещаться по ребрам графа: сначала каждый полицейский перемещается в соседнюю по ребру вершину или остается на месте, затем коп, после чего все снова повторяется. Цель проста и понятна — полицейские должны поймать вора, то есть оказаться с ним в одной вершине. Вопрос состоит в том, какое минимальное количество полицейских необходимо, что бы гарантированно поймать вора.

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

Для освоения курса никаких предварительных знаний не требуется.




Максим Евгеньевич Жуковский (ФИВТ МФТИ) — «Описательная сложность задачи об изоморфизме»

Пусть H — некоторый граф. Каким образом можно формализовать графовое свойство «содержать подграф, изоморфный графу H»? И вообще говоря, что подразумевается под словом «свойство»? В так называемой теории моделей свойством принято называть множество графов, замкнутое относительно изоморфизма. Иными словами, два одинаковых (изоморфных) графа должны обладать свойством одновременно, т.е. не может так случиться, что один из них обладает свойством, а второй — нет. Например, свойство «содержать треугольник» — это множество всех графов, содержащих треугольник. Попробуем теперь это свойство формализовать. Сделать это можно следующим образом:
Это формула языка первого порядка. Разумеется, формула истинна на некотором графе тогда и только тогда, когда этот граф обладает рассматриваемым свойстве. Одним из основных параметров формулы первого порядка является кванторная глубина формулы. Известно, что истинность формулы первого порядка глубины k проверяется на n-вершинном графе за O(n^k). В этой связи возникает естественный вопрос: какова наименьшая кванторная глубина формулы, записывающей свойство «содержать подграф, изоморфный графу H»? Об этом и подобных вопросах и пойдет речь в нашем курсе.




Дмитрий Захаров (матфак ВШЭ) — «Задача о единичных расстояниях»

Пусть на плоскости нарисовано n точек. Каково наибольшее число u(n) единичных расстояний между парами этих точек? Эта задача была поставлена в 50-х годах Полем Эрдешем и, как ни странно, до сих пор открыта. Я расскажу о лучших известных оценках в этой задаче, получаемых с помощью полиномиального метода, открытого около десяти лет назад Гутом и Кацем.
Специальных знаний для понимания курса не требуется, однако желательно знать, что такое непрерывная функция, d-мерное пространство, и не впадать в истерику от слова многочлен.




Дмитрий Геннадьевич Ильинский (ФИВТ МФТИ, школа 179) — «Основная теорема арифметики и её приложения»

В курсе мы докажем основную теорему арифметики для натуральных чисел несколькими способами, обобщим её на большие множества чисел. Также мы поговорим про пифагоровы тройки, представимость числа в виде суммы двух квадратов, и про великую теорему Ферма при n=3.




Алексей Константинович Ковалев (НИУ ВШЭ, ФИЦ ИУ РАН) — «Искусственный интеллект: возможности и ограничения»

Искусственный интеллект – магические слова 21 века. О нём говорят все: и ученые, занимающиеся разработкой, и бизнесмены, использующие его в индустрии, и даже те, кто не имеет к нему никакого отношения. Одни предрекают технологическую сингулярность и скорое управление всех сфер человеческой жизни искусственным интеллектом. Другие полны скепсиса и снисходительно смотрят на такие заявления. На серии занятий мы постараемся разобраться, что же такое искусственный интеллект. Это то же самое, что машинное обучение или нечто большее? Рассмотрим ограничения и перспективы. Познакомимся с вариантами практического применения и подробнее разберемся в некоторых методах искусственного интеллекта.




Даниил Владимирович Мусатов (ФИВТ МФТИ) — «Колмогоровская сложность»

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




Андрей Михайлович Райгородский (ФИВТ МФТИ, мехмат МГУ, Яндекс) — «Системы представителей и задачи комбинаторной геометрии»

Возможно, некоторые знают замечательную историю о том, как накалывать сардельки на шампуры (задача о выборе представителей для команды на олимпиаду). Возможно, многие знают, как разрезать торты на куски (проблема Борсука) и как раскрашивать плоскость и пространство. На сей раз я не только напомню эти задачи, но и расскажу о том, как, оказывается, удивительным образом они между собою связаны. Наверное, хорошо бы не бояться n-мерного пространства:)




Алексей Владимирович Савватеев (Университет Дмитрия Пожарского, ФИВТ МФТИ) — «Доказательная геометрия»

На рубеже XVIII-XIX веков произошла «первая математическая революция» (вторая происходит на рубеже XX-XXI веков на наших с вами глазах). А именно, был решен целый ряд задач, стоявших с античных времён. Среди них: как найти общую формулу для корней уравнения пятой (и более высокой) степени; как построить с помощью циркуля и линейки куб, вдвое бОльший данного; как разделить данный угол на три равные части; и некоторые другие проблемы.

Общей характерной чертой полученных решений было то, что они содержали доказательства невозможности требуемого в задачах. На этом пути произошло становление науки, которую я бы назвал «доказательной геометрией». Речь идёт о сведении геометрических формулировок к задачам из области чистой алгебры, и затем, после наращивания «военной техники», прихода к противоречию с логикой изучаемых алгебраических конструкций.

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




Евгений Юрьевич Смирнов (матфак ВШЭ, НМУ) — «Квадратичный закон взаимности»

Общеизвестно, что с остатками по произвольному модулю m можно делать почти то же самое, что с целыми числами: их можно складывать, вычитать, умножать… а если m простое, то даже делить друг на друга и решать уравнения вида ax=b. Как и в привычном нам случае вещественных чисел, каждое такое уравнение будет иметь единственное решение.

А как обстоит дело с квадратными уравнениями? Как выяснить, есть ли решения у уравнения ax^2=b по модулю p ? Это мы и обсудим в нашем курсе. Главным утверждением, которое мы при этом докажем, будет квадратичный закон взаимности Гаусса — теорема, устанавливающая связь между разрешимостью уравнений x^2=p mod q и x^2=q mod p. Мы увидим, как с его помощью выяснять, разрешимо ли квадратичное уравнение по данному простому модулю.

Знакомство с арифметикой остатков является желательным, но не обязательным; все необходимые сведения я напомню на первой лекции.




Дмитрий Владимирович Щелчков (ФИВТ МФТИ) — «Криптография 101»

На этом курсе вы узнаете, как работают:

  • шифрование длинных текстов коротким паролем;
  • обмен ключами шифрования по открытому каналу;
  • Возможность написать любому человеку письмо, прочитать которое сможете только вы.

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

Курс вводный, для выполнения практических заданий (взлома различных схем шифрования) требуется владение языком программирования python.




Михаил Ильсурович Ягудин — «Вложенная агентность и вневременные решения»

Предположим, мы хотим сделать робота, который достигает наших целей в реальном мире. Целей достаточно сложных, чтобы ему пришлось учить самого себя и узнать многое про мир, что нам ещё неизвестно. Это сложная инженерная задача. Более того, есть также проблема, чтобы понять, что, вообще, означает создание такого робота? Что значит оптимизировать реалистичные цели в физической среде? Как это работает?

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

Цель курсы дать интуицию и определить несколько интересных объектов.