Николай Владимирович Мальковский — кандидат физико-математических наук; Principal Engineer, Chebyshev Research Center; лектор МКН СПбГУ, ВШЭ.
Область интересов: практически-применимые эффективные алгоритмы и особенности их реализации.

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

Николай Полярный
– Team Lead команды разработки Agisoft Metashape
– Автор курса фотограмметрии и курса алгоритмов на видеокартах
– Школьный учитель программирования

Графические процессоры (GPU) предоставляют тысячи параллельных вычислительных потоков, поэтому при правильно организованном коде ускорение по сравнению с CPU может достигать ×10–×100. Однако не каждый алгоритм выигрывает от такой архитектуры. На курсе мы разберём, когда GPU-ускорение оправдано, и как извлечь из него максимум производительности.

Помимо разбора архитектуры и синтаксиса GPU-кода (CUDA, OpenCL, Vulkan), курс нацелен на формирование мышления в парадигме массового параллелизма. Мы обсудим, как перенести на GPU даже такие казалось бы линейные алгоритмы как merge-sort и добиться ускорения вплоть до ×100.

API-взаимодействие CPU с GPU мы обсудим лишь обзорно — в практических заданиях его возьмет на себя обёртка-библиотека. Главный акцент будет на коде, исполняемом непосредственно на видеокарте, а не на низкоуровневом управлении копированием памяти и запуском кернелов.

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

Примеры алгоритмов, которые мы реализуем в модели массового параллелизма:
– prefix-sum (scan)
– merge-sort за O(N) вместо O(N log N)
– умножение матриц (ядро большинства AI-фреймворков)
– построение BVH-дерева (фундамент современного real-time Ray Tracing)

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

Также на лекциях будут лилипуты и клоуны!

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

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

Изучаются специальные структуры и крупные задачи: сетевые модели, транспортные задачи с алгоритмами (максимальный поток/минимальный разрез), техники препроцессинга и факторизации. Обсуждаются основы декомпозиции (Данциг–Вулф). Практика включает моделирование и эксперименты в программных пакетах (открытых и коммерческих решателях ЛП), сравнение методов и анализ результатов. Требуются знания линейной алгебры и математического анализа; полезны навыки программирования.