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


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

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


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


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


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

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


Базовый поток

Продвинутый поток

Базовые структуры данных: список, очередь, стек, куча, set, map, hashmap.

Хэши (хэш-таблицы, хэширование строк, хэширование множеств, locality-sensitive hashing).

Деревья поиска

Бинарный поиск

Декартово дерево и декартово дерево по неявному ключу. Различные алгоритмы балансировки деревьев. Деревья отрезков и двумерные вариация.

Приложения

Простые структуры данных возникают при написании практически любого кода.

Помимо двоичного поиска, схожие идеи часто применяют в следующих областях:

  • Поиск ближайших соседей в пространстве большой размерности (участники реализуют свою поисковую систему)

  • Планировщик выполнения многопоточных программ


Графы


Базовый поток

Продвинутый поток

Вариации и представления


Алгоритмы поиска кратчайших путей (Флойд, Дейкстра, Форд-Беллман) и их вариации

Обходы в ширину и глубину

Остовные деревья

Алгоритмы поиска кратчайших путей (Флойд, Дейкстра, Форд-Беллман).

Поиск максимального потока и связанные задачи

Приложения

Теорию графов часто используется для моделирования взаимосвязей между реальными объектами. В “полевых” условиях работа с графами может вызывать нетривиальные проблемы с производительностью. Участники познакомятся с приложениями в следующих областях:

    • Геоинформационные системы

    • Анализ социальных графов

    • Оптимизации нейросетей и других графов вычислений

    • Анализ центров влияния через PageRank

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


Базовый поток

Продвинутый поток

Работа со строками, хэширование

Быстрый поиск подстроки

Бор

Бор, Ахо-Корасик

Теория формальных языков. Конечные автоматы и машины состояний.

Приложения

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

    • Диалоговые системы

    • Парсеры и регулярные выражения

    • Порождающие грамматики и генератор естественной речи

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


Темы этого блока будут рассмотрены ограничено, в зависимости от объема времени, потраченного на предыдущие темы.



Базовый поток

Продвинутый поток

Разные постановки задач оптимизации:

  • Линейное программирование

  • Глобальная оптимизация vs локальная

Переборы, отсечение по дереву обхода.

Тернарный поиск

Задача коммивояжера, приближенные алгоритмы решения

Динамическое программирование

Задача о рюкзаке

Градиентный спуск

Генетические алгоритмы, метод отжига

Приложения

  • Как обучаются нейронные сети, и где математика расходится с практикой

  • Поиск стратегии в играх (например, крестики-нолики на бесконечном поле)

  • Решение алгоритмических задач с помощью методов оптимизации


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