Введение в олимпиадное программирование [2022] [Высшая инженерная школа СПбПУ] [Елена Крылова, Лев Стояновский]

Введение в олимпиадное программирование [2022]
Высшая инженерная школа СПбПУ (Санкт-Петербургский Политехнический Университет)
Елена Крылова, Лев Стояновский

Спортивное программирование – особый вид деятельности, увлекательный и азартный. Олимпиады по программированию бывают индивидуальными и командными, бывают официальными, дающими льготы при поступлении в ВУЗ, и совсем «домашними».

Главное отличие олимпиадного программирования от обычного – необходимость быстро анализировать многословные условия задач, выбирать из обширного набора решаемые, добиваться верного результата любыми средствами.

Что нужно для успеха? Прежде всего, умение читать задачу, увидеть в её описании путь к решению. Затем – опыт программирования, уверенное владение синтаксисом языка и инструментами отладки. Далее – знание стандартных приёмов решения задач, классических алгоритмов. И наконец, воля, внимание, стрессоустойчивость, умение работать и в команде, и самостоятельно.

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

Теоретический материал излагается преимущественно на алгоритмическом языке. Языками практических заданий являются С++, Visual Basic, Pascal, Python, C# и Java (учащийся может работать на любом из этих языков). Практики существенно больше, чем теории. Чередуется командная и индивидуальная работа.

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

Стилистика курса – креативность, соревновательность, сотрудничество.

Спортивное программирование - увлекательная и азартная интеллектуальная игра, а преуспевшие в ней могут добыть неплохие бонусы при поступлении в ВУЗы. Курс знакомит с правилами олимпиад, учит читать условие задачи, оценивать её сложность, планировать тактику, организовывать работу команды. Цель - дать старт дальнейшему саморазвитию ученика, обеспечив его необходимыми начальными знаниями и опытом. Курс для тех, кто уже умеет программировать.

Курс адресован школьникам 9-10 классов, уже владеющих навыками структурного и процедурного программирования.

В результате обучения учащиеся получат следующие знания, умения и навыки:
1. Навыки работы с системами автопроверки, применяемыми на олимпиадах по программированию.
2. Навыки анализа объёмных постановок задач, примерной оценки сложности решения.
3. Умение использовать в программировании математические знания, анализировать свойства чисел.
4. Умение организовывать структурированные данные, размер которых определяется в ходе работы программы.
5. Навыки оценки вычислительной сложности алгоритма, объёма используемой при его реализации памяти.
6. Знания некоторых стандартных алгоритмов, часто применяемых в спортивном программировании.
7. Навыки организации командной работы на олимпиаде.
8. Оперативная информация о доступных олимпиадах по спортивному программированию, их особенностям и правилам.

Спойлер: Содержание

Занятие 1 - Введение

• Особенности спортивного программирования.
• Олимпиады по программированию: виды, правила, способы оценки ответов.
• Примеры задач.
• Способы организации ввода и вывода, применяемые на олимпиадах.
• Оценка начального уровня учащихся – индивидуальная мини-олимпиада.

Занятие 2 - Искусство выбора решаемой задачи

• Примеры олимпиадных пакетов задач.
• Техника работы с условием задачи.
• Тренинги (индивидуальные и командный) по оценке сложности задач.

Занятие 3 - Математика в программировании

• Примеры задач, где решение находится математически проще, чем программно.
• Краткая сводка полезных программисту сведений из математики.
• Решение задач.
• Командный тренинг.

Занятие 4 - Основные типы данных

• Числовые типы данных, их возможности и особенности.
• Символы и строки.
• Работа со «слишком большими числами».
• Стандартные действия по анализу свойств чисел.
• Командный тренинг – решение задач на технику работы с числами.

Занятие 5 - Использование больших объёмов данных

• Массивы. Организация динамических массивов.
• Полезные алгоритмы, связанные с массивами.
• Проблема ограничений по памяти при олимпиадном программировании.
• Обзор специализированных типов данных (стеки, списки) и инструментов для их реализации.
• Индивидуальный тренинг – технически сложные задачи.

Занятие 6 - Перебор вариантов как метод поиска решения

• Способы организации перебора.
• Простой перебор с параметром, с заданным числом параметров.
• Индуктивный перебор: генерация варианта на основе предыдущего.
• Индивидуальный тренинг.

Занятие 7 - Перебор вариантов как метод поиска решения (продолжение)

• Рекурсия как способ организации перебора.
• Альтернативы рекурсии.
• Эффективность по времени, примеры.
• Командный тренинг с выбором задач из большого набора.

Занятие 8 - Тестирование программы. Организация работы команды

• Тестовые данные в олимпиадном программировании.
• Самотестирование программы. Типы тестовых данных в зависимости от способа оценки результатов.
• Варианты распределения ролей в команде.
  
• Командный тренинг - тактический разбор пакета заданий реальной олимпиады.

Занятие 9 - Оптимизация поиска решения

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

Занятие 10 - Графы и деревья

• Примеры задач, моделируемых посредством графов.
• Способы представления графов в программе.
• Обзор некоторых алгоритмов, связанных с графами.
• Решение задач

Занятие 11 - Командная олимпиада по программированию

Занятие 12 - Разбор заданий командной олимпиады

Индивидуальная олимпиада по программированию – экзамен

Продажник