Николай Мальковский — кандидат физико-математических наук; 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-агенты.

Николай Полярный. CTO Agisoft. Автор курса фотограмметрии и курса алгоритмов на видеокартах.
Борис Симиютин. Старший разработчик, Agisoft. Соавтор курса фотограмметрии и курса алгоритмов на видеокартах.

Процессор и видеокарта — в чём между ними разница? Если видеокарты так хороши — зачем нужен процессор? Чем отличаются OpenCL, CUDA и Vulkan? Что и когда выбрать для задачи? Как выглядят алгоритмы на видеокартах?

Обсудим, что такое вычисления в модели массового параллелизма. Что такое hyper-threading, occupancy, code divergence, coalesced memory access? Какие алгоритмы выигрывают от использования видеокарт?

Рассмотрим на примерах:
– merge-sort* за O(N)O(N)1​1
​​ вместо O(N⋅logN)O(N⋅logN),
– умножение матриц,
– real-time построение BVH-дерева (из этого вырос современный Ray Tracing).

Обсудим, как, понимая архитектуру компьютера хотя бы в общих чертах, можно оценить потенциал для ускорения с помощью разных методов оптимизации — даже без профилировщика.

Лекция будет сопровождаться кодом — с ним можно будет экспериментировать и после лекции. Также на лекции будут карлики и клоуны!

*
​​ merge-sort за O(N)O(N) — на видеокарте он, конечно, не работает строго за линию, но всё равно быстрее, чем на процессоре, в квинвигинтиллион**
​​ раз.

**
​​ В 123.9 раз.

– умение писать простой C++-код на уровне работы с арифметикой указателей
– понимание асимптотического анализа, базовых алгоритмов и структур данных
– базовые знания многопоточности
– для выполнения заданий достаточно любого ноутбука (видеокарта не требуется, можно тестировать на процессоре)
– для выполнения заданий рекомендуется Ubuntu или Windows, на MacOS потребуются дополнительные усилия

Даниил Орешников
Backend-разработчик в SourceCraft (Yandex), преподаватель курса алгоритмов и структур данных в ИТМО. Призер финалов школьных всероссийских олимпиад по математике и по программированию, NCUMC, MathOpen; координатор/проблемсеттер олимпиад по программированию для школьников.

Git для большинства — привычный набор команд: commit, merge, push, pull. Но за ними стоит достаточно сложная распределённая система с content-addressable storage, алгоритмами и протоколами обмена данными. Как связаны commit и «патчи» из изменений в коде? Как Git находит общее начало двух веток? Когда изменения можно объединить автоматически, а когда Git честно отказывается угадывать смысл результата? Как клиент и сервер определяют, какие объекты уже известны обеим сторонам, не передавая полную историю?

На курсе мы будем последовательно строить ответы на эти инженерные вопросы, чтобы чёрный ящик под названием Git стал немного прозрачнее. Разберём physical storage: packfiles, .idx, delta compression; посмотрим на используемые алгоритмы и структуры данных: object graph, обход commit DAG и поиск merge base; diff-алгоритмы семейства Myers, а также patience и histogram heuristics; three-way merge и устройство conflict state в index. Увидим, как Git приходит к компромиссам между компактностью и стоимостью чтения, обсудим протокол negotiation между клиентом и сервером через want/have, а также оптимизации и механизмы, которые делают Git применимым к большим репозиториям: commit-graph, Bloom filters, reachability bitmaps, partial clone.

Сквозной проект курса — создание собственного минимального Git-сервера, совместимого с настоящим клиентом Git для clone и fetch. Мы начнём с чтения объектов и refs, затем реализуем базовый протокол, discovery capabilities, negotiation общей истории и генерацию packfile.

– хотя бы раз в жизни пользовались Git'ом
– знание основ алгоритмов и структур данных (графы, хеш-таблицы)

Данил Сагунов
Координатор CS Space. Научный сотрудник ИТМО, МКН СПбГУ. Финалист ICPC 2016. Личная страница: danilka.pro

Задачи о длинном пути (Longest Path), независимом множестве (Independent Set) или раскраске графа в минимальное число цветов (Chromatic Number) — примеры известных NP-трудных задач. Но что именно делает их такими трудными? Ведь найти самый длинный путь в дереве, найти максимальное независимое множество в двудольном графе или раскрасить набор отрезков на прямой так, чтобы одноцветные отрезки не пересекались — можно эффективно за полиномиальное время, как нам известно из классических курсов алгоритмов.

