Школа для учителей информатики – 2021 – Национальный исследовательский университет «Высшая школа экономики»

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

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

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

Обучение в школе будет проходить в двух параллелях.

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

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

Структуры данных: стек, очередь, дек и их применение в олимпиадных задачах. Структуры данных 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:

Решить тестовые задания тех параллелей, на которые вы поступаете: параллель B, параллель С.

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

Басс Ирина Сергеевна
Бонвеч Елена Алексеевна
Галганова Дарья Анатольевна
Ганилова Татьяна Евгеньевна
Гришкина Мария Петровна
Илларионова Любовь Викторовна
Исаев Виталий Вячеславович
Карамшук Иванна Николаевна
Келина Марина Александровна
Кокурина Юлия Викторовна
Кондрашин Юрий Алексеевич
Ксенофонтов Алексей Николаевич
Курапов Михаил Михайлович
Лапухина Надежда Олеговна
Малыгин Андрей Александрович
Мартынов Александр Николаевич
Мартынова Анна Александровна
Марчукова Татьяна Ивановна
Нигматуллин Вадим Ринатович
Перескокова Ольга Ивановна
Пусева Ольга Наиловна
Румынин Матвей Николаевич
Савченко Сергей Викторович
Семенова Алена Владимировна
Силаев Петр Борисович
Хузиахметов Артур Хатипович
Шатилова Елена Николаевна
Щёголев Александр Фёдорович