ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ
В.М. Кирюхин
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ
по разработке заданий для школьного и муниципального этапов Всероссийской олимпиады школьников по информатике
в 2009/2010 учебном году
Москва 2009 г.
ОГЛАВЛЕНИЕ
Введение …………………………………………………………..…….…..… 3
1. Порядок и форма проведения школьного и муниципального этапов Всероссийской олимпиады школьников по информатике …….…......... 4
1.1. Порядок организации школьного и муниципального этапов ….….. 4
1.2. Форма проведения школьного и муниципального этапов ………… 6
1.3. Правила проведения школьного и муниципального этапов ………. 9
2. Общая характеристика задач для школьного и муниципального этапов ……………….…………………………………………….……… 12
2.1. Критерии отбора олимпиадных задач ……………………….……. 12
2.2. Общая характеристика содержания олимпиадных задач ………... 14
2.3. Порядок разработки оригинальных олимпиадных задач ……..…. 17
2.4. Требования к решениям задач участников ……………………….. 19
3. Рекомендации по проверке и оцениванию решений участников ……. 22
3.1. Методика проверки решений задач участников ……….…………. 22
3.2. Система оценивания решений участников ………………….…….. 24
3.3. Технология проверки решений участников ………………………. 27
4. Организация рабочего места участников школьного и муниципального этапов ……………………………………………………….……………. 34
Список рекомендуемой литературы ………………………………………. 40
Введение
Настоящие методические рекомендации подготовлены центральной предметно-методической комиссией по информатике и направлены на помощь муниципальным и региональным методическим комиссиям в составлении заданий для школьного и муниципального этапов Всероссийской олимпиады школьников по информатике в субъектах Российской Федерации.
Методические материалы содержат рекомендации по порядку и форме проведения олимпиад по информатике, требования к структуре и содержанию олимпиадных задач, рекомендуемые источники информации для подготовки задач, а также рекомендации по оцениванию решений участников олимпиад.
Центральная предметно-методическая комиссия по информатике выражает надежду, что представленные методические рекомендации окажутся полезными при проведении школьного и муниципального этапов Всероссийской олимпиады школьников по информатике, и желает успехов организаторам в их проведении. В случае необходимости, дополнительную информацию по представленным методическим материалам можно получить по электронной почте, обратившись по адресу support@rusolymp.ru в центральную предметно-методическую комиссию по информатике.
Настоящие методические рекомендации утверждены на заседании Центральной предметно-методической комиссии (протокол № 5 от 15 июля 2009 года).
Председатель центральной
предметно-методической комиссии
по информатике В.М. Кирюхин
1. Порядок и форма проведения школьного и муниципального этапов Всероссийской олимпиады школьников по информатике
При организации и проведении школьного и муниципального этапов Всероссийской олимпиады школьников по информатике необходимо руководствоваться Положением о Всероссийской олимпиаде школьников, утвержденным Приказом Минобрнауки России от 22 октября 2007 г. № 286, а также нормативными документами, регламентирующими проведение Всероссийской олимпиады школьников в 2009-2010 учебном году (все документы представлены на портале Всероссийской олимпиады школьников http://rusolymp.ru в разделе «Нормативные документы»).
1.1.
Порядок организации школьного и муниципального этапов
Организаторами школьного и муниципального этапов олимпиады по информатике являются соответственно образовательные организации и органы местного самоуправления муниципальных и городских округов в сфере образования.
Организаторы школьного этапа должны обеспечить участие в этом этапе любого школьника, который изъявил желание в нем участвовать. Никаких ограничений на количественный состав участников школьного этапа со стороны Положения о Всероссийской олимпиаде школьников нет.
Для проведения школьного и муниципального этапов олимпиады организатором соответствующего этапа создаются оргкомитет и жюри. Оргкомитет обеспечивает общую организацию соревнований и соблюдение утвержденных регламентов, выделяет необходимые для этого помещения, оборудованные соответствующими компьютерами и техническими средствами, обеспечивает установку на компьютерах нужного программного обеспечения, рассматривает конфликтные ситуации, возникшие при проведении соревнования, оформляет дипломы победителей и призеров олимпиады, осуществляет необходимую информационную поддержку.
Жюри школьного или муниципального этапа олимпиады, которое создается на время проведения соревнования, осуществляет проверку и оценку решений олимпиадных заданий, проводит с участниками разбор олимпиадных заданий и анализ полученных решений участников, рассматривает совместно с оргкомитетом школьного этапа Олимпиады апелляции, формирует список победителей и призеров, а также представляет в оргкомитет соответствующего этапа олимпиады аналитические отчеты о результатах проведения этого этапа.
Форма проведения и техническое обеспечение школьного этапа Олимпиады определяются муниципальной предметно-методической комиссией по информатике, формируемой органом местного самоуправления муниципальных и городских округов в сфере образования. В свою очередь, форма проведения и техническое обеспечение муниципального этапа олимпиады определяются региональной предметно-методической комиссией по информатике, формируемой органом государственной власти субъекта Российской Федерации в сфере образования. В своей работе эти комиссии руководствуется настоящими методическими рекомендациями.
В соответствии с Положением о Всероссийской олимпиаде школьников школьный этап олимпиады проводится по олимпиадным заданиям, разработанным предметно-методической комиссией муниципального этапа олимпиады, а муниципальный этап - по олимпиадным заданиям, разработанным региональной предметно-методической комиссией. С учетом этого предметно-методические комиссии должны предоставить жюри соответствующего этапа следующий комплект материалов:
· тексты олимпиадных задач;
· общие методические рекомендации по проверке решений участников;
· комплекты тестов в электронном виде, содержащие для каждой задачи файлы входных данных и соответствующие им файлы выходных данных;
· систему оценки результатов прохождения каждого теста и комплекта тестов в целом;
· краткие методические рекомендации по решению предложенных олимпиадных задач.
В случае необходимости, предметно-методическая комиссия соответствующего этапа предоставляет также дополнительные материалы, необходимые для автоматизированной проверки решений участников, включая проверяющие программы, позволяющие для каждой задачи определять правильность полученного решения в автоматическом режиме.
Подведение итогов школьного и муниципального этапов центральная предметно-методическая комиссия рекомендует осуществлять отдельно по классам. Количество победителей и призеров по каждому классу на школьном и муниципальном этапах определяется исходя из квоты, установленной организатором муниципального или регионального этапа соответственно. Никаких ограничений на эти квоты Положение о Всероссийской олимпиаде школьников не накладывает.
При определении названных квот следует руководствоваться следующим принципом: все наиболее сильные участники школьного этапа должны принять участие в муниципальном этапе, а наиболее сильные участники муниципального этапа – в региональном этапе. Устанавливать одинаковые и небольшие квоты для всех учреждений образования или муниципальных образований не целесообразно, так как состав участников следующего этапа формируется только из числа победителей и призеров предыдущего этапа, а отдельные учреждения образования или муниципальные образования по силе участников могут существенно отличаться друг от друга.
1.2.
Форма проведения школьного и муниципального этапов
Форма проведения и техническое обеспечение школьного и муниципального этапов олимпиады определяются соответственно муниципальной и региональной предметно-методической комиссией по информатике с учетом настоящих рекомендаций.
Центральная предметно-методическая комиссия по информатике рекомендует проводить школьный и муниципальный этапы в один или два компьютерных тура. Длительность тура не должна превышать пяти астрономических часов. Если школьный или муниципальный этап проводится в два тура, то между турами желательно предусмотреть один день отдыха, и все участники должны быть допущены к участию в обоих турах.
По усмотрению организаторов и жюри школьного и муниципального этапов перед началом олимпиады для всех участников может быть организован пробный тур, основное назначение которого – знакомство участников с компьютерной техникой и установленным на рабочих местах программным обеспечением, а также с Памяткой участнику, которая подготавливается жюри соответствующего этапа перед началом соревнований. Пробный тур из рекомендательного должен стать обязательным, если во время проведения соревнований участники должны использовать в процессе решения задач специализированную программную среду, позволяющую осуществлять проверку решений участников в автоматическом режиме.
Количество олимпиадных задач, предлагаемых участникам на школьном или муниципальном этапе, определяется предметно-методической комиссией соответствующего этапа. Рекомендуемое центральной предметно-методической комиссией количество задач на туре – три или четыре. Задачи должны быть такой сложности, чтобы дать возможность проявить себя как недостаточно подготовленным, так и сильным участникам. Здесь важно не отпугнуть учащихся сложностью задач, а дать им возможность за ограниченное время продемонстрировать свои лучшие качества и создать атмосферу соревновательности, характерную для всех этапов олимпиады.
Комплекты задач для школьного или муниципального этапа могут разрабатываться соответствующими предметно-методическими комиссиями отдельно как для каждой параллели, так и для некоторых параллелей, например, для 9 – 11 классов. Это определяется существующими в субъекте РФ традициями при проведении всероссийской олимпиады школьников по информатике в отдельных школах и муниципальных образованиях. Главное здесь – отобрать действительно лучших школьников из каждой параллели, допустимой Положением о Всероссийской олимпиаде школьников.
Центральная предметно-методическая комиссия по информатике рекомендует на школьном этапе предлагать всем учреждениям образования соответствующего муниципального образования одни и те же комплекты задач для выделенных параллелей. Аналогично и для муниципального этапа: комплекты задач для выделенных параллелей должны быть одинаковыми для всех муниципальных образований соответствующего субъекта РФ. Это даст возможность предметно-методическим комиссиям наиболее квалифицированно подойти к подготовке олимпиадных задач, минимизировать затраты на их подготовку и проверку, а также оценить результаты выступления участников по единым критериям.
При проведении школьного или муниципального этапов олимпиады организаторы соответствующего этапа должны принять все необходимые меры для предотвращения преждевременного доступа к текстам задач со стороны участников олимпиады, а также их учителей и наставников. В этой связи, время начала соревнований в учреждениях образования на школьном этапе и в муниципальных образованиях на муниципальном этапе должно быть таким, чтобы соответствующие участники не смогли преждевременно ознакомиться с условиями олимпиадных задач, которые им будут предложены.
Муниципальные и региональные предметно-методические комиссии по информатике с учетом характера олимпиадных задач, разработанных для соответствующего этапа олимпиады, формируют требования к решениям задач участников, которые заблаговременно доводятся до сведения участников и должны быть отражены в Памятке участнику, подготавливаемой жюри соответствующего этапа.
Рекомендуется в течение как минимум двух часов с момента начала тура (конкретный период определяется жюри соответствующего этапа) предоставить возможность каждому участнику олимпиады задать вопросы членам жюри по условиям задач. Вопросы должны задаваться письменно на заранее подготовленных бланках.
Во время туров следить за выполнением правил проведения соревнований должен специально выделенный оргкомитетом соответствующего этапа персонал. Кроме того, должна быть сформирована техническая группа, которая будет обеспечивать работоспособность используемой во время соревнований компьютерной техники и программного обеспечения.
1.3.
Правила проведения школьного и муниципального этапов
При проведении школьного или муниципального этапа олимпиады по информатике организационный комитет и жюри соответствующего этапа должны обеспечить во время туров соблюдение следующих правил.
1. Каждый участник размещается за выделенным ему рабочим местом в соответствии с планом размещения участников, установленным жюри соответствующего этапа.
2. Перед началом тура все компьютеры участников находятся во включенном состоянии. Участникам строго запрещено трогать компьютер и клавиатуру до начала тура.
3. Каждый участник должен получить доступ к текстам олимпиадных задач только в момент начала тура.
4. Вместе с текстами задач участники могут получить только специально подготовленную жюри памятку, содержащую правила поведения во время тура и инструкцию по работе со специализированной программной средой проведения соревнований, если она используется.
5. Во время туров участникам запрещается пользоваться интернетом, любыми электронными устройствами, в том числе личными компьютерами, калькуляторами, электронными записными книжками, средствами связи (пейджерами, мобильными телефонами и т.п.), электронными носителями информации (дискетами, CD- и DVD-дисками, модулями флэш-памяти и т.п.), а также учебной литературой и заготовленными личными записями.
6. В течение определяемого жюри периода времени с момента начала тура каждый участник может задать вопросы членам жюри по условиям задач и получить на них ответы. Вопросы должны задаваться в письменном виде на подготовленном жюри бланке и формулироваться по возможности так, чтобы ответ был в форме «да» или «нет». Ответы жюри на вопросы участников могут быть следующими: «да», «нет», « см. условие», «без комментариев». Если тот или иной ответ на вопрос какого-либо участника не следует из текста условия задачи в силу его неоднозначности, то ответ на такой вопрос должен быть доведен до сведения всех участников.
7. При использовании во время проведения туров специализированной программной среды, позволяющей осуществлять проверку решений задач в автоматическом режиме, участникам разрешается сдавать свои решения на предварительную проверку во время тура. Предварительная проверка заключается в том, что решения участников проверяются на тестах из условия задачи. Результаты этой проверки по возможности незамедлительно сообщаются участникам. Участники могут несколько раз посылать на предварительную проверку решение одной и той же задачи. Как правило, окончательной проверке после окончания тура подлежит только последнее успешно прошедшее предварительную проверку решение.
8. Во время тура участники имеют право общаться только с представителями жюри или оргкомитета, а также с дежурными преподавателями, находящимися в месте размещения участников.
9. В случае возникновения во время тура не по вине участника сбоев в работе компьютера или используемого программного обеспечения по решению жюри соответствующего этапа время, затраченное на восстановление работоспособности компьютера, может быть компенсировано.
10. За сохранность своих данных во время тура несет ответственность каждый участник. Чтобы минимизировать возможные потери данных на компьютере участника, необходимо своевременно сохранять свои файлы и данные на компьютере.
11. По истечении времени тура участникам запрещается выполнять любые действия на компьютере.
В случае нарушения участником школьного или муниципального этапа олимпиады настоящих правил жюри соответствующего этапа имеет право дисквалифицировать этого участника. Окончательное решение по этому вопросу принимает оргкомитет этого этапа олимпиады.
2. Общая характеристика задач для школьного и муниципального этапов
Задачи для школьного и муниципального этапов олимпиады разрабатывают муниципальные и региональные предметно-методические комиссии по информатике соответственно. Вместе с текстами задач эти комиссии должны передать в распоряжение жюри соответствующего этапа методические материалы, перечисленные в разделе 1.1. Эти материалы должны быть переданы жюри как минимум за 10 дней до начала тура, чтобы жюри смогло в полной мере подготовиться к проведению олимпиады, при этом ответственность за нераспространение этих материалов несет персонально председатель жюри.
2.1. Критерии отбора олимпиадных задач
Для проведения школьного и муниципального этапов Всероссийской олимпиады школьников по информатике могут использоваться как задачи, ранее использованные на других олимпиадах по информатике, так и задачи, разработанные муниципальными и региональными методическими комиссиями. Основными критериями отбора олимпиадных задач должны быть следующие показатели [11]:
· оригинальная формулировка задачи или оригинальная идея ее решения для конкретного состава участников олимпиады;
· в тексте условия задачи не должны встречаться термины и понятия, выходящие за пределы изучаемых в рамках базового учебного плана предметов; в крайних случаях, они должны быть определены или конкретизированы;
· задача должна быть однозначно определена, т.е. в ее формулировке не должно быть неоднозначностей, чтобы участник олимпиады решал именно ту задачу, которую задумали авторы;
· задача не должна требовать для своего решения специальных знаний;
· формулировка задачи должна предполагать наличие этапа формализации при ее решении, т.е. переход от неформальной постановки задачи к формальной;
· задача должна быть разумной сложности и трудоемкости.
При подготовке задач необходимо учитывать, что олимпиадные задачи могут быть трех типов. К задачам первого типа относятся стандартные задачи, решением которых является программа, формирующая по заданному входному файлу выходной файл. Задачи второго типа являются интерактивными. Решением задач этого типа также является программа, однако, в отличие от задач первого типа, вместо чтения исходных данных из входного файла и записи результата в выходной файл эта программа должна обмениваться данными с другой программой, определенной в условии задачи. В задачах третьего типа, которые называются задачами с открытым входом, решением является не программа, как в задачах первого или второго типов, а файлы выходных данных, соответствующие заданным в условии задачи входным файлам.
Разные задачи можно решать с использованием разных языков программирования. Список допустимых языков программирования устанавливается предметно-методической комиссией по информатике соответствующего этапа до начала проведения олимпиады с учетом настоящих рекомендаций.
Для задач, в которых решением является программа, в тексте условия указывается максимальное время работы программы на каждом тесте и размер доступной программе памяти. В случае превышение установленных ограничений, тест должен считаться не пройденным. При этом указанные ограничения по памяти включают всю память, используемую программой, в том числе память под код программы, системные нужды и т.д.
Решение должно выдавать одинаковые ответы на одинаковые тесты, вне зависимости от времени запуска и программного окружения. Жюри вправе произвести неограниченное количество запусков программы участника и выбрать наихудший результат по каждому из тестов.
2.2. Общая характеристика содержания олимпиадных задач
При определении содержания задач для школьного и муниципального этапов олимпиады по информатике основными документами, на которые можно ориентироваться в настоящее время, являются стандарт основного и среднего (полного) общего образования по информатике и ИКТ базового и профильного уровней, а также соответствующие примерные программы, приведенные в книгах [11, 18].
Важной особенностью задач, используемых при проведении школьного и муниципального этапов, является ориентация их на проверку развития у школьников теоретического мышления, логики, а также творческих способностей и интуиции. В отличие от задач ЕГЭ или студенческих олимпиад по информатике, которые, помимо всего прочего, направлены еще и на проверку обученности участников, задачи школьных олимпиад должны предоставлять возможность школьникам без специальных знаний решать нестандартные и новые для них задачи. Каждая задача должна позволять участникам сделать для себя небольшое открытие и в полной мере раскрыть имеющийся у них творческий потенциал.
Олимпиадные задачи для школьного и муниципального этапов олимпиады по информатике должны отличаются тематическим разнообразием. Из опыта проведения таких олимпиад в прошлые годы можно выделить наиболее часто встречающиеся разделы информатики, к которым с определенной долей условности можно отнести тематику той или иной олимпиадной задачи. В частности, такими разделами информатики являются:
· комбинаторика;
· сортировка и поиск;
· обработка последовательностей;
· алгоритмы на графах;
· элементы вычислительной геометрии.
· перебор вариантов и методы его сокращения;
· динамическое программирование;
Олимпиадная задача по информатике должна гармонично покрывать не только теоретические разделы курса информатики, но и давать возможность использовать в процессе ее решения знания и умения, характерные для основных этапов решения задач с помощью компьютеров. В частности, такими этапами являются:
· формализация задачи;
· выбор формального метода и разработка алгоритма решения задачи, включая оценку правильности и сложности алгоритма;
· программирование алгоритма и отладка программы;
· тестирование полученной программы.
Опыт проведения олимпиад по информатике в нашей стране показывает, что содержание и основные знания, умения и навыки, востребованные при решении олимпиадных заданий по информатике, строятся на основе сформированного уровня освоения школьниками содержания информатики и информационных технологий основной школы и развития профильного уровня освоения стандарта среднего образования по информатике [18]. Все представленные там дидактические единицы, в той или иной степени, обязательно заложены в олимпиадных задачах конкретного соревнования. Более того, анализ показывает, что все блоки содержания образования профильного уровня стандарта по информатике, а также требуемые компетентностные качества, в полной мере могут проверяться олимпиадными заданиями.
В частности, можно отметить следующие компетентностные качества, которые выявляются в результате участия школьников в олимпиадном движении:
· углубленные знания математических основ информатики;
· развитые умения и навыки в теории алгоритмов;
· устойчивые знания об информационных процессах, типах информации, способах представления и передачи информации;
· устойчивые практические навыки самостоятельного построения компьютерных моделей;
· расширенные представления о составе компьютера, программном принципе работы компьютера и прикладном программном обеспечении;
· беглое владение клавиатурным вводом на русском и английском языке;
· свободное владение компьютерным графическим интерфейсом;
· устойчивые навыки работы с периферийным оборудованием и разнообразными носителями информации;
· свободные навыки работы с компьютером: файловой системой, операционной системой, архивирующими средствами, конвертирующими средствами, программными приложениями, поисковой системой;
· устойчивые навыки работы с общими и персональными ресурсами в локальной компьютерной сети;
· устойчивые навыки работы со специализированным ПО (среды программирования, трансляторы, отладчики);
· свободные навыки работы с инструментальными средствами глобальной компьютерной сети (регистрация, передача данных, защита информации);
· ясное представление о нормах работы с информацией;
· развитое чувство самоконтроля и ответственности;
· навыки самостоятельного планирования заданий;
· общекультурные навыки организации рабочего места;
· общекультурные навыки этикета;
· проявление волевых качеств.
Очевидно, что чем выше уровень олимпиады, тем сложнее предлагаемые задачи и больший уровень знаний и умений требуется от участников. Но совершенно не правильно считать, что эта сложность возрастает только за счет программирования. Программирование здесь, как и в информатике в целом, играет важную, но не определяющую роль, и названный выше перечень знаний и умений участников в гораздо большей степени охватывает другие многочисленные разделы информатики как науки.
2.3. Порядок разработки оригинальных олимпиадных задач
Разработать олимпиадную задачу по информатике не так просто, особенно если в олимпиаде участвуют достаточно сильные школьники, способные успешно решать задачи для заключительных этапов Всероссийской олимпиады школьников. Хорошая задача – это, как правило, штучный и эксклюзивный продукт, для создания которого необходимо провести даже небольшое исследование.
В общем случае процесс создания олимпиадной задачи включает следующие основные этапы:
1) разработка идеи и подготовка текста условия задачи;
2) разработка различных алгоритмов решения задачи;
3) написание и отладка программ решений на всех разрешенных на олимпиаде языках программирования;
4) подготовка системы оценивания задачи;
5) разработка системы тестов для проверки решения задачи;
6) разработка проверяющей программы для включения ее состав программной проверяющей системы, если таковая используется при проведении олимпиады.
Вполне очевидно, что процесс создания олимпиадной задачи является итерационным. Очень часто случается, что условие задачи может кардинально измениться в зависимости от результатов выполнения последующих этапов.
Что касается разработки задач для школьного и муниципального этапов, то большую помощь в этом могут оказать существующие печатные издания и интернет-ресурсы, содержащие коллекции олимпиадных задач. Причем в качестве основы для разработки олимпиадной задачи могут использоваться даже задачи международных олимпиад. Дело в том, что сложность задач заключительных этапов и международных олимпиад в большинстве случае определяется размерностью задачи. Уменьшив эту размерность, можно получить задачу, которая вполне под силу школьникам, которые только начинают свой путь в олимпиадной информатике.
Если говорить о печатных изданиях, содержащих в достаточном количестве олимпиадные задачи по информатике, то здесь можно порекомендовать книги, перечень которых представлен в списке рекомендуемой литературы. Среди них можно выделить книги издательства «Просвещение» (http://prosv.ru/), непосредственно посвященные всероссийской олимпиаде школьников по информатике [11 – 14] и книги, изданные издательством «БИНОМ. Лаборатория знаний» в рамках библиотечки олимпиадной информатики [7, 8, 17, 22 – 25, 29] (http://metodist.lbz.ru).
Среди интернет-ресурсов полезными при разработке олимпиадных задач для школьного и муниципального этапов являются следующие сайты:
http://info.rusolymp.ru/ (сайт с наибольшей в России коллекцией задач международных и всероссийских олимпиад по информатике с методическими рекомендациями по их решению);
http://algolist.manual.ru/olimp/ (сайт «Олимпиадные задачи по программированию»);
http://www.olympiads.ru/moscow/ (сайт московских олимпиад по информатике);
http://neerc.ifmo.ru/school/russia-team/archive.html (сайт с архивом задач Всероссийских командных олимпиад школьников по программированию);
http://contest.ur.ru (сайт Уральских олимпиад по информатике);
http://www.olympiads.ru/ (сайт по олимпиадной информатике);
http://www.olympiads.nnov.ru/ (сайт «Олимпиадная информатика в Нижнем Новгороде»);
http://acmp.ru" (сайт «Школа программиста» для школьников Красноярского края);
http://acmu.ru (сайт «Олимпиады по информатике (ХМАО- Югра)» для школьников Ханты-Мансийского автономного округа);
http://olimpic.nsu.ru/nsu/archive/2005/index.shtml (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина);
http://imcs.dvgu.ru/works/school.html (сайт школьных олимпиад, проводимых в Приморском крае);
http://olymp.karelia.ru/pract.htm (сайт школьных олимпиад Республики Карелия);
http://school.sgu.ru/ (сайт по алгоритмизации и программированию Саратовского государственного университета).
Можно также воспользоваться сайтами, которые содержат не только коллекции олимпиадных задач, но и обеспечивают возможность проверки решений представленных там задач. К таким сайтам относятся:
http://acm.timus.ru/ (сайт Уральского государственного университета, содержащий большой архив задач с различных соревнований по спортивному программированию);
http://informatics.mccme.ru (сайт дистанционной подготовки по информатике Московского института открытого образования и МЦНМО);
http://acm.sgu.ru (сайт Саратовского государственного университета, содержащий архив задач с системой онлайн-проверки).
2.4. Требования к решениям задач участников
Решения задач должны сдаваться участниками школьного и муниципального этапов олимпиады на проверку только на электронном носителе. В зависимости от типа задачи ее решением может быть либо текст программы, написанной с использованием допустимых сред программирования (для стандартных и интерактивных задач), либо набор выходных файлов, соответствующих заданным входным файлам (для задач с открытым входом), о чем должно сообщаться в условии задачи.
Разные задачи можно решать с использованием разных языков программирования.
Если решением задачи является программа и для проверки решений участников используется программная среда проведения соревнований, то ее компиляция в проверяющей системе осуществляется с помощью команды компиляции, соответствующей выбранному участником языку программирования. Таблица команд компиляции должна быть доведена до сведения всех участников перед началом каждого тура и содержаться в памятке участнику.
Для задач, решением которых является программа, в тексте условия рекомендуется указывать максимальное время работы программы и размер доступной программе памяти. Временем работы программы считается суммарное время работы процесса на всех ядрах процессора. Память, используемая приложением, включает всю память, которая выделена процессу операционной системой, включая память кода и стек.
Для программ-решений рекомендуется также использовать следующие ограничения: размер файла с исходным текстом программы не должен превышать 256 Кбайт, а время компиляции программы должно быть не больше одной минуты.
Участникам школьного и муниципального этапов олимпиады разрешается использование в решениях задач любых внешних модулей и заголовочных файлов, включенных в стандартную поставку соответствующего компилятора.
В решениях задач участникам запрещается:
• создавать каталоги и временные файлы при работе программы;
• любое использование сетевых средств;
• любые другие действия, нарушающие работу проверяющей системы, если она используется.
Для задач с открытым входом формат выходных файлов должен полностью соответствовать описанным в условии задачи требованиям. При нарушении этих требований выходной файл на проверку не принимается.
Решение в виде программы должно выдавать одинаковые ответы на одинаковые тесты, вне зависимости от времени запуска и программного окружения. Жюри соответствующего этапа олимпиады вправе произвести неограниченное количество запусков программы участника и выбрать наихудший результат по каждому из тестов.
3. Рекомендации по проверке и оцениванию решений участников
Методику проверки и систему оценивания решений задач школьного и муниципального этапов олимпиады предоставляют жюри предметно-методические комиссии соответствующего этапа олимпиады. Все необходимые для этого материалы должны поступить в распоряжение жюри как минимум за 10 дней до начала олимпиады, чтобы члены жюри смогли настроить и проверить работоспособность соответствующего программного обеспечения.
3.1.
Методика проверки решений задач участников
Методика проверки решений каждой олимпиадной задачи зависит от типа этой задачи. Если решением задачи является программа, то оценка правильности ее решения осуществляется путем исполнения программы с входными данными, соответствующими каждому тесту из представленного предметно-методической комиссией соответствующего этапа комплекта тестов с последующим анализом полу
Если решением задачи является программа, то результатом решения таких задач является исходный текст программы на одном из разрешенных языков программирования – Pascal, C, С++, и Visual Basic. Рекомендуемые центральной предметно-методической комиссией по информатике среды программирования, приведены в разделе 4.
Поскольку участники олимпиады должны сдавать на проверку решения в виде исходного текста программы на одном из разрешенных языков программирования, то проверка решений каждого участника должна осуществляться в следующей последовательности:
· компиляция исходного текста программы;
· последовательное исполнение полученного exe-файла для файлов с входными данными, соответствующих тестам из набора тестов для данной задачи, подготовленного предметно-методической комиссией по информатике соответствующего этапа;
· сравнение результатов исполнения программы на каждом тесте с правильным ответом.
При компиляции исходного текста программы, которую участник сдал на проверку, необходимо учитывать следующее.
1) Жюри должно использовать вполне определенные команды компиляции, соответствующие выбранному участником языку программирования. Таблица команд компиляции доводится до сведения всех участников перед началом каждого тура и должна содержаться в Памятке участнику.
2) Желательно учитывать, что размер файла с исходным текстом программы не должен превышать 256 Кбайт. Время компиляции программы не должно превышать одной минуты.
В случае нарушения принятых жюри ограничений решение участника считается неправильным и никакие баллы за эту задачу участнику не начисляются. Информация об этих ограничениях также должна быть размещена в Памятке участнику.
При исполнении программы на каждом тесте, в первую очередь, жюри должно определить, нарушаются ли присутствующие в условии этой задачи ограничения на время работы программы на отдельном тесте и размер доступной программе памяти в процессе ее исполнения. В случае нарушения имеющих место ограничений баллы за этот тест участнику не начисляются.
Если приведенные в условии задачи ограничения не нарушаются в процессе исполнения программы с входными данными, соответствующими конкретному тесту, то после завершения исполнения программы осуществляется проверка правильности полученного ответа. Эта проверка может осуществляться как путем сравнения полученного выходного файла с файлом выходных данных из тестового набора данных, так и с использованием предоставляемых предметно-методической комиссией соответствующего этапа проверяющих программ, если для проверки решений участников предполагается использовать специализированную программную среду соревнований с возможность проверки решений в автоматическом режиме.
Все представленные на проверку решения участников сначала должны проходить предварительное тестирование на тестах из примера или примеров, приведенных в условии задачи. Если на этих тестах решение участника выдает правильный ответ, то тогда это решение принимается жюри на окончательную проверку, которая после завершения соответствующего тура осуществляется на всех тестах из заданного набора тестов для этой задачи. В противном случае, решение участника считается неверным, и за него участнику не начисляются какие-либо баллы.
При проверке решений участников с использованием специализированной программной среды соревнований процесс предварительной проверки осуществляется в течение тура по мере посылки решений на сервер соревнований. В зависимости от возможностей проверяющей системы на окончательную проверку может приниматься либо последнее прошедшее предварительное тестирование решение одной и той же задачи, либо то, которое он должен указать. В любом случае, участник олимпиады должен быть проинформирован до начала тура, каким образом будет определяться решение, принятое проверяющей системой для окончательной проверки. Эту информацию также следует разместить в Памятке участнику.
3.2.
Система оценивания решений участников
Система оценивания решений каждой олимпиадной задачи школьного и муниципального этапов олимпиады должна предоставляться жюри предметно-методической комиссией соответствующего этапа в следующем виде:
1) комплекта тестов для каждой задачи, где каждому тесту соответствует файл с входными данными и файл с соответствующими выходными данными;
2) распределения максимального количества баллов за задачу (как правило, это 100 баллов, если иное не оговорено в условии задачи) между всеми группами тестов и отдельными тестами внутри каждой группы.
Комплекты тестов разрабатываются таким образом, чтобы жюри соответствующего этапа без проблем могло в максимальной степени оценить все возможные типы алгоритмов, которые могут быть использованы в решениях участников и продифференцировать полученные участниками решения по степени их корректности и эффективности. В общем случае в комплекте тестов для каждой задачи выделяются следующие группы тестов:
1) простые тесты;
2) тесты на частные случаи, позволяющие выявить особенности используемых алгоритмов;
3) общие тесты (достаточно случайные тесты, разные по размеру: от простых тестов до сложных);
4) тесты, проверяющие наличие эвристик в алгоритмах;
5) тесты максимальной размерности (тесты с использованием максимальных значений входных переменных, позволяющие оценить эффективность предложенных алгоритмов или их работоспособность при максимальной размерности задачи).
Распределение максимального количества баллов за задачу между всеми группами тестов и отдельными тестами внутри каждой группы представляется в виде таблицы, в которой каждому тесту и группе тестов ставится в соответствие определенное количество баллов. Такое распределение строится следующим образом: сначала максимальное количество баллов за задачу распределяется между всеми группами тестов, а затем между тестами внутри каждой группы.
При распределении максимального количества баллов за задачу между всеми группами тестов учитывается следующий принцип: правильное решение для всех ограничений из условия задачи должно набирать полный балл, в то время как правильное для определенной размерности входных данных, но не эффективное в целом решение задачи, должно набирать ориентировочно 30-70% баллов.
Поскольку каждый тест в группе используется для проверки вполне определенного свойства алгоритма решения задачи, то баллы внутри группы распределяются с учетом важности этого свойства для решения задачи в целом. В случае правильного ответа на тесты из конкретной группы или определенные тесты внутри этой группы участнику начисляется установленное для этой группы или теста количество баллов, в противном случае – нуль баллов.
Общая оценка за решение отдельной задачи конкретным участником складывается из суммы баллов, начисленных ему по результатам исполнения тестов из всех групп тестов для этой задачи. Итоговая оценка проверки решений всех задач олимпиады для каждого участника формируется как сумма полученных этим участником баллов за каждую задачу.
После окончания проверки решений всех участников и до подведения окончательных итогов олимпиады результаты проверки решений каждого участника должны быть доведены до его сведения в обязательном порядке. При возникновении каких-либо претензий по поводу полученных оценок каждый участник имеет право подать апелляцию в жюри соответствующего этапа.
Итоговые результаты проверки решений всех задач заносятся в итоговую таблицу, представляющую собой ранжированный список участников, расположенных по мере убывания набранных ими баллов. Участники с равным количеством баллов располагаются в алфавитном порядке.
3.3.
Технология проверки решений участников
Существуют различные способы проверки решений участников. Если по условию задачи ее решением должна быть программа, то самый простой способ, но в то же время самый трудоемкий, заключается в последовательном запуске проверяемой программы на каждом тесте из заданного комплекта тестов для этой задачи. Для этого способа вполне достаточно иметь для каждого теста файл с входными данными и файл с соответствующими выходными данными. Если учесть, что для каждой задачи эти файлы предоставляются жюри предметно-методической комиссией по информатике соответствующего этапа, то члены жюри вполне могут справиться с задачей проверки решений участников таким «ручным» способом при наличии достаточного количества членов жюри.
Если по условию задачи ее решением является набор выходных файлов, то проверка сданного участником на проверку файла осуществляться путем его сравнения с правильным выходным файлом.
Конечно, описанный способ достаточно трудоемкий, но тот факт, что решения участников сначала проверяются на одном или двух тестах из условия задачи, и только в случае успешного прохождения этих тестов решение далее проверяется на всех тестах из заданного набора, в определенной степени уменьшает объем необходимой работы. Более продуктивным выходом из создавшегося положения является автоматизация процесса проверки решений участников. Как минимум, это можно сделать с помощью командных файлов, которые следует подготовить предметно-методическим комиссиям соответствующего этапа и включить в состав комплекта материалов для проверки решений участников членами жюри.
В настоящее время во многих субъектах РФ вопрос с автоматизированной проверкой решений участников успешно решается, и специализированные системы проведения соревнований используются достаточно широко. Организаторы школьного или муниципального этапов, которые только начинают осваивать современные информационные технологии при проведении олимпиад по информатике, могут решать эту проблему одним из следующих способов:
1) Разработать своими силами простейшую программную систему автоматической проверки решений олимпиадных задач по информатике, ориентируясь на материалы предметно-методической комиссии соответствующего этапа.
2) Использовать для проверки решений участников одну из свободно распространяемых программных систем проведения олимпиад по информатике, информацию о которых можно найти либо в интернете, либо обратившись в региональную предметно-методическую комиссию по информатике.
3) Закупить одну из имеющихся в стране коммерческих программных систем для проведения олимпиад по информатике.
Какой способ лучше – это выбор организаторов школьного или муниципального этапа, поскольку везде есть свои преимущества и недостатки. Центральная предметно-методическая комиссия готова оказать консультационную помощь в решении этой проблемы, если представители региональной предметно-методической комиссии к ней обратятся.
Поскольку в функции предметно-методических комиссий по информатике соответствующего этапа олимпиады не входит обеспечение школьного и муниципального этапов программными системами проведения олимпиад по информатике, то единственное, чем они могут помочь организаторам школьного или муниципального этапов в решении вопроса автоматизации проверки решений участников – это предоставить жюри проверяющие программы для каждой задачи, которые могут быть либо интегрированы в большинство уже существующих в стране аналогичных систем, либо использованы в самостоятельно разработанных системах.
Следует заметить, что вопрос обеспечения школьного или муниципального этапов автоматизированными системами проверки решений участников не должен решаться только членами жюри соответствующего этапа накануне проведения олимпиады. Организаторы соответствующего этапа должны предусмотреть решение этого вопроса задолго до проведения олимпиады, поскольку для создания или приобретения и освоения такой системы требуется определенное время и дополнительные материальные и финансовые ресурсы, которых перед проведением соответствующего этапа у его организаторов может не оказаться. Здесь можно пойти по пути ряда субъектов РФ, которые на региональном уровне приобретают или разрабатывают типовую программную систему проведения олимпиад по информатике, и затем тиражируют ее в учреждения образования, обеспечивая проведение школьного или муниципального этапа в своем регионе по единой технологии. Возможны также и другие пути решения названной проблемы, например, и на муниципальном уровне. Однако в этом случае предметно-методическим комиссиям соответствующих этапов при формировании комплектов тестов и проверяющих программ необходимо будет учитывать разнообразие используемых систем проверки решений участников в различных учреждениях образования, проводящих школьный или муниципальный этапы.
Что касается подготовки предметно-методическими комиссиями соответствующих этапов материалов для автоматизированной проверки решений участников, то центральная предметно-методическая комиссия по информатике рекомендует направлять их в адрес жюри на компакт-диске. Материалы для каждой задачи должны быть представлены в отдельном каталоге. Каталог каждой задачи может включать:
1) Каталог «preliminary», содержащий тесты из примеров в условии задачи, предназначенные для предварительной проверки решений участника во время тура. Каждый тест из примера должен содержаться в отдельном файле, входные файлы называются «01», «02» и т.д. Файлы с правильными ответами называются «01.a», «02.a» и т.д. Тесты пронумерованы в том же порядке, в котором они следуют в условии задачи.
2) Каталог «tests», содержащий тесты для окончательной проверки и оценивания решений участников, правильные ответы и программы-генераторы, использовавшиеся для создания тестов. Программы-генераторы приведены исключительно для ознакомления жюри и организаторов школьного или муниципального этапа с методами получения тестов. Их запуск и использование для перегенерации тестов не требуется, так как комплект материалов уже содержит сгенерированные тесты и ответы к ним. Каждый тест должен содержаться в отдельном файле. Входные файлы называются «01», «02» и т.д. Файлы с правильными ответами называются «01.a», «02.a» и т.д. Программы генераторы содержатся в файлах, написанных на различных языках программирования, их компиляция и метод использования обычно описаны в командном файле, например, «doall.cmd», содержащемся в том же каталоге.
3) Исходный текст проверяющей программы для данной задачи «check.dpr».
4) Примеры правильных и неправильных решений. Каждое решение должно находиться в отдельном файле. Этот файл имеет, например, имя, построенное по маске «problem.ext», где «problem» - идентификатор задачи, обычно он совпадает с названием каталога, в котором находятся материалы задачи, «ext» - расширение файла, соответствующее языку программирования, на котором написано решение. Решения, которые являются неправильными или неоптимальными, также имеют суффикс, обычно указывающий на проблемы с этим решением, например «problem_wrong.ext» (неправильное решение), «problem_slow.ext» (медленное решение), «problem_bug.ext» (решение, содержащее некоторую типичную ошибку). Решения предоставляются для ознакомления членов жюри с возможной реализацией правильных и неправильных решений. Их использование для генерирования правильных ответов на тесты не требуется, так как материалы содержат готовые правильные ответы на все тесты.
5) Каталог «reference», содержащий эталонное решение задачи, которое должно использоваться для подбора ограничения по времени в случае существенных различий в быстродействии проверяющего компьютера, используемого региональным жюри, и рекомендуемого.
Проверяющая программа для каждой задачи, как правило, представляет собой файл, написанный на определенном языке программирования. Для компиляции проверяющей программы следует использовать соответствующий компилятор. В своей работе проверяющие программы могут использовать некоторый подключаемый модуль testlib, который также должен входить в состав материалов, распространяемых предметно-методическими комиссиями соответствующего этапа.
Запуск проверяющей программы может осуществляться следующим образом. В пустой каталог необходимо скопировать проверяющую программу (check.exe), входной файл, ответ для которого следует проверить (input), выходной файл, созданный программой участника (output) и файл с правильным ответом (answer). После этого проверяющая программа запускается с четырьмя параметрами: «check.exe input output answer result». Программа завершает свою работу с одним из трех возможных кодов возврата:
0 — ответ участника является правильным;
1 — ответ участника удовлетворяет формату вывода, но является неправильным, в этом случае участнику отправляется сообщение «Неверный ответ»;
2 — ответ участника не удовлетворяет формату вывода, в этом случае участнику отправляется сообщение «Ошибка формата выходных данных».
Файл «result» после завершения программы будет содержать сформированный проверяющей программой комментарий о причинах, по которым был выдан соответствующий отклик. Этот комментарий не должен сообщаться участникам и служит только для справки членам жюри.
Проверяющая программа check.exe используется как на этапе предварительной проверки, так и на этапе окончательной проверки и оценки решений участников. Отличие заключается в том, что при окончательной проверке при возникновении любой ошибки вместо формирования участнику сообщения, система просто помечает тест как не пройденный, и по результатам проверки участнику начисляются баллы за успешно пройденные тесты в соответствии с системой оценивания, разработанной предметно-методической комиссией соответствующего этапа.
Для задач с открытым входом, то есть, когда решением задачи является набор выходных файлов, проверяющая программа для предварительной и окончательной проверки могут несколько отличаться друг от друга. Для предварительной проверки может использоваться проверяющая программа, например, с именем «checkPreliminary.dpr», работа которой осуществляется следующим образом. В пустой каталог копируются исполняемый файл проверяющей программы (checkPreliminary.exe), входной файл соответствующего теста (input), выходной файл, присланный участником на проверку (output) и файл с правильным ответом (answer). Программа запускается с четырьмя параметрами: «checkPreliminary input output answer result». Программа завершает свою работу с одним из двух возможных кодов возврата:
0 — ответ участника удовлетворяет формату вывода;
2 — ответ участника не удовлетворяет формату вывода, в этом случае участнику отправляется сообщение «Ошибка формата выходных данных».
Файл «result» будет содержать сформированный проверяющей программой комментарий о причинах, по которым был выдан соответствующий отклик. Этот комментарий не должен сообщаться участникам и служит только для справки членам жюри и оргкомитета соответствующего этапа олимпиады. Если файл удовлетворяет формату вывода, то он принимается на проверку.
После окончания тура осуществляется окончательная проверка выходного файла. Для этого может использоваться, например, основная проверяющая программа с именем «check.dpr», работа которой осуществляется следующим образом. В пустой каталог копируются исполняемый файл проверяющей программы («check.exe»), входной файл, ответ для которого следует проверить (input), выходной файл, созданный программой участника (output), и файл с правильным ответом (answer). После этого проверяющая программа запускается с четырьмя параметрами: «check.exe input output answer result». Программа завершает свою работу с одним из двух возможных кодов возврата:
0 — ответ участника является правильным;
1 — ответ участника удовлетворяет формату вывода, но является неправильным.
Файл «result» после завершения программы будет содержать сформированный проверяющей программой комментарий о причинах, по которым был выдан соответствующий отклик. По результатам проверки участнику начисляются баллы за успешно пройденные тесты в соответствии с системой оценивания, разработанной предметно-методической комиссией соответствующего этапа.
4. Организация рабочего места участников школьного и муниципального этапов
За организацию рабочих мест участников школьного и муниципального этапов, включая оснащение компьютерной техникой и установку необходимого программного обеспечения, несут ответственность организаторы этих этапов олимпиады. Требования к организации рабочего места участников школьного и муниципального этапов олимпиады определяют соответственно муниципальные и региональные предметно-методические комиссии по информатике с учетом настоящих рекомендаций.
Рабочее место каждого участника школьного или муниципального этапа олимпиады должно быть оснащено персональным компьютером без подключения его к сети Интернет. Минимальные характеристики персонального компьютера должны быть не хуже следующих: процессор с частотой 1ГГц, объем оперативной памяти 256 Мбайт, объем жесткого диска 20 Гбайт. Для обеспечения равных условий для всех участников школьного или муниципального этапа используемые во время туров компьютеры должны иметь одинаковые или близкие технические характеристики.
Все компьютеры участников олимпиады и компьютеры, которые будут использоваться жюри при проверке решений участников, должны быть объединены в локальную компьютерную сеть. Выход в интернет для участников олимпиады во время очных туров должен быть заблокирован.
Для проведения школьного или муниципального этапа олимпиады на персональном компьютере каждого участника должно быть инсталлировано только программное обеспечение, необходимое для решения задач олимпиады, включая операционную систему. Центральная предметно-методическая комиссия по информатике рекомендует использовать для этого, помимо операционной системы, следующее программное обеспечение:
• Far Manager 1.7;
• Borland Delphi 7.0;
• Borland Pascal 7.0;
• Borland C++ 3.1;
• FreePascal 2.x.x;
• Microsoft Visual C/C++ 2005 Express Edition Service Pack 1;
• GNU C/C++ 4.4.x (версия для Windows - MinGW);
• Codeblocks 8.х
• Microsoft Visual Basic 2005 Express Edition Service Pack 1.
Муниципальные и региональные предметно-методические комиссии могут сами определять состав инструментального программного обеспечения, необходимого для проведения школьного и муниципального этапа соответственно. Однако при этом необходимо иметь в виду, что на заключительном этапе планируется использовать только названное выше программное обеспечение и в распоряжение жюри соответствующих этапов должны быть предоставлены все необходимые материалы для проверки решений, полученных с использованием предложенных предметно-методическими комиссиями систем программирования.
Если с обеспечением участников школьного и муниципального этапов олимпиады компьютерной техникой все обстоит более или менее нормально, то с установкой нужного программного обеспечения возникает много вопросов. Основной вопрос – где взять рекомендуемое центральной предметно-методической комиссией по информатике программное обеспечение в случае его отсутствия в учреждении образования, на базе которого проводятся эти этапы.
Проблема эта может решаться следующим образом. Системы программирования FreePascal 2.x.x; GNU C/C++ 4.4.x и Codeblocks 8.х являются свободно распространяемыми программными продуктами и их можно загрузить с соответствующих сайтов. Методическую помощь в этом случае учреждениям образования, которые проводят школьный и муниципальный этапы, должны оказывать соответственно муниципальные и региональные предметно-методические комиссии по информатике.
Ряд программных продуктов, которые можно использовать при проведении школьного и муниципального этапов, входят в состав стандартного базового пакета программного обеспечения «Первая помощь», поставка которого была осуществлена во все российские школы. Если какие-либо продукты компании Borland в этом пакете отсутствуют, то по вопросу получения лицензионных прав на бесплатное использование этих продуктов во время проведения школьного или муниципального этапа можно обращаться непосредственно в компанию Embarcadero Technologies (Sergey.Kozhevnikov@embarcadero.com), которая обладает всеми правами на продукты Borland, и между ней и центральной предметно-методической комиссией по информатике есть договоренность о поддержке Всероссийской олимпиады школьников.
Помимо вышеназванного программного обеспечения, современный уровень проведения олимпиад по информатике предполагает также установку на каждом компьютере участника программного приложения, обеспечивающего работу специализированной системы проведения соревнований, включая автоматическую проверку решений участников. Еще раз хотелось бы отметить, что установка такой системы является прерогативой организаторов школьного или муниципального этапа олимпиады. Отсутствие у жюри возможности автоматической проверки решений участников существенно усложняет весь процесс проверки и оценки решений участников и приводит к большому количеству ошибок.
Опыт использования в различных субъектах РФ систем автоматической проверки решений участников показал, что по своим функциональным возможностям и вариантам реализации такие системы могут отличаться друг от друга, но все они настроены на использование проверяющих программ, о которых шла речь в разделе 3.3. Более того, можно выделить основные функции таких систем, которые характерны для многих из них. В частности, в процессе предварительной проверки решений участников, представленных в виде программ, такие системы должны последовательно выполнять следующие действия:
1) Скомпилировать программу участника, используя приведенную в Памятке участнику команду для соответствующего языка программирования. Если компиляция программы участника завершается неудачно, участнику сообщается результат «Ошибка компиляции». Возможно предоставление участнику вывода компилятора в стандартный поток вывода и стандартный поток ошибок. Если компиляция завершилась успешно, программа проверяется на тестах из примера.
2) Осуществить последовательную проверку программы участника на всех тестах из примера. Проверка на одном тесте осуществляется следующим образом. В пустой каталог копируется исполняемый файл программы участника и тестовый входной файл. Тестовый файл должен иметь имя, указанное в условии задачи. Далее программа участника запускается, и проверяющая система отслеживает соблюдение программой существующих ограничений, связанных с запретом на создание каталогов и временных файлов при работе программы, а также любое использование сетевых средств и выполнение других действий, нарушающих работу самой проверяющей системы.
3) Обеспечить контроль времени работы программы участника и объема используемой памяти. Если время работы программы превысило ограничение, указанное в условии задачи, выполнение программы участника прерывается и участнику отправляется сообщение «Превышено время работы». Если количество используемой памяти превысило ограничение, указанное в условии задачи, то выполнение программы участника также прерывается и участнику отправляется сообщение «Превышен максимальный объем используемой памяти».
4) Проверить, создала ли программа участника и самостоятельно обработала исключительную ситуацию (exception). Если программа участника создала и самостоятельно не обработала исключительную ситуацию (exception), выполнение программы участника прерывается и участнику отправляется сообщение «Ошибка времени исполнения».
5) Проверить, завершила ли программа участника работу с нулевым кодом возврата. Если программа участника завершила работу с ненулевым кодом возврата, участнику отправляется сообщение «Ошибка времени исполнения».
6) Проверить, создала ли программа участника в каталоге, в котором она была запущена, выходной файл с именем, указанным в условии задачи, если программа участника завершила работу за отведенный период времени, не превысила максимальный объем памяти и завершила работу с нулевым кодом возврата. Если файл с указанным именем не найден, участнику отправляется сообщение «Ошибка формата выходных данных». Если выходной файл создан, то осуществляется проверка его корректности. Для этого используется соответствующая проверяющая программа.
7) Сообщить участнику о результатах проверки его программы. Если программа участника выдает правильный ответ на всех тестах из примера, то она может быть принята на окончательную проверку. В этом случае участнику отправляется сообщение «Принято на проверку», а тестирующая система запоминает решение участника как последнее принятое решение по данной задаче. В противном случае участнику отправляется сообщение в соответствии с описанными выше правилами. При этом участнику помимо типа ошибки сообщается номер теста из примера, на котором произошла ошибка.
При окончательной проверке решений участников, представленных в виде программ, которая осуществляется после тура, программная система проведения олимпиад по информатике должна проверить на основных тестах последнее принятое на проверку решение участника по каждой задаче. Выполняемые системой функции в этом случае во многом повторяют вышеописанные. Однако при возникновении любой ошибки вместо отправки участнику сообщения, система просто помечает тест как не пройденный. Кроме того, по результатам окончательной проверки система начисляет участнику баллы за успешно пройденные тесты.
Сказанное выше можно распространить и на проверку решений участников, представленных в виде набора выходных файлов. Однако из описанных выше функций программных систем для проведения олимпиад по информатике остаются только две последние с небольшими изменениями. В частности, в процессе предварительной проверки осуществляется только контроль формата присланного участником выходного файла. Если этот файл удовлетворяет формату вывода, то он принимается на окончательную проверку. В противном случае, по результатам предварительной проверки участнику отправляется сообщение «Ошибка формата выходных данных».
В заключение хотелось бы отметить, что если нет возможности использовать при проведении школьного или муниципального этапа какой-либо готовой программной системы проведения олимпиады по информатике, то разработка простейшей системы, позволяющей осуществлять окончательную проверку решений участников в автоматическом режиме, является не такой уж сложной задачей и по силам любой муниципальной или региональной предметно-методической комиссии по информатике с привлечением специалистов соответствующей квалификации. Наличие такой системы в субъекте РФ позволит на должном уровне осуществлять проверку решений участников не только на школьном и муниципальном этапах, но и региональном этапе олимпиады по информатике.
Список рекомендуемой литературы
1. Алексеев А.В., Беляев С.Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта: учебно-методическое пособие для учащихся 7-11 классов. – Ханты-Мансийск: РИО ИРО, 2008. – 284 с.
2. Андреева Е.В., Босова Л.Л., Фалина И.Н. Математические основы информатики. Элективный курс: Учебное пособие. – М.: БИНОМ. Лаборатория Знаний, 2007. – 312 с.
3. Арсак Ж. Программирование игр и головоломок. – М.: Наука, 1990. – 224 с.
4. Бентли Д. Жемчужины творчества программистов: пер. с англ. – М.: Радио и связь, 1990. – 224 с.
5. Брудно А.Л., Каплан Л.И. Московские олимпиады по программированию/ Под ред. акад. Б.Н. Наумова.- 2-е изд., доп. и пераб. – М.: Наука, гл. ред. физ.-мат. лит., 1990. – 208 с.
6. Долинский М.С. Алгоритмизация и программирование на Turbo Pascal: от простых до олимпиадных задач: Учебное пособие. – СПб.: Питер Принт, 2004. – 240 с.
7. Задачи по программированию /С.М. Окулов, Т.В. Ашихмина, Н.А. Бушмелева и др.; Под ред. С.М. Окулова. – М.: БИНОМ. Лаборатория знаний, 2006. – 820 с.
8. Златопольский Д. М. Программирование: типовые задачи, алгоритмы, методы. – М.: БИНОМ. Лаборатория знаний, 2007. – 223 с.
9. Иванов С.Ю., Кирюхин В.М., Окулов С. М. Методика анализа сложных задач по информатике: от простого к сложному // Информатика и образование. 2006. №10. С. 21 – 32.
10. Кирюхин В.М. Всероссийская олимпиада школьников по информатике. М.: АПК и ППРО, 2005. –212 с.
11. Кирюхин В.М. Информатика. Всероссийские олимпиады. Выпуск 1. – М.: Просвещение, 2008. – 220 с. – (Пять колец).
12. Кирюхин В.М. Информатика. Всероссийские олимпиады. Выпуск 2. – М.: Просвещение, 2009. – 222 с. – (Пять колец).
13. Кирюхин В.М. Информатика. Всероссийские олимпиады. Выпуск 3. – М.: Просвещение, 2010. – 201 с. – (Пять колец). (Планируется к изданию в конце 2009 года).
14. Кирюхин В.М. Информатика. Международные олимпиады. Выпуск 1. – М.: Просвещение, 2009. – 239 с. – (Пять колец).
15. Кирюхин В.М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. №4. С. 42 – 54.
16. Кирюхин В.М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. №5. С. 29 – 41.
17. Кирюхин В.М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. – М.: БИНОМ. Лаборатория знаний, 2007. – 600 с.
18. Кирюхин В.М., Цветкова М.С. Всероссийская олимпиада школьников по информатике в 2006 году. – М.: АПК и ППРО, 2006. – 152 с.
19. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 1999. – 960с.
20. Меньшиков Ф.В. Олимпиадные задачи по программированию. – СПб.: Питер, 2006. – 315 с.
21. Московские олимпиады по информатике. 2002 – 2009. / Под ред. Е.В. Андреевой, В.М. Гуровица и В.А. Матюхина. – М.: МЦНМО, 2009. – 414 с.
22. Окулов С. М. Основы программирования. – М.: БИНОМ. Лаборатория знаний, 2005. – 440 с.
23. Окулов С. М. Программирование в алгоритмах. – М.: БИНОМ. Лаборатория знаний. 2002. – 341 с.
24. Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учебное пособие. – М.: БИНОМ. Лаборатория знаний. 2008. – 422 с.
25. Окулов С. М., Лялин А. В. Ханойские башни. – М.: БИНОМ. Лаборатория знаний. 2008. – 245 с. (Развитие интеллекта школьников).
26. Пинаев В.Н. Олимпиадные задачи по программированию: Учебное пособие / РГАТА. – Рыбинск, 1997. – 41 с.
27. Рейнгольд Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, н. Део. – М.: Мир, 1980. – 476 с.
28. Скиена С.С., Ревилла М.А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. – М.: Кудиц-образ, 2005. – 416 с.
29. Столяр С.Е., Владыкин А.А.. Информатика. Представление данных и алгоритмы. – СПб.: Невский Диалект; М.: БИНОМ. Лаборатория знаний. 2007. –382 с.
30. Уэзерелл Ч. Этюды для программистов. – М.: Мир, 1982. – 288 с.
31. Шень А. Программирование: теоремы и задачи. – М.:МЦНМО, 1995. – 264 с.