Александр Тискин
– DPhil (Oxford)
– доцент факультета МКН СПбГУ
– Научные интересы: алгоритмы на строках, параллельные алгоритмы, комбинаторная оптимизация

Борис Золотов
– Аспирант МКН СПбГУ, преподаватель
– Научные интересы: алгоритмы на строках, структуры данных, вычислительная геометрия

Доклад будет посвящен классической задаче вычисления наибольшей общей подпоследовательности (Longest Common Subsequence, LCS) для пары строк, также известной в мире биоинформатики как задача выравнивания последовательностей (Sequence Alignment). Решение из учебника основано на методе динамического программирования и кажется единственно возможным. Мы увидим, что это не так: предварительно обобщив задачу, ее можно эффективно решить при помощи рекурсии, где «склеивание» подзадач производится при помощи на первый взгляд совершенно посторонней структуры — моноида Гекке или «липких кос», определяемого через тропическое матричное умножение и очень похожего на классическую группу кос. Такое решение представляет не только теоретический интерес, но и позволяет получить эффективные алгоритмы для сравнения сжатых строк без их декомпрессии, параллельного сравнения строк, а также решения некоторых практических задач биоинформатики. В последние годы появляется все больше приложений этого метода: приближенный поиск по образцу в режиме малого редакционного расстояния; сравнение динамических строк; сравнение периодических строк; локальное сравнение строк при помощи оракула. Мы опишем основные идеи некоторых из них.

Александр Нестеров
– Phd in Economics
– Заведующий Международной лабораторией теории игр и принятия решений
– Доцент департамента экономики ВШЭ Санкт-Петербург

Мы поговорим об основах теории игр для решения экономических задач: как предсказывать поведение агентов (людей, фирм) и как устраивать оптимальные правила их взаимодействий? Когда свободный рынок работает хорошо и когда совсем плохо? Когда свободный рынок будет саморазрушаться? Как это можно предотвратить? Как на рынке оказываются вредные посредники и как сделать это для них невыгодным? Как менялся рынок приёма в вузы в России, и какие перемены ждать в будущем?

Константин Сергеевич Яковлев, к.ф.-м.н., ведущий научный сотрудник ФИЦ ИУ РАН и AIRI, доцент ВШЭ, МФТИ, СПбГУ

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

Именно на этот весьма актуальный вопрос мы попытаемся ответить в этой лекции. Будут рассмотрены как централизованные методы планирования, опирающиеся на классические техники поиска путей на графах (такие как алгоритм эвристического поиска A*, например), так и децентрализованные подходы, которые активно используют последние достижения в области искусственного интеллекта (обучения с подкреплением, трансформеные нейросетевые модели и пр.).

Федор Писниченко
Доцент кафедры прикладной математики Федерального университета ABC (UFABC) в Бразилии с более чем 14-летним опытом преподавания. Моя специализация охватывает численную оптимизацию, методы оптимизации с ограничениями в виде дифференциальных уравнений (PDE-constrained) и высокопроизводительные вычисления. Мои исследования включают линейное и нелинейное программирование, оптимизацию без использования производных и численные методы для решения дифференциальных уравнений, с применением в обработке сейсмических данных и разработке решений для задач в реальном времени. Сотрудник Chebyshev Research Center.

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

Курс состоит из 7 лекций и предназначен для студентов старших курсов, аспирантов и начинающих учёных. Курс включает методы решения задач безусловной нелинейной оптимизации, имеющих решающее значение в нейронных сетях, предиктивном управлении (MPC), робототехнике, автономных системах, обработке сигналов, медицинской визуализации, компьютерном зрение и машинном обучении. По окончании курса вы получите глубокое понимание применения методов нелинейной оптимизации в решении реальных задач различных отраслей.

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

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

Курс охватит теоретические основы и практические методы:

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

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

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

1. Мысланты — Львов Алексей, Гайдай-Турлов Иван, Туревский Максим (15 баллов)
2. 239 14-1 — Давидюк Владимир, Коротченко Таисия, Бахарев Иван (13 баллов)
3. X — Згонник Илья, Кузнецов Роман, Ананьев Дмитрий (13 баллов)
4. Пщимаф Наверх — Шеховцов Александр, Мясников Константин, Захаров Георгий (12 баллов)
5. Репка — Васильев Иван, Кайбышев Арслан, Расторгуев Данила (12 баллов)
6. Fans of zabashta — Дмитриев Владислав, Коновалов Кирилл, Матвеев Андрей (12 баллов)
7. тюлень и два зайки — Лихачев Алексей, Смирнов Вадим, Хриптан Георгий (12 баллов)
8. Крутые бобры — Дрозин Александр, Лотников Алексей, Карпов Александр (12 баллов)
9. Комбиматорик, сатаналитик, погромист — Сапрунов Егор, Французов Церен, Югов Михаил (12 баллов)
10. Basis2d — Михайлов Леонид, Баранов Александр, Прозоров Павел (11 баллов)
11. 1.5 shirovlasika — Хисамутдинов Эльдар, Савинов Даниил, Мишуков Николай (11 баллов)
12. Трое в лодке, не считая собаки — Миргалимова Розалина, Нагибин Ярослав, Калинин Александр (11 баллов)