Отделение информатики Олимпиадных школ

УЧАСТНИКИ

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

Видеоприглашение от методиста отделения:


ЯЗЫКИ ПРОГРАММИРОВАНИЯ

Языком программирования по умолчанию является С++. Преподаватели, показывая примеры реализаций алгоритмов и структур данных, будут отдавать предпочтение именно этому языку. Гарантируется, что все задачи смены можно решить, уверенно уложившись в ограничения по времени, на языках С++ и Java. Допускается сдача задач на языках Python 2/3, однако, программы на этом языке работают в несколько раз медленнее, нежели на С++. В силу этого, во многих сложных задачах написание достаточно быстрого решения задач на Python оказывается практически невозможным. На нашей школе мы так же не даем никаких гарантий относительно того, можно ли сдать ту или иную задачу на языке Python. Также это относится к языкам Pascal/Delphi — эти языки сопоставимы по скорости с C++ и Java, однако, Pascal/Delphi НЕ ВХОДЯТ в список языков программирования, разрешенных на Всероссийской олимпиаде школьников по информатике. В силу этого, мы также не рекомендуем использовать этот язык.

Для тех, кто не владеет языком С++, но хочет его изучить, у нас есть специальная группа, в которой значительная часть занятий посвящена изучению языка программирования с нуля — это группа ИИ-1 направления "Информатика + Информатика" (подробности направления читайте в разделе «Обучение»). Чтобы попасть в эту группу, нужно также пройти тестирование. При этом гарантируется, что в тестировании присутствует достаточное количество задач, которые можно решить и на языке Python, и на остальных языках. Подробнее о программе в ИИ-1 и других группах можно ознакомиться в следующем разделе.


ОБУЧЕНИЕ

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

Для результативного освоения программы предлагаем следующие параллели подготовки:

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

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

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

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

    Примерная программа:
    Группа ИИ-1:
    - С++: введение. Базовые арифметические операции, ввод-вывод, оператор if, логические операции
    - С++: циклы for и while + типа данных
    - С++: массивы, двумерные массивы. Разложение числа в p-ичной системе счисления, битовые операции
    - С++: функции. Рекурсия. Составные типы данных (struct)
    - Геометрия - введение: точки-прямые-отрезки, скалярные/векторные произведения, расстояния/пересечения и т.п.
    - ТЧ: остатки по модулю, по простому модулю. Нахождение обратного по модулю, быстрое возведение в степень, решето Эратосфена
    - Введение в динамическое программирование, одномерное ДП
    - Двумерное ДП: задача о рюкзаке

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

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

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

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

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

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

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

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

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

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

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

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


НАШИ ПРЕПОДАВАТЕЛИ

Рухович Филипп Дмитриевич
Методист

  • Кандидат физико-математических наук;
  • Дважды призер и победитель Всероссийской олимпиады школьников по информатике (2007-2009);
  • Четырехкратный призер полуфинала ACM ICPC;
  • Финалист ACM ICPC 2014;
  • Абсолютный победитель личной Открытой олимпиады МФТИ;
  • Финалист Всероссийского открытого чемпионата по программированию, CROC 2013 и Russian Code Cup 2014;
  • Победитель KPI-Open 2013 и Открытого чемпионата по программированию в г. Гродно;
  • Тренер бронзовых призёров ICPC World Finals 2019;
  • Преподаватель по программированию у продвинутого потока ФПМИ МФТИ

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

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

Невструев Владислав Сергеевич

  • Призер Всероссийской олимпиады школьников по информатике (2014-2015);
  • Диплом третьей степени на Открытой олимпиаде по программированию (2014-2015);
  • Полуфиналист чемпионата мира по программированию ACM ICPC (2015-2016)

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

  • Первое место на Всесибирской открытой олимпиаде по программированию имени Поттосина 2018;
  • Первое место на чемпионате Урала 2018;
  • Второе место на NEERC 2018;
  • Бронзовая медаль чемпионата мира по программированию ICPC 2019;
  • Двукратный призёр ВсОШ по информатике

Труфанов Павел Николаевич

  • Преподаватель олимпиадной информатики в школе Летово;
  • Преподаватель вебинаров по олимпиадной информатике в онлайн-школе Фоксфорд;
  • Глава отделения информатики выездных школ Фоксфорда

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

  • Заведующий кафедры информатики Лицея НИУ ВШЭ;
  • Преподаватель курса «Разработка приложений под Android» в IT школе Samsung

Сапожников Денис Сергеевич

  • Участник ВсОШ 2017-2018;
  • Призёр Всесибирской командной олимпиады имени Поттосина 2019-2020;
  • Член жюри и автор задач на олимпиадах "Когнитивные технологии", Келдыш, RuCode;
  • Преподаватель на сменах Олимпиадных школ МФТИ (зимние и летние смены), MWJ (ЗКШ), АПО