Школа для учителей информатики

Школа для учителей информатики "Алгоритмы в решении олимпиадных задач" направлена на подготовку учителей информатики средних и средне-специальных образовательных организаций. Основной упор будет сделан на изучение алгоритмов, встречающихся на олимпиадах школьников по информатике и решение олимпиадных задач, а также практическое применение изученных алгоритмов.

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

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

Выполнить задания заочного модуля необходимо до 1 марта включительно.

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

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

9 января - 1 марта

Заочный этап.

Необходимо успешно решить не менее 50% задач из каждого учебного блока.
20-24 марта

Очный этап.

30 лучших педагогов будут приглашены на очный интенсив, который пройдет на ФКН.

Примерная программа курса

Параллель «С»

Структуры данных: стек, очередь, дек и их применение в олимпиадных задачах. Структуры данных STL (vector, queue, deque).

Структуры данных STL: set, map и их применения.

Простые задачи на бинарный поиск.

Сортировка подсчетом и применение встроенных сортировок.

Введение в динамическое программирование: одномерная и двумерная динамика.

Комбинаторный перебор и рекурсия, алгоритмы STL для организации перебора.

Графы: способы их хранения и обхода (в ширину и в глубину). Проверка графа на двудольность, поиск циклов и топологическая сортировка графа.

Введение в вычислительную геометрию: расстояние до прямой, пересечение прямых, площадь многоугольника.

Введение в теоретико-числовые алгоритмы: НОД, НОК, разложение на множители, решето Эратосфена, проверка на простоту, быстрое возведение в степень.

Типовые олимпиадные задачи, решаемые с помощью жадных алгоритмов.

Строковые алгоритмы: применение конечных автоматов, бор, хеширование.

Параллель «B»

Применение сортировок: скользящее окно, два указателя, сканирующая прямая, сжатие координат.

Бинарный поиск и его применения.

Применение структур данных STL к решению задач: set, multiset, map, priority_queue, rope.

Хеширование строк и других объектов, хеш-таблицы.

Динамическое программирование на подотрезках, на поддеревьях, на подмножествах, по профилю.

Обход графов в глубину: мосты, точки сочленения, компоненты сильной связности.

Кратчайшие пути в графах (алгоритмы Дейкстры, Флойда, Форда-Беллмана), минимальные остовные деревья (алгоритм Прима) и система непересекающихся множеств (алгоритм Краскала).

Одномерные деревья отрезков и их применения (задачи RMQ, RSQ, групповые операции, дерево отображений).

Задачи LCA (наименьший общий предок) и LA (k-й предок). Разреженные таблицы.

Вычислительная геометрия на плоскости.

Быстрые алгоритмы вычислительной геометрии. Применение структур данных в вычислительной геометрии.

Параллель «А»

Дерево отрезков, дерево Фенвика

Декартово дерево

DSU, Dynamic Connectivity Offline

Z-функция, префикс-функция, Ахо-Корасик