III. Разработка комплектов олимпиадных задач для муниципального/межлицейского этапа

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

Для учащихся 9―11 классов проводится муниципальный этап олимпиады. Далее участники муниципального этапа, набравшие необходимое для участия в заключительном этапе олимпиады количество баллов, установленное организатором заключительного этапа олимпиады, принимают участие в заключительном этапе олимпиады.

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

Олимпиада проводится в один тур, продолжительность тура муниципального этапа составляет 235 минут.

Муниципальный этап олимпиады проводится с использованием автоматической тестирующей системы, как правило, той же, что будет использоваться на заключительном этапе в Донецкой Народной Республике.

Для проведения олимпиады используются задания по программированию с использованием универсальных языков, таких, как Pascal, Python, C/С++.

В вариант муниципального этапа включают 4―6 заданий различной тематики и различного уровня сложности. Первая задача должна быть доступна практически всем участникам олимпиады, далее сложность заданий должна возрастать. Сложность последней задачи должна быть такой, чтобы её решали участники уровня победителя соответствующего этапа олимпиады.

При составлении варианта, с одной стороны, не рекомендуется включать задачи, требующие знания специфических алгоритмов, например алгоритмов на графах, алгоритмов на строках, алгоритмов динамического программирования. В любом случае не следует включать более 1―2 таких задач, они должны быть максимальными по сложности; помимо таких задач, в комплект должно входить не менее 4 задач, не требующих знания специфических алгоритмов.

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

Олимпиады по Информатике и ИКТ за свою историю прошли свой путь развития, в результате чего сформировалась определенная проблематика, методика проведения и проверки (тестирования). Неизменным всегда оставалось одно: суть задания по Информатике и ИКТ заключается в том, чтобы придумать достаточно эффективный алгоритм для решения в общем случае поставленной задачи и реализовать этот алгоритм в виде программы на одном из распространенных языков программирования. В настоящее время на олимпиаде по Информатике и ИКТ в Донецкой Народной Республике участникам предлагаются языки Pascal, C/C++, Python.

Учитывая это, можно сформулировать основные требования к знаниям, умениям и навыкам участника олимпиады по информатике.

Участник должен знать:

1) методы построения алгоритмов;

2) один из предлагаемых языков программирования;

3) одну из сред разработки для выбранного языка программирования;

4) проверяющую систему, на которой проводится соответствующий этап олимпиады.

Участник должен уметь:

1) прочесть и понять условие задачи (условия записываются на русском языке, но важно точно понимать написанное и не домысливать чего-либо еще, о чем в условии не сказано явно);

2) формализовать поставленную задачу, определить, что в ней является входными и выходными данными (аргументами и результатами);

3) выбирать наиболее подходящие структуры данных для хранения данных, которые будут использованы при решении;

4) составлять алгоритм решения формализованной задачи;

5) оценивать вычислительную сложность составленного алгоритма;

6) записывать программу на одном из предлагаемых языков программирования;

7) тестировать и отлаживать набранную программу;

8) отправлять код программы-решения для проверки в проверяющую систему.

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

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

Также для подготовки к олимпиаде по информатике целесообразно прорешивать задания соответствующего этапа Республиканских олимпиад прошлых лет, а также имеющиеся Интернет-ресурсы (online-judge-архив – архивы с задачами, которые обеспечивают возможность онлайн-проверки этих задач, а также сайты, на которых с определенной периодичностью проводятся онлайн-соревнования). Только решая задачи в условиях, приближенных к олимпиадным, можно закрепить знания и выработать навыки, которые необходимы для успешного участия в олимпиадах по информатике.

3.1. Перечень вопросов для подготовки к муниципальному/межлицейскому этапу олимпиады

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

Участник должен знать:

• методы анализа правильности алгоритма;

• позиционные системы счисления;

• понятие вычислительной и емкостной сложности алгоритма;

• способы построения и определения в языке программирования сложных структур данных;

• определение рекурсивных функций;

• методы оптимизации кода программы.

