Принципы подбора задач для олимпиад

Цели олимпиад по программированию:

· выявить на ранней стадии одаренных детей для того, чтобы можно было продолжать работу с ними в дальнейшем в ВУЗах;

· для школьников же наличие элемента соревновательности, стимулирует их дальнейший интерес в области программирования и самоутверждения.

При проведении олимпиады по программированию нужно выявить три фактора у участника олимпиады:

1. умение квалифицированной работы на компьютере,

2. усвоение технологии программирования,

3. уровень алгоритмического мышления.

Технология программирования содержит следующие этапы:

1. Определение технического задания,

2. Алгоритмизация,

3. Выбор языка программирования,

4. Выбор структуры данных,

5. Описание алгоритма,

6. Оптимизация (глобальная, локальная, техническая),

7. Подготовка отладки,

8. Подготовка тестов,

9. Программирование,

10. Тестирование и отладка,

11. Документирование.

При определении уровня освоения технологии программирования появляется необходимость выделения двух туров:

1) теоретического тура, который может содержать 2,3,4,5,9 и 10 этапы технологии программирования,

2) практический тур на ЭВМ, который может содержать со 2-го по 11 этапы.

На олимпиаде можно проверить следующие способности:

· разработка эффективного алгоритма;

· методы программирования конкретного алгоритма на языке программирования;

· программирование данного алгоритма;

· отладка программы;

· тестирование программы;

· модификация существующей программы.

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

Предварительно оценим технические возможности ученика при написании и отладке 4-5 программ на олимпиаде. Квалифицированная машинистка при наборе текста в течении рабочего дня набирает около 25 страниц текста. За полдня около 12. Таким образом, в среднем объем текста, одной решенной задачи, не более 2 страниц.

Олимпиадная задача для ученика состоит из трех компонент:

1. Условие задачи (легенда), которое для восприятия обычно по объему не превышает 1/3 страницы. По структуре для улучшения контроля результата решения определяется формат входных и выходных данных и для уточнения условия задачи предлагаются примеры по условию задачи с ожидаемыми правильными ответами,

2. решение задачи, которое, исходя из возможности записи текста ученика, не должна превышать 2-х страниц,

3. ответ, полученный в результате работы программы участника олимпиады.

При работе жюри на олимпиаде если участвует свыше 70 учеников и они пишут текст около 8 страниц, то набирается свыше 500 страниц текста. Если все члены жюри будут просматривать при проверке все работы, то необходимо только прочтение работ одним человеком займет несколько дней. Поэтому эту работу необходимо разделить по членам жюри, Возможны различные способы разделения:

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

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

В данном случае наиболее приемлем второй подход. При этом подходе обеспечивается сокращение проверяемого текста решения задач до 120-150 страниц.

Этот подход при внимательном изучении работ и оценке результата требует также много времени.

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

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

Для того, чтобы этот метод сработал более эффективно, необходимо разноплановость решаемых задач, чтобы каждая задача была трудной для большей части участников и разных групп участников. Тогда число наиболее вероятных претендентов будет около 1/10 или наиболее внимательно надо будет анализировать около 15-20 страниц текста решения задач, что уже более реально.

Для облегчения контроля ответов введем понятие F-простой задачи в данной теории Т.

Определение: Пусть задана теория Т. Задача Z называется F-простой задачей в теории Т, если длина записи условия задачи Z -короткая и ответ задачи имеет короткую длину записи.

Набор олимпиадных задач по математике или по физике имеет обычно свойство F-простоты.

Это свойство F-простоты олимпиадных задач позволяет членам жюри легко отсекать участников олимпиады, не решивших задачу, по полученному ответу. Основное внимание уделяется только небольшой группе участников олимпиады, у которых имеются правильные ответы, и только среди них удается более четко провести ранжирование участников по местам. Остальная же группа участников олимпиады очень грубо оценивается и полученое ранжирование плохо отражает реальную расстановку мест в середине таблицы. При оценке методов решения в основном учитывается только наличие метода решения и многие технические погрешности игнорируются.

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

При оценке решения задач по программированию важную роль играют два фактора:

— правильноcть решения данной программой поставленной задачи;

— метод решения задачи.

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

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

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

Организаторы современных олимпиад, начиная с городского уровня, стараются, используя задачи из класса F-простых, автоматизировать проверку работ участников олимпиад. Процесс проверки и оценки предъявленных работ сводится к сумме баллов полученным по пройденным тестам. И работа жюри сводится к разработке системы тестов и их ценности.

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

Данный подход имеет два недостатка:

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

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

Для использования в олимпиадах с данными требованиями к работе жюри наиболее подходящими и многократно опробованными являются следующие классы задач:

—определение задачи, решаемой заданной программой;

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

—задачи – фильтры, которые позволяют организовать быстрое тестирование правильности программы;

—алгоритмические задачи, которые не имеют аналитического решения но решаются алгоритмически;

и т.п.