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

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

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

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

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

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

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

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

Графы

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

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

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

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

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

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

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

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

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

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