В этом курсе мы изучим множество параметров, описывающих структуру графа. Базовый смысл каждого отдельного параметра — чем больше параметр, тем сложнее структура графа. Параметры могут быть совершенно разнообразными, от, например, средней степени графа, до его древесной ширины (treewidth). Мы исследуем, как эти параметры взаимосвязаны между собой, как их можно эффективно вычислить, а самое главное — как они помогают разработать эффективные алгоритмы для задач, которые вычислительно сложны в общем случае.

Студенты научатся использовать структурные параметры графа как инструмент — превращать наблюдения о структуре в конкретные алгоритмические техники (динамическое программирование по древесной декомпозиции, ILP, ветвление, кернелизация и другие). Отдельным увлекательным элементом курса станет построение общей карты изученных параметров — иерархического графа, отражающего, какие параметры ограничивают друг друга, а какие из них несравнимы, и как устроен весь ландшафт "структурной сложности" целиком.

Без них будет трудновато:
– базовые понятия теории графов
– стандартные алгоритмы

Могут пригодиться:
– основы вычислительной сложности
– параметризованные алгоритмы

Дмитрий Булычев
К.ф-м.н., с.н.с. междициплинарной лаборатории им. Чебышёва, руководитель магистратуры «Разработка ПО и науки о данных» МКН СПбГУ. Область научных интересов — языки и инструменты программирования, функциональное, логическое и реляционное программирование.

Когда мы пишем программы, мы не оперируем элементарными терминами языка программирования, подобно тому, как, говоря на родном языке, мы не размышляем в терминах синтаксиса и морфологии. Человеческое мышление мнемонично, оно действует в терминах абстракций и идиом. Такой способ рассуждений хорошо работает при создании прикладных программ, однако даёт странные и иногда необъяснимые результаты при реализации языковых инструментов, то есть программ, которые получают на вход одни программы и возвращают другие (компиляторов, интерпретаторов, специализаторов и т. д.).

Это происходит оттого, что такие инструменты должны правильно работать для всех исходных программ, а не только для таких, которые состоят из удобных нам мнемонических структур. Например, что следует делать, если в программе на языке C в теле цикла while мы встретили оператор case (сразу, без switch)?

Довольно быстро (после каких-то 20 лет развития науки о языках программирования) оказалось, что для надёжной работы таких инструментов (или, как минимум, для правдоподобного обоснования, почему они работают именно так) необходимы способы формальной и точной спецификации семантики языков программирования, которые предоставили бы средства для математического доказательства свойств программ и их преобразователей.

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

– знание какого-либо языка программирования (а лучше нескольких, а лучше — принадлежащих разным парадигамам (C — Java — Haskell и т.д.))
– начало мат. логики
– начало дискретного анализа

Андрей Михайлович Райгородский — директор Физтех-школы прикладной математики и информатики МФТИ, доктор физико-математических наук.

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

Леонид Альжанов — студент КТ ИТМО, разработчик в Agisoft. Выпускник ПФМЛ 239, энтузиаст графического программирования, автор собственного 2D движка на Vulkan.
В прошлом году Леонид успешно прошёл два курса Николая Полярного, а затем вместе с ним работал над задачей, о которой расскажет на лекции.

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

• где блик будет ярким (глянцевая поверхность), а где блика не будет вовсе (например, какой-нибудь сухой мох)?
• где блик будет большим, а где — маленьким пятнышком?
• где игра света обнаружит трещину, а где — идеально отполированную поверхность?

Для реалистичного описания взаимодействия поверхности и света часто используют Physically-Based Rendering (PBR). Этот подход позволяет передать ощущение металличности, мокрости, глянцевости и рыхлости поверхности.

На лекции обсудим программу, разработанную в рамках летней стажировки. В рамках проекта был разработан метод, строящий правдоподобные и детальные PBR-текстуры (albedo map, normal map, roughness map, metallic map) методом математической оптимизации. Обсудим также, как этот алгоритм был ускорен на видеокартах.

Предполагается, что слушателям:

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