Информатика

ОСОБЕННОСТИ ОБУЧЕНИЯ

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

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

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

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

Методический совет

Куренков
Владимир Вячеславович

  • Методист отделения информатики
  • Старший преподаватель НИУ ВШЭ
  • Директор центра технологических конкурсов и олимпиад НИТУ МИСИС

Козлов
Владислав Сергеевич

  • Методист отделения информатики
  • Лауреат Гранта Министерства образования за достижения по математике и информатике
  • Призёр Открытой олимпиады школьников 2019-2020
  • Один из составителей задач олимпиады ФПМИ по информатике
  • Финалист кейса Phystech Business Solutions по технологиям блокчейна
  • Призер Олимпиады Тинькофф и Мехмата МГУ по математике 2021

Алькин
Руслан Валерьевич

  • Главный методист RuCode трека алгоритмическое программирование
  • Организатор олимпиад по спортивному программированию в Карелии
  • Руководитель Клуба Творчества Программистов и тренер команд Петрозаводского государственного университета
  • Победитель программы VK Fellowship для преподавателей, призер студенческих олимпиад ICPC, в частности

Преподаватели

Куренков
Владимир Вячеславович

  • Методист отделения информатики
  • Старший преподаватель НИУ ВШЭ
  • Директор центра технологических конкурсов и олимпиад НИТУ МИСИС

Алькин
Руслан Валерьевич

  • Главный методист RuCode трека алгоритмическое программирование
  • Организатор олимпиад по спортивному программированию в Карелии
  • Руководитель Клуба Творчества Программистов и тренер команд Петрозаводского государственного университета
  • Победитель программы VK Fellowship для преподавателей, призер студенческих олимпиад ICPC, в частности

Христенко
Олег Богданович

  • Технический координатор Олимпиадных школ, Moscow Workshops Juniors и международных студенческих сборов по программированию Moscow Workshops ICPC
  • Член жюри Московского четвертьфинала ICPC
  • Координатор Открытого кубка имени Е.В. Панкратьева
  • Главный редактор портала snarknews.info

Козлов
Владислав Сергеевич

  • Методист отделения информатики
  • Лауреат Гранта Министерства образования за достижения по математике и информатике
  • Призёр Открытой олимпиады школьников 2019-2020
  • Один из составителей задач олимпиады ФПМИ по информатике
  • Финалист кейса Phystech Business Solutions по технологиям блокчейна
  • Призер Олимпиады Тинькофф и Мехмата МГУ по математике 2021

Степанов
Илья Даниилович

  • Методист отделения информатики
  • Старший преподаватель кафедры алгоритмов и технологий программирования МФТИ
  • Бронзовый медалист чемпионата мира по программированию ICPC 2019
  • Двукратный призёр заключительного этапа ВсОШ по информатике
  • Победитель Всесибирской открытой олимпиады по программированию имени Поттосина 2018
  • Победитель чемпионата Урала 2018, второе место на NEERC 2018
Задать вопрос ?