Информатика

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

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

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

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

 

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

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

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

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

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

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

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

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

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

  • Методист отделения информатики
  • Кандидат физико-математических наук
  • Двукратный призер и победитель Всероссийской олимпиады школьников по информатике (2007-2009)
  • Четырехкратный призер полуфинала ACM ICPC
  • Финалист ACM ICPC 2014
  • Финалист Russian Code Cup 2014
  • Тренер бронзовых призёров 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
  • Двукратный призёр ВсОШ по информатике

Шарушинский
Георгий Александрович

  • Призер Всероссийской олимпиады школьников по информатике
  • Призёр индивидуальной олимпиады школьников по информатике
  • Призёр олимпиады «Высшая проба» по информатике
  • Член жюри регионального этапа ВсОШ

Агеев
Артем Андреевич

  • Финалист международного конкурса проектных работ Intel ISEF (2019)
  • Победитель Пекинского конкурса проектных работ BYSCC (2019)
  • Участник и организатор научных выставок ‘Nauka 0+’ и ‘Rukami Fest’
  • Победитель и дважды финалист конкурса ‘Учёные Будущего’ (2018-2020)

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

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

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

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

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

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

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

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

Халтурин
Евгений Александрович

  • Лауреат стипендии Президента РФ (2021 год)
  • Победитель олимпиады «Я – профессионал» по направлению «Программная инженерия» (2019 г)
  • Призёр по направлению «Безопасность ИС и технологий КВО» (2021 г)
  • Диплом второй степени в полуфинале чемпионата мира по программированию ACM ICPC (2017-2018 гг)
Задать вопрос ?