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

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

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

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

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

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

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

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

Задачи




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

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



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

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

Задачи




Михаил Григорьев (ФИВТ МФТИ) — «Combinatorial Nullstellensatz»

Известно, что n+1 уравнение вида P(a_i)=b_i, где P — неизвестный многочлен от одной переменной, всегда задает единственный многочлен степени не выше n. Для многочленов от нескольких переменных ситуация намного сложнее. Комбинаторная теорема Алона о нулях нетривиальный результат позволяющий улучшить наивные результаты о интерполяции многочленов от нескольких переменных.
Также рассмотрим неожиданные применения теоремы Алона в различных комбинаторных задачах.

Задачи




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

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

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

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




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

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

Задачи




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

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

Задачи 1

Задачи 2




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

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

Презентация




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

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




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

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

Задачи 1

Задачи 2




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

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

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

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

Задачи




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

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

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

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

Задачи

Записки лекций




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

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

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

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

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




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

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

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

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