Алгоритмы и приложения

В рамках направления планируется два потока, разделение на потоки будет произведено в начале школы на основе входного тестирования.

Программа состоит из двух тесно связанных частей: алгоритмы и их приложения.

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

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

К участию приглашаются все желающие, уже умеющие программировать на каком-нибудь языке. Основной язык курса – С++, но жестких ограничений нет. Для тех, кто мало знаком c C++, в начале программы базового потока запланирован небольшой блок про синтаксис и основные конструкции.

Структуры данных

Базовый поток
Продвинутый поток
Базовые структуры данных: список, очередь, стек, куча, set, map, hashmap. Вероятностные структуры данных: Фильтр Блума, HyperLogLog. Conflict-free replicated data types.
Деревья поиска.
Бинарный поиск, бинарный поиск по ответу. Декартово дерево и декартово дерево по неявному ключу. Различные алгоритмы балансировки деревьев. Деревья отрезков и двумерные вариация.
Приложения
Простые структуры данных возникают при написании практически любого кода. Менее тривиальные примеры:
  • Поиск ближайших соседей в пространстве большой размерности (поисковые системы).
  • Планировщик выполнения многопоточных программ.

Графы

Базовый поток
Продвинутый поток
Вариации и представления графов. Алгоритмы поиска кратчайших путей (Флойд, Дейкстра, Форд-Беллман) и их вариации.
Обходы в ширину и глубину. Остовные деревья.
Алгоритмы поиска кратчайших путей (Флойд, Дейкстра, Форд-Беллман). Поиск максимального потока и связанные задачи.
Приложения
Теорию графов часто используется для моделирования взаимосвязей между реальными объектами. В "полевых" условиях работа с графами может вызывать нетривиальные проблемы с производительностью. Участники познакомятся с приложениями в следующих областях:
  • Геоинформационные системы.
  • Анализ социальных графов.
  • Оптимизации нейросетей и других графов вычислений.
  • Анализ центров влияния через PageRank.

Строки и конечные автоматы

Базовый поток
Продвинутый поток
Базовая работа со строками. Быстрый поиск подстроки.
Бор. Бор, Ахо-Корасик.
Теория формальных языков. Конечные автоматы и машины состояний.

Регулярные выражения.

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

Методы оптимизации

Базовый поток
Продвинутый поток
Разные постановки задач оптимизации:
  • Линейное программирование.
  • Глобальная оптимизация vs локальная.
Переборы, отсечение по дереву обхода.
Тернарный поиск. Градиентный спуск.
Генетические алгоритмы, алгоритм имитации отжига.
Приложения
  • Как обучаются нейронные сети, и где математика расходится с практикой.
  • Поиск стратегии в играх (например, крестики-нолики на бесконечном поле).
  • Решение алгоритмических задач с помощью методов оптимизации.

Теоретико-числовые алгоритмы и хэши

Базовый поток
Продвинутый поток
Вычисления по простому модулю, алгоритм Евклида.

Быстрое возведение в степень.

Введение в теорию групп.
Полиномиальное хэширование строк. Хэш-таблицы, хэширование множеств, locality-sensitive hashing.
Работа с битовыми представлениями. Битовые оптимизации. Быстрое преобразование Фурье.
Приложения
  • Шифрование RSA.
  • Цифровая подпись.
  • Аутентификация и проверка корректности больших объемов данных.
  • Блокчейн.

Динамическое программирование и вероятностное моделирование

Базовый поток
Продвинутый поток
Введение в динамическое программирование, задача о рюкзаке. Динамика по профилю, по подмножествам, по поддеревьям.
Случайные величины. Категориальные распределения. Марковские цепи и введение в математическую статистику.
Байесовский подход к теории вероятностей. Непараметрические байесовские модели.
Приложения
  • Выравнивание генома в биоинформатике.
  • Разметка частей речи в естественном языке.
  • Тестирование гипотез и выводы по данным.

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