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

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

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

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

Выполнить задания онлайн-этапа необходимо до 20 марта включительно.

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

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

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

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

Структуры данных: стек, очередь, дек и их применение в олимпиадных задачах. Структуры данных STL (vector, queue, deque).
Структуры данных STL: set, map и их применения.
Простые задачи на бинарный поиск.
Сортировка подсчетом и применение встроенных сортировок.
Введение в динамическое программирование: одномерная и двумерная динамика.
Комбинаторный перебор и рекурсия, алгоритмы STL для организации перебора.
Графы: способы их хранения и обхода (в ширину и в глубину). Проверка графа на двудольность, поиск циклов и топологическая сортировка графа.
Введение в вычислительную геометрию: расстояние до прямой, пересечение прямых, площадь многоугольника.
Введение в теоретико-числовые алгоритмы: НОД, НОК, разложение на множители, решето Эратосфена, проверка на простоту, быстрое возведение в степень.
Типовые олимпиадные задачи, решаемые с помощью жадных алгоритмов.
Строковые алгоритмы: применение конечных автоматов, бор, хеширование.

Рекомендованным языком параллели C является C++. Вступительное задание можно решать и на другом языке программирования, однако к моменту начала школы желательно освоить C++ в рамках онлайн-курса «Введение в программирование (C++)» от Яндекса и НИУ ВШЭ.

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

Применение сортировок: скользящее окно, два указателя, сканирующая прямая, сжатие координат.
Бинарный поиск и его применения.
Применение структур данных STL к решению задач: set, multiset, map, priority_queue, rope.
Хеширование строк и других объектов, хеш-таблицы.
Динамическое программирование на подотрезках, на поддеревьях, на подмножествах, по профилю.
Обход графов в глубину: мосты, точки сочленения, компоненты сильной связности.
Кратчайшие пути в графах (алгоритмы Дейкстры, Флойда, Форда-Беллмана), минимальные остовные деревья (алгоритм Прима) и система непересекающихся множеств (алгоритм Краскала).
Одномерные деревья отрезков и их применения (задачи RMQ, RSQ, групповые операции, дерево отображений).
Задачи LCA (наименьший общий предок) и LA (k-й предок). Разреженные таблицы.
Вычислительная геометрия на плоскости.
Быстрые алгоритмы вычислительной геометрии. Применение структур данных в вычислительной геометрии.

План работы школы

Шаг 1:

Заполнить регистрационную анкету.
Шаг 2:

Выполнить задания заочного модуля.
Шаг 3:

Приехать на очный модуль

Список участников очного этапа

1. Бонвеч Елена Алексеевна
2. Ганилова Татьяна Евгеньевна
3. Горшков Даниил Александрович
4. Илларионова Любовь Викторовна
5. Келина Марина Александровна
6. Кондрашин Юрий Алексеевич
7. Корельская Елена Юрьевна
8. Ксенофонтов Алексей Николаевич
9. Кузнецова Александра Борисовна
10. Курапов Михаил Михайлович
11. Мальцев Александр Михайлолвич
12. Мамцев Виталий Сергеевич
13. Митясова Елена Анатольевна
14. Муржин Дмитрий Викторович
15. Нигматуллин Вадим Ринатович
16. Песков Аркадий Геннадьевич
17. Плетенёва Людмила Викторовна
18. Пусева Ольга Наиловна
19. Чиглаков Ильдар Андреевич
20. Эргашев Артур Артыкович