Информатика

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

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

Участники, не написавшие тестирование или решившие в нем недостаточное количество задач, автоматически зачисляются в группу “Си++ с нуля”.

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

Смена направлена на подготовку к региональному и заключительному этапам Всероссийской олимпиады школьников, а также к перечневым олимпиадам 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

Информатика

В следующие ниже группы попадут участники, набравшие проходные баллы на тестировании. Каждый день участник может выбирать группу в зависимости от темы и сложности. При этом тема состоит из 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 — не ниже призеров региональных этапов Всероссийской олимпиады.

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

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

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

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

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