Николай Мальковский — кандидат физико-математических наук; Principal Engineer, Chebyshev Research Center

Range minimum query — это довольно известная академическая задача, она важна и на практике, но не сама по себе. Часто она используется как рутина в алгоритмах типа LZ, суффиксных деревьев или поисковых индексов. У задачи есть несколько вариаций. Основная суть в том, что дан массив чисел, и нужно на произвольном подотрезке индексов искать минимум. Самый простой пример того, где такая задача может возникнуть — запрос к базе данных вида «какая максимальная зарплата сотрудников в возрасте от 30 до 40 лет?».

На семинаре я расскажу про эффективное решение статической задачи, то есть, когда массив известен заранее и не изменяется, но запросы заранее неизвестны. Наиболее эффективное решение такой вариации — это разреженные таблицы, их проблема в том, что они требуют O(n log n) памяти и, соответственно, применимы для размеров максимум ~10^7. Существует много подходов, как за счёт чуть более медленных запросов добиться использования O(n) памяти, включая классический алгоритм Фараха-Колтона — Бендера. Существуют также и succinct подходы, которые требуют ~2.5n бит памяти, но скорость ответа на запросы на практике у них уже заметно хуже. На семинаре я расскажу, как взять лучшее из обоих миров: два варианта, каждый из которых сравним по скорости ответа на запросы с разреженной таблицей, но при этом
— Первый вариант требует 1.05n дополнительных бит, но при этом нужно иногда подглядывать в исходный массив;
— Второй вариант требует 2.1n дополнительных бит, но заглядывать в исходный массив не нужно.

Иван Самойленко — математик, младший научный сотрудник MIRAI и ВШЭ, аспирант МФТИ. В прошлом тимлид математиков в Wildberries (operational research)

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

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