Участник должен уметь:

• сравнивать различные алгоритмы и методы обработки структур данных по их производительности;

• анализировать результаты выполнения алгоритмов, собственные ошибки при выполнении задач;

• тестировать и отлаживать алгоритмы и программы;

• работать с проверяющей системой (отправка решений, получение и учет результата проверки);

• использовать метод динамического программирования с функцией от 1 параметра.

Основные структуры данных:

• массив;

• список;

• стек;

• очередь;

• двухсторонняя очередь;

• куча;

• множество.

Современное содержание олимпиадной информатики:

· Математические основы информатики.

· Разработка и анализ алгоритмов.

· Основы программирования.

· Средства ИКТ.

· Операционные системы.

· Основы технологии программирования.

· Методы вычислений и моделирование.

· Компьютерные сетевые технологии.

Классификация олимпиадных задач по темам:

• Комбинаторика.

• Сортировка и поиск.

• Обработка последовательностей.

• Перебор вариантов и методы его сокращения.

• Алгоритмы на графах.

• Динамическое программирование.

• Элементы вычислительной геометрии.

• Задачи на технику программирования.

• Задачи на идею.

Основные алгоритмы:

• перевод чисел из одной системы счисления в другую;

• расширенный алгоритм Евклида: решение диофантовых уравнений, восстановление числа по остаткам;

• двоичный поиск;

• метод двух указателей (слияние двух упорядоченных массивов);

• эффективные методы сортировки (пирамидальная, слияниями, быстрая сортировка);

• особые случаи сортировки (сортировка подсчетом, цифровая (поразрядная) сортировка);

• нахождение медианы (порядковых статистик);

• длинная арифметика (сложение, вычитание многозначных чисел, умножение многозначного числа на однозначное);

• вычисление расстояния между точками;

• вычисление углов между векторами;

• проверка принадлежности точки прямой, вычисление расстояния от точки до прямой;

• проверка пересечения двух отрезков;

• позиционирование точки относительно многоугольника;

• вычисление площади многоугольника;

• рекурсивный перебор с возвратом;

• подсчет количества комбинаторных объектов.

Примерная программа по олимпиадной информатике Республиканских олимпиад школьников

Примерная программа по олимпиадной информатике Республиканских олимпиад школьников построена с учетом Государственного образовательного стандарта по предметам «Информатика» и «Информатика и ИКТ», а также на основе структуры современного содержания олимпиад по Информатике и ИКТ. Программа является примерной, она отражает постоянно растущие требования к участникам олимпиады в освоении наиболее важных разделов информатики с учетом развития олимпиадного движения, и обобщает многолетний опыт развития содержания курса школьной Информатики, банка задач муниципальных/межлицейских и заключительных этапов Республиканской олимпиады школьников, разработанных предметно-методической комиссией по Информатике и ИКТ.

Не следует рассматривать данную программу как совокупность знаний и умений, необходимых для победы в олимпиадах по Информатике и ИКТ. Путь к наивысшим достижениям на олимпиадах по Информатике и ИКТ является эволюционным и включает несколько этапов. Наивысшие достижения могут проявляться учениками на разных этапах олимпиады, однако следует учитывать, что сильнейшие учащиеся устойчиво показывают наивысшие достижения в группе 9-11 классов только в случае, если они использовали точку входа в олимпиады уже в 5-6 классах. Каждый из этапов характеризуется своим уровнем сложности. Постепенно осваивая каждый такой уровень и переходя с одного уровня на другой, только так можно подняться на вершину олимпиадной пирамиды и стать лучшим из лучших.

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

Представленная ниже примерная программа по олимпиадной информатике содержит восемь разделов, которые раскрываются входящими в них темами. Каждая тема, в свою очередь, содержит дидактические единицы, более подробно раскрывающие ключевые знания и умения, позволяющие для каждого школьника выстроить индивидуальную траекторию подготовки к олимпиадам по Информатике и ИКТ. С учетом сказанного программа будет выглядеть следующим образом.