Информатика

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

Смена направлена на подготовку к региональному и заключительному этапам Всероссийской олимпиады школьников, а также к перечневым олимпиадам 1-2 уровня: «Технокубок», «Московская олимпиада школьников», «Открытая олимпиада по программированию», «Открытая олимпиада школьников (информатика)», «Олимпиада школьников по информатике и программированию», «Высшая проба» и другие.

Стартовый уровень — владение основными конструкциями языка С++ (основные типы данных и арифметические и битовые операции с ними, циклы for и while, функции, массивы, структуры и классы)

Обучение ведется на языке программирования С++.

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

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

Обращаем внимание еще раз: во всех группах обучение происходит на языке С++, и примеры реализации алгоритмов будут показываться именно на этом языке. Если вы будете программировать на другом языке, то: а) «перевод» алгоритма останется за вами; б) как уже было сказано ранее, в случае некоторых языков, таких как Python, нет гарантии, что задачу в принципе можно сдать. В силу этого, даже если вы виртуозно владеете Python-ом, знаете много алгоритмов, но не владеете С++, вы не сможете сдавать домашние задания, в этом случае можем предложить вам направление «C++ с нуля».

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

C++ с нуля

Направление предназначено для тех, кто никогда не программировал на языке С++ и хочет изучить этот язык программирования. Группа подойдет как для тех, кто никогда в жизни не программировал, так и для тех, кто имеет опыт программирования на другом языке (Python, Java, Pascal/Delphi и т.п.).

Примерная программа:
1) С++: введение, установка codeblocks+mingw, Базовые арифметические операции, ввод-вывод, оператор if, логические операции, знакомим с cppreference
2) Продвинутые операции (битовые сдвиги, разложение числа в p-ичной системе счисления). Простые типы данных, for, while, do-while
3) Массивы, двумерные массивы, разбора типичных ошибок при работе. Массивы как С-шные, так и std::vector
4) Функции, рекурсия, проблема циклической зависимости, можно как пример посмотреть разные dfs-обходы
5) Составные типы данных struct, их использование с std::vector, можно затронуть поэлементный for
6) Немного об std::algorithms: сортировка, компараторы.
7) Длинная арифметика: сложение, вычитание, умножение, деление, если всё хорошо, извлечение корня (2 способа: бинпоиск, ‘математический подход’)
8) Контейнеры stack, queue, deque

Информатика + Информатика

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

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

Для успешного поступления в параллель И+И необходимо пройти тестирование по информатике.

Примерная программа:

Для группы ИИ-1:

• Основы асимптотики. Бинарный поиск, бинарный поиск по ответу
• ТЧ: остатки по модулю, по простому модулю. Нахождение обратного по модулю, быстрое возведение в степень, решето Эратосфена
• Введение в динамическое программирование, одномерное ДП: двумерное, рюкзак
• Геометрия — введение: точки-прямые-отрезки, скалярные/векторные произведения, расстояния/пересечения и т.п.
• Рекурсивные переборы (задача о расстановках ферзей, генерация ПСП, Ханойские башни)

Для группы ИИ-2:

• Сортировки. Слияние двух отсортированных массивов. MergeSort, задача о количестве инверсий; Heap, операции с ним, Heapsort
• Графы: введение, способы хранения, DFS, BFS
• Геометрия — введение: точки-прямые-отрезки, скалярные/векторные произведения, расстояния/пересечения и т.п, площадь простого многоугольника через векторное произведение
• ДП: задачи об НВП, НОП
• Диаметр дерева, ДП на поддеревьях

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

Информатика Регион

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

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

Информатика ПРОФИ

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

Примерная программа:

Для группы ИПро-1:

• Задачи RSQ, RMQ. Префиксные суммы, разреженная таблица, дерево отрезков
• ДП: номер по объекту(перестановки, сочетания, ПСП…)/объект по номеру
• Геометрия — база + многоугольники: лежит ли точка в многоугольнике (за линию и за log n в выпуклом многоугольнике), площадь многоугольника (метод трапеций и сумма векторных), площадь пересечения круга и многоугольникаа
• ТЧ: решето Эратосфена, линейное решето Эратосфена, КТО, диофантовы уравнения
• Базовые строки (Префикс, Z, Манакер, хэши)

Для группы ИПро-2

• Остовные деревья, СНМ
• Мосты, точки сочленения, 2-мосты, неочевидный разговор о dfs. Поиск компонент сильной связности, задача 2-SAT
• STL: НВП за O(n log n), Дейкстра/Прим с кучей, auto, lambda-функции, декомпозиция, кастомные компараторы, передача функции параметром функции, перегрузка ввода и вывода
• — Геометрия — база + тернарный поиск
• — Алгоритм Дейкстры, неасимтотические оптимизации, алгоритм А*, Флойд, Форд-Беллман

Для группы ИПро-3

• Паросочетания: алгоритм Куна, мин.покрытие, макс. незав. мн-во
• Дерево отрезков: присвание/прибавление/… на подотрезке. Применения: метод сканирующей прямой
• SQRT-декомпозиция, алгоритм Мо
• Выпуклая оболочка: алгоритмы Джарвиса, Грэхема, Эндрю
• Декартовы деревья по явному ключу, по неявному ключу

Для группы ИПро-4

• ДП на подмасках/по профилю, по изломанному профилю
• Heavy-light decomposition, centroid decomposition
• Суффиксный массив: построение за O(n log n), алгоритм Касаи
  Бор, алгоритм Ахо-Корасик
• Теория игр: введение, примеры игр, ретроанализ, теория Шпрага-Гранди

Для группы ИПро-5

• Потоки — 1: алгоритм Эдмондса-Карпа, масштабирование, алгоритм Диница
• Потоки — 2: максимальный поток минимальной стоимости
• Суффиксный автомат
• Суффиксное дерево (с использование суффиксного массива, автомата)
• Быстрое преобразование Фурье. Быстрое деление. Fast subset convolution и многомерное преобразование Фурье

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

Рекомендуемый уровень обучающихся в параллели Информатика ПРОФИ – не ниже участников (для группы ИПро-2) и/или призеров (для группы ИПро-3) региональных этапов Всероссийской олимпиады.

Информатика ПРОФИ Hard

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

Предполагаемый уровень – призеры/победители заключительного этапа Всероссийской олимпиады школьников по информатике, а также те, кто успешно закончил обучение в сильнейших группах по направлению «Информатика ПРОФИ» ЗОШ/ЛОШ/ООШ/ВОШ в предыдущих сменах.