Детский технопарк «Альтаир» РТУ МИРЭА открывает набор в клуб по
спортивному программированию для учащихся 8–11-х классов, владеющих
базовыми навыками программирования.
Занятия проводятся БЕСПЛАТНО и будут проходить 1 раз в неделю по
субботам во второй половине дня. Длительность одного занятия – 3 часа.
Начало курса — 5 февраля 2022 года. Длительность обучения — 2 года (для 11-х классов — 1 год).
Участники клуба готовятся к успешному выступлению на олимпиадах муниципального и регионального уровней, таких как:
- Всероссийская олимпиада школьников по информатике
- Всероссийская олимпиада школьников «Высшая проба» (ВШЭ)
- Олимпиада школьников СПбГУ по информатике
- Технокубок
- Олимпиада школьников «Ломоносов»
- Открытая олимпиада школьников по информатике ИТМО
- Олимпиада Университета Иннополис
- Московская олимпиада школьников по информатике и другие
Для участия в клубе необходимо зарегистрироваться по ссылке и пройти отборочный этап, который состоится 30 января в 14:00 в дистанционном формате.
Внимание! Регистрация доступна для школьников, зарегистрированных и авторизованных в личном кабинете школьника РТУ МИРЭА.
Рекомендуемые начальные знания:
- Типы данных, переменные, константы
- Инструкции ветвления
- Инструкции циклов
- Массивы, в том числе многомерные
Список простых задач олимпиадного формата, которые можно использовать для самопроверки (они необязательны для прохождения отбора, но помогут вам лучше понять, что такое олимпиадные задачи и готовы ли вы решать самые простые из них):
В чём ценность данного курса?
Фундаментальные знания. Написать «Hello World!» по обучающему видео в Youtube может практически каждый. Мы не научим вас делать красивое приложение на Android или Arduino (хотя постараемся ответить на вопросы в силу своего опыта).
Чему же вы научитесь в нашем клубе? Мы расскажем об особенностях представления данных в компьютере и какие проблемы связаны с этим; про различные способы оптимизации ваших программ — простые подходы и структуры данных; объясним алгоритмы, придуманные учёными-математиками и алгоритмистами, а также множество различных идей для написания эффективных программ и решения различных связанных с этим задач.
Но зачем нужны все эти знания в то время, когда на всё есть библиотеки и сложные программные системы, содержащие реализации всех стандартных алгоритмов? Есть несколько причин:
- В олимпиадах по программированию, как и в ЕГЭ, никакие библиотеки недоступны, только вы и стандартная версия языка. И тут вам потребуются все ваши познания и навыки.
- Многие крупные IT-компании на собеседованиях любят задавать алгоритмические задачи. Маловероятно, что вам будет достаточно посидеть пару недель на тематическом сайте, чтобы уверенно решать большинство таких задач.
- Чтобы использовать готовый алгоритм, вы должны понимать, какой алгоритм и как необходимо применить в данной конкретной ситуации. А ведь иногда решением задачи является их комбинация. В общем случае это может быть не столь очевидно.
- Существующих решений попросту не всегда достаточно для эффективного решения поставленной задачи. Причём это верно даже не для чистых программистов — любой учёный при анализе больших данных может столкнуться с важными недостатками существующих решений, из-за которых придётся реализовывать свой собственный проект.
Практика программирования. Как и любой другой навык, программирование требует практики. Много практики. Всякой практики. Но не всегда понятно, что программировать и как.
Задачи по программированию хорошо справляются с этой целью. Одна задача обычно требует не слишком много кода, что позволяет не потерять фокус. В то же время при решении даже самых простых задач вы будете отрабатывать раз за разом те или иные действия и приёмы, доводя их до автоматизма.
Вы можете встретить мнение, что олимпиадный код зачастую является написанным на скорую руку — некрасивым, некачественным, его сложно поддерживать, в реальных проектах придётся всё писать не так. Мы на это скажем лишь одно — нам тоже не нравится такой код, поэтому в процессе обучения внимание будет уделяться не только корректности кода, но ещё и его качеству — будут разбираться хорошие и плохие подходы к реализации с примерами от педагогов.
Общение с единомышленниками. На каждом занятии вы будете находиться в окружении людей со схожими, но в то же время чуть отличающимися от ваших интересами и знаниями. Если вы не постесняетесь, то сможете узнать много нового от своих новых знакомых и в то же время дать им что-то полезное для их будущей жизни. Как знать, возможно, именно в нашем клубе вы найдёте команду для создания своего первого стартапа!
Перспективы углублённого обучения. Для тех ребят, которые в будущем планируют продолжить учёбу в РТУ МИРЭА, данный курс позволит получить необходимые навыки для участия в студенческой сборной университета по спортивному программированию.
Сборная РТУ МИРЭА — это сообщество активных студентов, которым интересно решать сложные алгоритмические задачи под руководством тренеров. Получить углублённые знания здесь могут как начинающие олимпиадники, так и более опытные и сильные алгоритмисты. Наиболее активным студентам университет оплачивает участие в различных сборах по спортивному программированию.
Студенты, которые занимаются в составе сборной, демонстрируют высокие достижения на различных соревнованиях. Только за последнее время ребята вышли в полуфинал Международного студенческого чемпионата мира по программированию, стали призёрами и победителями на финальном чемпионате по алгоритмическому программированию в рамках международного фестиваля RuCode 2020, успешно выступили на сборах по алгоритмическому программированию и ИИ Discover World 2020. Больше информации о сборной в сообществе.
Содержание курса
- Формальное описание задач и проектирование алгоритмов. Формулировка задачи на языке математики, выделение числовых характеристик задачи и описание связей между ними. Проектирование алгоритма, решающего поставленную задачу. Асимптотическая оценка сложности алгоритма.
- Типы данных. Целые числа: представление в памяти, переполнение. Вещественные числа: представление в памяти, точность вычислений. Символы и строки. Массивы.
- Базовые структуры данных. Список (вектор и связный список). Стек, очередь, двунаправленная очередь. Очередь с приоритетами. Хеш-таблица. Двоичные деревья поиска.
- Простейшие приемы оптимизации. Сортировки, принцип «Разделяй и властвуй». Префикс-суммы. Бинарный поиск. Два указателя. Сканирующая прямая.
- Рекурсия, перебор. Внутреннее устройство рекурсии. Рекуррентные соотношения. Ханойские башни. Генерация перестановок. Перебор всех подмножеств.
- Основы теории чисел. Системы счисления и представления числа. Делимость и модульная арифметика. Делители числа. Простые числа. Наибольший общий делитель и алгоритм Евклида. Быстрое возведение в степень. Функция Эйлера.
- Основы теории графов. Способы хранения. Поиск в ширину. Поиск в глубину. Топологическая сортировка. Кратчайшие пути. Минимальные остовные деревья, система непересекающихся множеств. Наименьший общий предок.
- Динамическое программирование. Одномерное (зайчик ^_^) и двумерное (черепашка). ДП на подотрезках, подмножествах, поддеревьях и т.д.
- Комбинаторика. Перестановки. Сочетания и размещения. Треугольник Паскаля. Задачи о шарах и урнах. Принцип включения-исключения.
- Геометрия. Векторы. Прямые, лучи, отрезки. Выпуклая оболочка.
- Жадные алгоритмы. Принцип обмена.
- Алгоритмы на строках. Полиномиальные хеши. Z- и Префикс-функции. Палиндромы, алгоритм Манакера. Бор, алгоритм Ахо-Корасик. Суффиксный массив.
- Основы теории вероятности. Вероятность события. Случайная величина. Математическое ожидание. Парадокс дней рождения.
- Продвинутые структуры данных. Дерево отрезков (segment tree), дерево Фенвика (fenwick tree). Разреженная таблица (sparse table). Корневая декомпозиция (sqrt decomposition). Алгоритм МО (корневая декомпозиция запросов). Дерамида.
- Основы теории игр. Ретроспективный анализ. Ним, теорема Шпрага-Гранди.
Источник: РТУ МИРЭА
