Отделение информатики ОШ

УЧАСТНИКИ

На осеннюю смену с 31 октября по 6 ноября на направление подготовки «Информатика» мы приглашаем учащихся 7-11 классов.

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

Обучение ведется на языке программирования С++.

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

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

Для тех, кто не владеет языком «С++», но хочет его изучить, у нас есть регулярный курс по «С++ с нуля».

ОБУЧЕНИЕ

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

Обращаем внимание еще раз: во всех группах обучение происходит на языке С++, и примеры реализации алгоритмов будут показываться именно на этом языке. Если вы будете программировать на другом языке, то: а) «перевод» алгоритма останется за вами; б) как уже было сказано ранее, в случае некоторых языков, таких как Python, нет гарантии, что задачу в принципе можно сдать. В силу этого, даже если вы виртуозно владеете Python-ом, знаете много алгоритмов, но не владеете С++, вы не сможете сдавать домашние задания, в таком случае единственный вариант обучения, который мы можем вам предложить — это онлайн-курс «C++ с нуля». Обращаем ваше внимание на то, что данный курс не является направлением на смене осенней Олимпиадной школы.

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

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

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

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

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

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

Группа ИИ-1:

— Основы асимптотики. Бинарный поиск, бинарный поиск по ответу
— ТЧ: остатки по модулю, по простому модулю. Нахождение обратного по модулю, быстрое возведение в степень, решето Эратосфена
— Введение в динамическое программирование, одномерное ДП: двумерное, рюкзак

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

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

Группа ИИ-2:

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

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

— Геометрия — введение: точки-прямые-отрезки, скалярные/векторные произведения, расстояния/пересечения и т.п, площадь простого многоугольника через векторное произведение
— ДП: задачи об НВП, НОП
— Диаметр дерева, ДП на поддеревьях

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

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

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

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

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

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

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

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

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

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

Группа ИПро-5:
— Потоки — 1: алгоритм Эдмондса-Карпа, масштабирование, алгоритм Диница
— Потоки — 2: максимальный поток минимальной стоимости
— Суффиксный автомат
— Суффиксное дерево (с использование суффиксного массива, автомата)
— Быстрое преобразование Фурье. Быстрое деление. 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 (ЗКШ), АПО

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

Виденин Сергей Александрович Директор чемпионата мира по программированию ICPC Восточно-сибирского региона; Сертифицированный инструктор Microsoft (Microsoft Certified Trainer, MCT); Заведующий кафедры «Информационные системы» СФУ; Преподаватель курса «Программирование» и «Архитектура информационных систем»;

Ким Зыонг преподаватель АНОО «Физтех-лицей» им. П. Л. Капицы методист ЦТПО МФТИ

Красносельская Марфа Учительница информатики 57 школы. Выпускница математического факультета ВШЭ, совместный бакалавриат ВШЭ и ЦПМ.

Хохрин Максим Преподаватель информатики лицея НИУ ВШЭ Победитель олимпиады «Я – профессионал» по направлению «Интернет вещей и киберфизические системы» 2019 г. Победитель конкурса научных IT проектов Цифровая трансформация 2019 г.

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

Зарегистрироваться