Детский технопарк РТУ МИРЭА «Альтаир» открывает набор в клуб по спортивному программированию для учащихся 9–10-х классов, владеющих базовыми навыками программирования.
Занятия проводятся БЕСПЛАТНО и будут проходить 1 раз в неделю по субботам, с 15:00.
Длительность одного занятия – 3 часа.
Начало курса — декабрь 2020 года. Длительность обучения — 2 года.
Участники клуба готовятся к успешному выступлению на олимпиадах муниципального и регионального уровней, таких как:
● Всероссийская олимпиада школьников по информатике
● Всероссийская олимпиада школьников «Высшая проба» (ВШЭ)
● Олимпиада школьников СПбГУ по информатике
● Технокубок
● Олимпиада школьников «Ломоносов»
● Открытая олимпиада школьников по информатике ИТМО
● Олимпиада Университета Иннополис
● Московская олимпиада школьников по информатике и другие.
Занятия для школьников в рамках предлагаемого курса проводят тренеры сборной РТУ МИРЭА по спортивному программированию, имеющие богатый опыт по подготовке к различным олимпиадам и соревнованиям по программированию.
Для участия в клубе необходимо зарегистрироваться по ссылке и пройти отборочный этап, который состоится 28 ноября в 14:00 в дистанционном формате.
Рекомендуемые начальные знания:
1. Типы данных, переменные, константы
2. Инструкции ветвления
3. Инструкции циклов
4. Массивы, в том числе многомерные
Задачи будут разбираться преимущественно на C++, иногда на Python.
Список простых задач олимпиадного формата, которые можно использовать для самопроверки:
● https://acmp.ru/index.asp?main=task&id_task=25
● https://acmp.ru/index.asp?main=task&id_task=539
● https://acmp.ru/index.asp?main=task&id_task=529
● https://acmp.ru/index.asp?main=task&id_task=43
● https://acmp.ru/index.asp?main=task&id_task=715
● https://acmp.ru/index.asp?main=task&id_task=642
● https://acmp.ru/index.asp?main=task&id_task=357
● https://acmp.ru/index.asp?main=task&id_task=46
В чём ценность данного курса?
· Фундаментальные знания. Безусловно, владение навыками программирования на сегодняшний день является значительным конкурентным преимуществом на рынке труда. Тем не менее, в случае конкуренции в среде программистов владение основными навыками программирования, которое обычно развивается сначала в школе, а затем в университете, не является отличительной чертой. Существенными факторами становятся знания в области конкретных технологий (фреймворков, наборов инструментов, заточенных под выполнение определённых задач) и углублённые знания алгоритмов, структур данных и умение их применять в прикладных задачах. И если конкретные технологии и фреймворки меняются каждый год, то алгоритмы и структуры данных, лежащие в основе разработки эффективных программ, остаются неизменными. Именно поэтому изучение данных подходов и закрепление соответствующих навыков при помощи решения олимпиадных задач является лучшей инвестицией среди прочих на пути становления ценного специалиста в сфере разработки программного обеспечения.
· Перспективы углублённого обучения. Для тех ребят, которые в будущем планируют продолжить учёбу в РТУ МИРЭА, данный курс позволит получить необходимые навыки для участия в студенческой сборной университета по спортивному программированию.
Это сообщество активных студентов, которым интересно решать сложные алгоритмические задачи под руководством тренеров. Получить углублённые знания здесь могут как начинающие олимпиадники, так и более опытные и сильные алгоритмисты. Наиболее активным студентам университет оплачивает участие в различных сборах по спортивному программированию. Студенты, которые занимаются в составе сборной, демонстрируют высокие достижения на различных соревнованиях. Только за последнее время ребята вышли в полуфинал Международного студенческого чемпионата мира по программированию, стали призёрами и победителями на финальном чемпионате по алгоритмическому программированию в рамках международного фестиваля RuCode 2020, успешно выступили на сборах по алгоритмическому программированию и ИИ Discover World 2020. Больше информации о сборной в сообществе.
Содержание курса
1. Формальное описание задач и проектирование алгоритмов. Формулировка задачи на языке математики, выделение числовых характеристик задачи и описание связей между ними. Проектирование алгоритма, решающего поставленную задачу.
2. Целочисленная и модульная арифметика. Основы теории чисел. Перебор делителей числа. Алгоритм проверки на простоту. Решето Эратосфена. Алгоритм Евклида. Расширенный алгоритм Евклида. Свойства колец и полей. Быстрое возведение в степень. Нахождение обратного по модулю.
3. Комбинаторика и вероятность. Число сочетаний. Треугольник Паскаля и его свойства. Дискретные случайные величины. Геометрическое и биномиальное распределение. Парадокс дня рождения.
4. Одномерные массивы и последовательности. Сортировка с помощью кучи. Быстрая сортировка. Бинарный поиск. Сортировка за линейное время. Медианы и порядковые статистики.
5. Жадные алгоритмы. Размен монет. Выбор заявок.
6. Алгоритмы на строках. Палиндромы. Поиск подстрок. Алгоритм Кнута-Морриса-Пратта.
7. Рекурсия, перебор. Рекуррентные соотношения. Ханойские башни. Синтаксический анализ арифметических выражений. Все подпоследовательности.
8. Двумерные массивы. Матрицы. Умножение матриц. Алгоритм Штрассена. Обращение матрицы.
9. Динамическое программирование. Задача о порядке перемножения матриц. Наибольшая общая подпоследовательность.
10. Геометрия. Свойства отрезков. Поиск пересекающихся отрезков. Построение выпуклой оболочки. Пара ближайших точек.
11. Основы теории графов. Поиск в ширину. Поиск в глубину. Топологическая сортировка.
12. Структуры данных. Множества и словари. Очередь, стек, список. Асимптотическая сложность операций. Преимущества и недостатки, реализация. Стандартная библиотека.
13. Задача одномерной оптимизации. Метод дихотомии. Метод золотого сечения.
Примеры задач, которые не должны вызывать трудностей у выпускников клуба:
● http://acmp.ru/index.asp?main=task&id_task=118
● https://acmp.ru/index.asp?main=task&id_task=151
● https://acmp.ru/index.asp?main=task&id_task=161
● https://acmp.ru/index.asp?main=task&id_task=421
● https://acmp.ru/index.asp?main=task&id_task=427
● https://acmp.ru/index.asp?main=task&id_task=16
