https://vk.com/video_ext.php?oid=-56385969&id=456239485&hd=2; Автоматическое дифференцирование или метод обратного распространения ошибки; 43:41; На уроке пойдёт речь об очень важной составляющей современного обучения глубоких нейронных сетей — методе обратного распространения ошибки. А именно, будет показано, как при весьма естественных предположениях о нейросети можно вычислять градиент (производные) целевой функции. В нашем случае — суммы квадратных невязок выходов сети и того, что она должна выдавать на заданных входах практически за то же время, что и вычисление самой функции. Вычисление градиента является ключевым местом в организации процедуры обучения посредством стохастического градиентного спуска.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239722&hash=54bd6f943a2a9294&hd=2; Алгоритм Дейкстры или как работают навигаторы?; 49:18; В лекции говорится о достаточно классическом сюжете — поиске кратчайшего пути на графе. Рассказывается об алгоритме Дейкстры.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239462&hd=2;Аукцион второй цены Викри; 20:54; В небольшом докладе пойдет речь о «справедливых» аукционах. То есть совместимых по стимулам (честные ставки — самые выгодные) и равновесных по Нэшу (никому из участников в одиночку не выгодно отклоняться от своей стратегии). Аукцион второй цены, предложенный в 60-е годы Викри (Нобелевская премия в 90-е), является как раз примером такого аукциона (в отличие от всем известного аукциона первой цены). Идея очень простая — все делают ставки, и товар отдается тому, кто сделал наибольшую ставку, но отдается не по той цене, что он сам готов заплатить, а по цене, которая вторая в «стакане», то есть следующая по величине.
Литература: Литвак Н., Райгородский А. Кому нужна математика? М.: МЦНМО, 2024. Савватеев А., Филатов А. Занимательная экономика. Теория экономических механизмов от, А до Я. Изд-во «АСТ», 2022.
https://vk.com/video_ext.php?oid=-56385969&id=456239521&hd=2; Быстрая арифметика; 41:16; Под элементарной операцией будем будем понимать сложение или умножение двух цифр от 0 до 9. Сколько таких операций будет нужно сделать, чтобы сложить два n-разрядных чисел? Ответ: приблизительно n. А сколько потребуется таких операций, чтобы посчитать произведение двух n-разрядных числа? Стандартное умножение «в столбик» дает приблизительно n2. Можно ли более эффективно осуществлять умножение? В лекции будет рассмотрен алгоритм Карацубы, предложенный в 1961 году, который породил целое направление исследований, финальной точкой в которых, по-видимому, будут алгоритмы работающие за n * log n элементарных операций. Также в лекции будет показано, что если есть алгоритм вычисляющий произведение двух чисел a*b за T элементарных операций, то можно построить алгоритм (и описано как именно это сделать), который вычисляет a/b за 5T элементарных операций. Примечательно, что оба алгоритма (Карацубы и алгоритм деления) достаточно просты и вполне доступны даже семиклассникам.
Литература: Математическая составляющая. Под ред. Н.Н. Андреева. etudes.ru
https://vk.com/video_ext.php?oid=-56385969&id=456239696&hd=2; Быстрое умножение матриц; 55:37; Что такое матрица? Как она связана с линейными преобразованиями пространства? Как и зачем умножают матрицы? И как это делать эффективно. На лекции мы поговорим об алгоритмах Винограда, Штрассена и даже познакомимся с таким понятием как тензорный ранг.
https://vk.com/video_ext.php?oid=-56385969&id=456239554&hd=2;Вероятность вокруг нас; 01:04:51; Парадокс раздела ставки. Игра в теннис с родителями. Парадокс Бертрана (бросание случайной хорды на окружности). Задача о встрече. Парадокс дней рождений. Оценка длины отрезка по выборке из равномерного распределения. Решение функциональных уравнений вида $x (n+1) — x (n) = n$.
Литература: Секей Г. Парадоксы в теории вероятностей и математической статистике. Москва-Ижевск, РХД, 2003.
https://vk.com/video_ext.php?oid=-56385969&id=456239701&hd=2;Избранные математические этюды;59:47;В лекции рассказывается о трёх сюжетах из проекта «Математические этюды» etudes.ru. Первый сюжет связан со спутниковой навигацией, второй — с тем, какие бывают правильные многогранники (формула Эйлера), в частности, можно ли склеить футбольный мяч из правильных шестиугольников, третий — с самоподобием и книгопечатанием и связью с цепными (подходящими) дробями.
https://vk.com/video_ext.php?oid=-56385969&id=456239704&hd=2;Интуиция как источник парадоксов;49:06;В лекции, следуя книге Валерия Босса «Лекции по математике. Т. 12: Контрпримеры и парадоксы», рассматривается несколько простых математических сюжетов, в которых интуиция может подводить. Первый сюжет связан с верёвкой, опоясывающей земной шар по экватору. Если её удлинить на 10 метров, насколько такая верёвка поднимется над Землёй? Оказывается, больше чем на 1,5 метра. Второй сюжет — о том, сколько оборотов сделает колесо, прокатившись по неподвижному колесу такого же радиуса. Ответ, вызывающий частое удивление, — два оборота. Третий сюжет связан с принципом неподвижной точки и показывает важность математической формализации постановки. Четвёртый — с масштабированием географических карт. В завершение рассматривается классическая задача из книги Якова Перельмана «Занимательная физика» о движении парусника против ветра.
https://vk.com/video_ext.php?oid=-56385969&id=456239694&hd=2; Как бороться с пробками?; 56:22; Что такое равновесие и почему многие крупные мегаполисы типично живут с пробками? Как с этим бороться? Чем отличается равновесие от социального оптимума и как сделать так, чтобы равновесие стало социальным оптимумом? Мы рассмотрим простейшие примеры поиска равновесий в транспортных сетях, а в конце обсудим, как можно бороться с пробками (на примере платных дорог и улучшения ситуации с общественным транспортом)?
https://vk.com/video_ext.php?oid=-56385969&id=456239659&hd=2;Коллективная ответственность;37:57;В лекции пойдет речь о том, как с помощью экономических механизмов можно бороться с безбилетниками в электричках и налоговыми неплатежами. Будут рассмотрены конкретные примеры. Литература: Савватеев А., Филатов А. Занимательная экономика. Теория экономических механизмов от А до Я. – Litres, 2022.
https://vk.com/video_ext.php?oid=-56385969&id=456239703&hd=2;Конечно-разностные линейные уравнения и комплексные числа;32:45;В лекции рассматривается конечно-разностное уравнение вида a_{n+1} = 2 a_n - 2 a_{n-1}. Его решение предлагается искать в виде a_n = const x^n. Подставляя в исходное уравнение и упрощая то, что получается, приходим к квадратному уравнению x^2 = 2x - 2. Данное уравнение не имеет действительных корней, зато имеет два комплексных корня x = 1 + i, x = 1 - i, где i^2 = 1. Общее решение может быть записано в виде a_n = С_1 (1 + i)^n + C_2 (1 - i)^n, где С_1 и С_2 — произвольные константы. Если задать a_0 = a_1 = 1, то C_1 = C_2 = 1/2, в итоге a_n = 1/2 (1 + i)^n + 1/2 (1 - i)^n. Получилось, что для вычисления a_n требуется использовать комплексные числа. Используя соотношение Эйлера, которое объяснено на лекции, e^{i \phi} = cos \phi + i sin \phi, можно получить, что a_n = 2^{n/2} cos (\pi n/4).
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239466&hd=2;Конфликты с точки зрения теории игр. Повторяющиеся игры. Вопросы репутации; 46:03; Классическим примером матричной игры является дилемма заключенного. Особенностью конкретной этой игры является ситуация, в которой равновесие по Нэшу (ни одному из двух игроков не выгодно отклоняться от используемой стратегии "не кооперировать") не эффективно (оптимально) по Парето. То есть можно указать каждому из игроков как действовать (в данном случае использовать стратегию "кооперировать") и выигрыш у каждого станет больше. Но на практике реализуется именно равновесие Нэша. Этот простой пример объясняет природу многих конфликтов. В этой небольшой лекции обсуждается как можно было бы все же вернуть ситуацию в социальный оптимум (использованию обоими игроками стратегии "кооперировать"). Для этого рассматривается повторяющийся вариант игры "Дилемма заключенного", с некоторой вероятностью продолжения игры после каждого нового розыгрыша. В таком случае быть "эгоистом" может быть невыгодно, если против тебя, например, играют стратегию "вечной кары" (эта стратегия выглядит очень просто: кооперироваться до тех пор пока оппонент не выбрал стратегию "не кооперироваться", после этого во всех оставшихся розыгрышах используется стратегия также "не кооперироваться" независимо от того, что делает оппонент). Собственно, исследуется вопрос о том, когда стратегия "вечной кары" будет равновесием по Нэшу у обоих игроков (эта стратегия приводит к кооперации). Обсуждаются в связи с вышесказанным вопросы репутации и почему в малых городах, как правило, практически нет правонарушений...
Литература: Пейдж С. Модельное мышление. Изд-во "МИФ", 2020.
https://vk.com/video_ext.php?oid=-56385969&id=456239664&hd=2; Метод главных компонент и ИИ; 50:42; Кратко разберём идею автоэнкодера в ИИ и понятие эмбеддинга. На примере метода главных компонент — с геометрической интуицией и схемой их получения — эти концепции будут продемонстрированы в линейном случае. Литература Гудфеллоу Я., Бенджио И., Курвиль А. Глубокое обучение. Изд-во ДМК, 2017.
https://vk.com/video_ext.php?oid=-56385969&id=456239555&hd=2; Основные принципы оптимизации; 33:27; В лекции рассказано о двух базовых принципах оптимизации: принципе Ферма и принципе Лагаранжа. Принцип Ферма состоит в том, что если минимум функции достигается внутри области, в которой решается задача и функция гладкая, то производная (градиент) должна равняться нулю в точке минимума. Принцип Лагранжа состоит в том, что для задачи с ограничениями, принцип Ферма применяется к функции Лагаранжа, минимум которой совпадает с минимумом исходной функции. Функция Лагранжа получается добавлением к исходной функции ограничений, умноженных на множители Лагранжа. Для поиска множителей Лагранжа предлагается использовать условия дополняющей нежесткости. Оба принципа неформально выводятся. Принцип Ферма демонстрируется примером отражения света от зеркальной поверхности. Также рассматривается пример построения сети Штейнера для вершин квадрата, как пример более сложной задачи, которую не так просто подогнать под возможность применения перечисленных двух принципов.
Литература: Тихомиров В.М. Рассказы о максимумах и минимумах. М.: МЦНМО, 2017.
https://vk.ru/video_ext.php?oid=-56385969&id=456239698&hd=2; Парадокс Пигу-Найта-Доунса
; 34:28; В лекции рассказывается об экономических предполсылках известной фразы: «хотели как лучше, а получилось как всегда». А именно, будет рассмотрен конкретный естественный пример простой транспортной сети сначала с двумя альтернативными дорогами, соединяющими два пункта. Одна из дорог объездная широкая, длинная, вторая узкая, но короткая. Будет показано, что расширение узкой дороги может не приводить к тому, что водители станут быстрее добираться, более того, если построить еще и метро (и появляется третья альтернатива), соединяющее пункты, то может так сложиться, что расширение второй дороги даже ухудшит для всех ситуацию.Также мы поговорим о том как подружить в классе всех мальчиков и девочек, чтобы никому не хотелось поменять друга.
Литература: Савватеев А., Филатов А. Занимательная экономика. АСТ, 2022.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239461&hd=2;Парадокс Симпсона, групповой отбор и процветание альтруистов; 15:47; В лекции говорится о роли группового отбора на примере парадокса Симпсона. Суть парадокса в том, что если общество состоит из нескольких групп, в каждой группе есть некоторое количество альтруистов и эгоистов, то со временем процент альтруистов может вырасти, что вроде как противоречит тому, что в каждой отдельной группе количество альтруистов уменьшается (внутригрупповую борьбу выигрывают эгоисты). Как такое может быть? Ответ довольно прост: те группы, в которых альтруистов больше, более успешны и увеличивают в процентом отношении свое присутствие в обществе. При должном подборе чисел можно получить описанные парадоксы. Парадокс несет большой философский смысл и представляется весьма полезным не только как упражнение по элементарной математике.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239484&hd=2;Парадоксы теории вероятностей; 38:54; В современных школах курс теории вероятностей читается с 7 класса. И уже в 7 классе можно столкнуться с достаточно странными парадоксами… Например, возьмем три одинаковых картонки. На первой с обеих сторон нарисуем букву А, на второй букву Б, а на третьей картонке с одной стороны нарисуем А, с другой Б. Положим картонки в мешок. Затем одну выложим наугад и положим на стол. Предположим, что на видимой стороне картонки изображена буква А. Какова вероятность того, что на другой стороне тоже А? Казалось бы ответ ½. Но на самом деле, 2/3. В рамках урока мы познакомимся еще с несколькими парадоксами, которые позволяет лучше прочувствовать, важность четкого понимания (формализации) условий задачи.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239483&hd=2;П-теорема в физике и математике; 52:30; Рассмотрим задачу определить период колебания математического маятника T (в секундах) с длинной L (метров) и массой m (кг). Маятник находится в поле силы тяжести, характеризуемой ускорением свободного падения g (метры/секунды^2). Оказывается, совсем не сложно понять, что T ~ \sqrt{L/g}. Получается это из соображений размерности. Никак по-другому из L, m, g не получится сконфигурировать физическую величину, имеющую физическую размерность секунды. Таким образом, с точностью до числового множителя можно получить правильную формулу. На самом деле, используемые выше соображения хороши известны как физикам, так и математикам. В лекции мы поговорим об общей схеме, которая называется Пи-теорема теории размерностей. Посмотрим, как с помощью такой теоремы можно решить задачу о перекрытии реки камнями и определить шаг в методе градиентного спуска (возникает, например, при обучении нейронных сетей). Также рассмотрим несколько ярких примеров применения соображений подобия и размерностей, чтобы ответить на вопросы: кто выше прыгает, быстрее плавает и бегает и т.п.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239731&hash=f26effacb46a6fd0&hd=2;Прогулки с физикой;36:29;В лекции вместе со школьниками мы отправляемся в путешествие, пытаясь объяснить с точки зрения элементарной физики то, что мы наблюдаем: росу на листочках утром, облака, зацепляющиеся за горы, круговорот воды в природе, почему есть день и ночь, лето и зима, почему в Якутске разница дневной и ночной температуры большая, а в Петербурге нет, почему большая разница температуры летом и зимой, почему в Гонконге в декабре светлое время суток существенно больше, чем в Казани, откуда текут реки и почему из озера обычно вытекает одна река и т.д.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239488&hd=2; Рекомендательные системы; 45:46; На уроке мы поговорим о матрицах, матричных разложениях, немного об оптимизации. Объединяющим элементом всех этих сюжетов будет задача о том, как рекомендовать новые фильмы зрителям, например, в онлайн-кинотеатре «Кинопоиск» или «Okko» на основе того, что они уже посмотрели и оценили.
https://vk.com/video_ext.php?oid=-56385969&id=456239661&hd=2;Реакция Вассермана или как правильная математическая модель эксперимента помогает существенно экономить время;32:26; Есть n испытуемых (n≫1), среди которых с вероятностью p=0,01 встречаются больные. Задача — выявить их с помощью анализа крови на антитела. Если тестировать всех по отдельности, понадобится n тестов. Но можно ли уменьшить это число? Ответ: да. Достаточно разбить всех на группы по 10 человек, смешать их пробы и сделать один тест на группу. Если результат отрицательный — идём дальше, если положительный — проверяем каждого в группе отдельно. Такой метод сокращает ожидаемое число тестов примерно в 5 раз. Но почему именно по 10 человек? Ответ кроется в довольно интересной математике, о которой и пойдёт речь. Литература Лагутин М. Б. Наглядная математическая статистика. Учебное пособие. – БИНОМ. Лаборатория знаний, 2012.
https://vk.com/video_ext.php?oid=-56385969&id=456239702&hd=2;Сила выбора из двух;55:45;В супермаркете имеется много очередей (серверов, обслуживающих заявки), имеющих в общем случае разную длину. Уследить за всеми одновременно невозможно. Поэтому рассматривается стратегия: выбрать очередь случайно и пойти в неё. Альтернативный вариант — выбрать две очереди случайно и пойти в ту, которая короче, — оказывается не просто лучше (что довольно очевидно), а существенно лучше. В лекции даётся математическое объяснение тому, почему это так, и рассказывается, как именно количественно измерить разницу в равновесном режиме функционирования супермаркета с огромным числом очередей. Сюжет взят из книги Нелли Литвак и Андрея Райгородского «Кому нужна математика».
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239486&hd=2;Счётчики с короткой памятью; 45:46; На уроке мы обсудим возможность в огромной таблице с большим числом повторяющихся записей посчитать количество разных записей. Например, посчитать клиентов банка. Каждая транзакция (запись в таблице) связана с конкретным клиентом, однако у одного клиента может быть много транзакций… Об эффективных методах решения такой задачи мы и поговорим.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239733&hash=2d918bda4335e2b0&hd=2;Схема регуляризации Тихонова;47:09;В лекции рассматривается система линейных уравнений $Ax = b$ с плохо обусловленной симметричной матрицей $A$. Если правая часть системы $b$ задана неточно, то плохая обусловленность может приводить к сколь угодно большой ошибке в решении $x$. Чтобы избежать этого, исходную систему уравнений, следуя А.Н. Тихонову, предлагается переписать в виде задачи квадратичной оптимизации $\min_x \|Ax - b\|_2^2$ и добавить также квадратичный регуляризатор $\min_x \|Ax - b\|_2^2 + \mu/2 \|x\|_2^2$. В условиях истокопредставимости (существует y: x = Ay) показывается, как за счёт правильного выбора параметра регуляризации $\mu$ можно добиться того, что неточность в правой части $\delta$ приводит к неточности порядка $\sqrt{\delta}$ в решении $x$. Отметим, что основным приёмом в получении этого результата является принцип Ферма (если минимум гладкой функции многих переменных достигается, то он достигается в точке, в которой все частные производные этой функции равны нулю), который применяется четырежды по ходу доказательства.
https://vk.com/video_ext.php?oid=-56385969&id=456239658&hd=2;Теорема Эрроу или почему так сложно сделать справедливую систему голосования в случае, когда кандидатов более двух; 40:25; Теорема Эрроу или почему так сложно сделать справедливую систему голосования в случае когда кандидатов более двух. В лекции обсуждается на примере нескольких парадоксов известная теорема Эрроу, которую иногда называют "правилом диктатора", говорящая о невозможности создания такой системы голосования (для трех и более кандидатов), которая бы удовлетворяла естественным аксиомам типа независимости и монотонности. Литература 1. В.Пахомов «Демократия с точки зрения математики» // «Квант», 1992, No10, с.2–6. 2. Алексей Савватеев, Александр Филатов, Максим Цветков О политике, футболе, коллективном выборе и однопиковых предпочтениях http://old.math.isu.ru/ru/chairs/me/files/filatov/2011_-_arrow.pdf
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239719&hash=a13f192b0772481c&hd=2;Теорема Гёделя и диофантовы уравнения; 57:06; В лекции обсуждается такая формулировка теоремы Гёделя (в форме Ю.В. Матиясевича): существует конкретный (который можно указать) полином P(x) = P(x_1,...,x_n) такой, что высказывание: «Уравнение P(x) - y = 0 неразрешимо по x (в целых положительных числах) при некоторых y (положительных целых)» истинно, но недоказуемо ни в какой непротиворечивой системе аксиом, содержащей примитивную арифметику.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239463&hd=2;Физика и география на горной прогулке (13 маршрут Красная поляна); 44:39; Многие факты школьных курсов географии и физики (термодинамики) можно рассказывать просто на прогулке. В нашем случае, на прогулке в горах. Начнем с географии. Во время такой прогулки можно показать и объяснить: откуда текут реки, почему реки типично сливаются, но не раздваиваются, как зарастают озера, почему типично, что из озера выпадает всего одна река, в то время как впадает много, почему в горах ночью холодно, а у моря нет. Аналогично по физике можно объяснить причину возникновения росы по утрам, ветра фен, облаков, созревания ягод на разных высотах, обсудить вопросы приготовления пищи на высоте и т.д. Собственно, прогуливаясь по 13 маршруту на гору Ачишхо в Красной поляне мы постараемся на школьном уровне ответить на эти вопросы.
https://vkvideo.ru/video_ext.php?oid=-56385969&id=456239468&hd=2;Цепные дроби. Золотое сечение. Предел последовательности. Неподвижная точка; 33:41; Что такое цепные дроби? В этой небольшой лекции будет рассмотрен конкретный пример цепной дроби (с основаниями 1), приводящей к золотому сечению. А именно, сначала будет выписано рекурентное уравнение, связывающее подходящие дроби, получающиеся если оборвать цепную дробь на шаге n и n+1. Затем, выписанное рекурентное соотношение: x_{n+1} = 1 / (1 + x_n) исследуется с точки зрения предела. Предполагая, что предел существует (на лекции поясняется что это значит) и равняется числу a больше 0 выписывается уравнение, которому должно удовлетворять число a: a = 1 / (1 + a). Это уравнение, в свою очередь, сводится к квадратному уравнению, которое впоследствие успешно решается и получается золотое сечение.
https://vk.com/video_ext.php?oid=-56385969&id=456239663&hd=2; Что такое антагонистическая игра и как в неë играть?; 48:55; В лекции вводится понятие смешанной стратегии, антагонистической игры и на примере конкретной игры двух лиц вычисляется равновесие Нэша в смешанных стратегиях. Также упоминается теорема фон Неймана о седловой точке. Литература Босс В. Лекции по математике. Контрпримеры и парадоксы. Т. 12. Книжный дом "Либроком", 2009.
https://vk.com/video_ext.php?oid=-56385969&id=456239662&hd=2;Электронная цифровая подпись и система RSA;53:15;В отличие от классических лекций о RSA, здесь фокус — на приложениях. В частности, кульминацией станет рассказ о том, как может быть устроен протокол электронного голосования. Литература Музыкантский А.И., Фурин В.В. Лекции по криптографии. М.: МЦНМО, 2013.