Информатика

Обратите внимание!

Для участия в группах, отличных от “Си++ с нуля”, необходимо входное тестирование перед началом смены.

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

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

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

Обучение ведется на языке программирования С++, за исключением программы «Подготовка к региональному этапу ВсОШ», где обучение будет также на «Python».

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

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

Обращаем внимание еще раз: во всех группах обучение происходит на языке С++ и примеры реализации алгоритмов будут показываться именно на этом языке. Если вы будете программировать на другом языке, то: а) «перевод» алгоритма останется за вами; б)  в случае некоторых языков, таких как 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

Информатика. Алгоритмы

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

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

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

• Основы асимптотики. Бинарный поиск, бинарный поиск по ответу

• ТЧ: остатки по модулю, по простому модулю. Нахождение обратного по модулю, быстрое возведение в степень, решето Эратосфена

• Введение в динамическое программирование, одномерное ДП: двумерное, рюкзак

• Геометрия — введение: точки-прямые-отрезки, скалярные/векторные произведения, расстояния/пересечения и т.п.

• Рекурсивные переборы (задача о расстановках ферзей, генерация ПСП, Ханойские башни)

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

• Сортировки. Слияние двух отсортированных массивов. MergeSort, задача о количестве инверсий; Heap, операции с ним, Heapsort

• Графы: введение, способы хранения, DFS, BFS

• Геометрия — введение: точки-прямые-отрезки, скалярные/векторные произведения, расстояния/пересечения и т.п, площадь простого многоугольника через векторное произведение

• ДП: задачи об НВП, НОП

• Диаметр дерева, ДП на поддеревьях

Для группы Инф-3:

• Задачи RSQ, RMQ. Префиксные суммы, разреженная таблица, дерево отрезков

• ДП: номер по объекту(перестановки, сочетания, ПСП…)/объект по номеру

• Геометрия — база + многоугольники: лежит ли точка в многоугольнике (за линию и за log n в выпуклом многоугольнике), площадь многоугольника (метод трапеций и сумма векторных), площадь пересечения круга и многоугольникаа

• ТЧ: решето Эратосфена, линейное решето Эратосфена, КТО, диофантовы уравнения

• Базовые строки (Префикс, Z, Манакер, хэши)

Для группы Инф-4:

• Остовные деревья, СНМ

• Мосты, точки сочленения, 2-мосты, неочевидный разговор о dfs. Поиск компонент сильной связности, задача 2-SAT

• STL: НВП за O(n log n), Дейкстра/Прим с кучей, auto, lambda-функции, декомпозиция, кастомные компараторы, передача функции параметром функции, перегрузка ввода и вывода

• — Геометрия — база + тернарный поиск

• — Алгоритм Дейкстры, неасимтотические оптимизации, алгоритм А*, Флойд, Форд-Беллман

Для группы Инф-5:

• Паросочетания: алгоритм Куна, мин.покрытие, макс. незав. мн-во

• Дерево отрезков: присвание/прибавление/… на подотрезке. Применения: метод сканирующей прямой

• SQRT-декомпозиция, алгоритм Мо

• Выпуклая оболочка: алгоритмы Джарвиса, Грэхема, Эндрю

• Декартовы деревья по явному ключу, по неявному ключу

Для группы Инф-6:

• ДП на подмасках/по профилю, по изломанному профилю

• Heavy-light decomposition, centroid decomposition

• Суффиксный массив: построение за O(n log n), алгоритм Касаи
  Бор, алгоритм Ахо-Корасик

• Теория игр: введение, примеры игр, ретроанализ, теория Шпрага-Гранди

Для группы Инф-7:

• Потоки — 1: алгоритм Эдмондса-Карпа, масштабирование, алгоритм Диница

• Потоки — 2: максимальный поток минимальной стоимости

• Суффиксный автомат

• Суффиксное дерево (с использование суффиксного массива, автомата)

• Быстрое преобразование Фурье. Быстрое деление. Fast subset convolution и многомерное преобразование Фурье

Группы Инф-1 и 2 предназначены для школьников, которые хотят готовиться к олимпиадам по информатике, но еще не имеют большого опыта и/или успехов в спортивном программировании. Инф-3 и следующие группы предназначены для школьников, уже имеющих опыт и успехи в олимпиадном программировании и желающих развиваться в этом направлении дальше. Рекомендуемый уровень обучающихся для группы Инф-4 – не ниже участников региональных этапов Всероссийской олимпиады,  для группы Инф-5 — не ниже призеров региональных этапов Всероссийской олимпиады.

Подготовка к региональному этапу ВсОШ по информатике

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

Подготовка к заключительному этапу ВсОШ по информатике и IOI

Здесь вас ждут тренировочные контесты формата школьных олимпиад и формата «на полное решение» (RuCode/ICPC). Сложность контестов — уровень div A RuCode/полуфиналов ICPC, а также тренировочных туров сборов.