автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Методология и технические решения для проведения олимпиад по информатике и программированию

На поавах рукописи

М-

Станкевич Андрей Сергеевич

Методология и технические решения

для проведения олимпиад по информатике и программированию

Специальность 05.13.06 — «Автоматизация и управление технологическими процессами и производствами (образование)»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2011

- 8 ДЕК 2011

005004771

Работа выполнена на кафедре «Компьютерные технологии» в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики (НИУ ИТМО)

Научный руководитель

доктор технических наук, профессор

Парфенов Владимир Глебович

Официальные оппоненты

доктор физико-математических наук, профессор

Романовский Иосиф Владимирович

кандидат технических наук Нарвский Андрей Сергеевич

Ведущая организация Саратовский государственный университет

имени Н. Г. Чернышевского

Зашита диссертации состоится 22 декабря 2011 г. в 12 часов 30 минут на заседании диссертационного совета Д 212.227.06 в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики но адресу: 197101, Санкт-Петербург, Кронверкский пр. 49.

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО.

Автореферат разослан 21 ноября 2011 г. Ученый секретарь диссертационного совета,

доктор технических наук, профессор Л. С. Лисицына

Общая характеристика работы

Актуальность проблемы. В последнее время число различных соревнований по информатике и программированию для школьников и студентов постоянно растет. Олимпиады поддерживаются университетами, поскольку участие в них позволяет сформировать у школьников и студентов интерес к информатике и программированию, стимулируя поступление на специальности соответствующего профиля. Также поддержка олимпиад осуществляется государством через гранты Министерства образования и науки РФ и компаниями, специализирующимися на разработке программного обеспечения. Для компаний олимпиады представляют собой способ поиска и отбора высококвалифицированных сотрудников, а также предоставляют возможность для распространения информации об инженерной и исследовательской работе, проводимой компаниями. Происходит популяризация профессии'программиста как творческого труда, требующего высокой квалификации.

На основе олимпиад по информатике и программированию был предложен и развивается соревновательный подход в образовании.

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

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

Цель диссертационной работы — разработка методологии и технических решений для организации и проведения олимпиад но информатике и программированию. Для достижения этой цели были поставлены и решены следующие задачи:

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

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

3. Создать автоматическую систему управления соревнованиями по программированию.

4. Внедрить разработанные методику и автоматическую систему в практику проведения олимпиад по информатике и программированию.

5. Внедрить разработанные методику и автоматическую систему в учебный процесс при работе со школьниками, абитуриентами и студентами.

Научная новизна. На защиту выносятся следующие результаты,

обладающие научной новизной.

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

2. Унифицированный метод обработки результатов и подведения итогов соревнований в автоматической системе управления соревнованиями по программированию.

3. Модель представления данных о соревнованиях, позволяющая осуществлять эффективное переиспользование материалов соревнований.

Методы исследования. В работе использованы методы теории формальных языков, дискретной математики и теории алгоритмов.

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

1. При проведении олимпиад по информатике и программированию, в том

числе:

о Всероссийской командной олимпиады школьников по информатике и программированию, которая проводится под руководством автора с 2000 г. по настоящее время; о серии интернет-олимпиад школьников по информатике и

программированию; о индивидуальной олимпиады по информатике и программированию; о олимпиады Russian Code Сир.

2. В учебном процессе на кафедре «Компьютерные технологии» НИУ ИТМО при проведении практических занятий по курсам «Дискретная математика и алгоритмы», «Алгоритмы и структуры данных», «Теория формальных языков», «Языки программирования и методы трансляции», «Алгоритмы алгебры и теории чисел».

3. В учебном процессе на кафедре «Компьютерные технологии» НИУ ИТМО при проведении вступительных тестирований абитуриентов с 2000 по 2007 г.

4. В дополнительном обучении информатике и программированию школьников, например, в Физико-математическом лицее № 239 (Санкт-Петербург).

' Апробация результатов работы. Основные положения диссертационной работы докладывались на научно-методических конференциях «Современные технологии обучения» (СПбГЭТУ, 2002), «Телематика-2004» (СПбГУ ИТМО), «Конференция молодых ученых СПбГУ ИТМО» (2005), «Телематика-2005» (СПбГУ ИТМО), «Телематика-2009» (СПбГУ ИТМО), «Телематика-2010» (СПбГУ ИТМО), «Competitive Learning Institute Symposium» (Харбин, Китай, 2010).

Внедрение результатов работы. Результаты диссертации использованы при выполнении научно-исследовательских работ Министерства образования и науки РФ по темам «Создание информационной обучающей системы подготовки разработчиков программного обеспечения на основе методологии, используемой в международных олимпиадах по программированию», «Разработка концепции и методического обеспечения новой технологии обучения и контроля качества образования в области программирования», «Разработка технологии создания программного обеспечения систем управления на основе автоматного подхода», а также государственных контрактов «Выполнение работ (оказание услуг) по организации и проведению Всероссийской олимпиады школьников и студентов по информатике и программированию», «Выполнение работ (оказание услуг) по созданию системы повышения квалификации педагогических кадров в области информационных технологий на базе интегрированной информационной образовательной среды и комплекса интернет-олимпиад и творческих конкурсов».

Публикации. На тему диссертации опубликовано 13 научных работ, в том числе шесть статей, из которых две в журналах из перечня ВАК.

Награды. В 2003 г. автор в составе авторского коллектива стал лауреатом премии Президента Российской Федерации в области образования за научно-практическую работу для образовательных учреждений высшего профессионального образования «Разработка концепции и создание организационной структуры, учебно-методического и программного обеспечения инновационной системы подготовки высококвалифицированных кадров в области информационных технологий».

В 2004 г. автору была присуждена премия ACM ¡CPC Founder's Award за вклад в развитие чемпионата мира по программированию в Европе.

В 2008 г. автору была присуждена премия ACM ICPC Distinguished Coach Award за выдающиеся достижения как тренеру команд НИУ ИТМО на чемпионате мира по программированию.

Автор является дважды призером чемпионата мира по программированию (2000 г.— четвертое место, 2001 г. — третье место), тренером трех команд — чемпионов мира по программированию (2004, 2008. 2009 гг.) и трех команд, занявших третье место на этом чемпионате (2003, 2005, 2007 гг.).

В 2009 г. автору присуждена Молодежная премия Санкт-Петербурга в области информационных технологии.

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

Содержание работы

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

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

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

В США в 1977 г. был проведен первый чемпионат вузов по программированию, который затем был преобразован в чемпионат мира. В России соревнования студентов по программированию проводятся с 1996 г. С 1998 г., в нашей отборочной группе по причине большого числа желающих участвовать в соревнованиях, проводятся четвертьфинальные соревнования чемпионата мира. Расширение географии соревнования привело к образованию в России и ближнем зарубежье новых четвертьфиналов. Организация многих из них происходила на базе вузов, не имевших традиций проведения олимпиад, поэтому им требовалось помощь в организации. При их проведении подготовка задач и управление соревнованием происходит из Санкт-Петербурга. Полуфинал чемпионата мира проводился одновременно в Санкт-Петербурге и Барнауле. С расширением географии соревнований появилась необходимость увеличить число мест проведения полуфинала.

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

•Затем в этой главе проводится обзор олимпиад школьников. Всероссийская олимпиада школьников по информатике проводится с 1988 г. С 2003 г. автор является членом жюри и научного комитета Всероссийской олимпиады школьников по информатике. В 2003 г., а также с 2005 г. по настоящее время автор яатяется председателем научного комитета олимпиады. До 2002 г. тестирование решений участников на олимпиаде проводилось с помощью скриптов в полуавтоматическом режиме в присутствии участников. До 2010 г. на олимпиаде использовалась система оценки по тестам. Начиная с 2011 г., используется система оценки на основе подзадач, при которой каждая задача разбивается на подзадачи и баллы за подзадачу начисляются только если все тесты, соответствующие подзадаче, пройдены.

Городские командные олимпиады школьников по информатике и программированию проводятся в Санкт-Петербурге с 1993 г. Начиная с 1998 г., на олимпиаду в Санкт-Петербург приглашаются представители других городов. В 1998 и 1999 гг. были проведены первый и второй пилотные командные чемпионаты школьников по программированию. Общего Всероссийского командного соревнования школьников в то время не существовало.

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

Далее в первой главе приводится обзор различных подходов к тестированию программных решений и подведению итогов. Основными сценариями тестирования являются: тестирование на последовательном наборе тестов, интерактизное тестирование и тестирование в форме турнира. Различные соревнования по информатике и программированию используют различные схемы подведения итогов. Наиболее широко распространенными являются система студенческого чемпионата мира, система международной олимпиады школьников по информатике, использовавшаяся до 2009 г., новая система, используемая на

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

Затем проводится обзор ряда автоматических систем управления соревнованиями.

• Система eJudge (Александр Чернов, МГУ).

• Система ВОМ/^е (Голландия, университет Утрехта).

• Система м^е (Самарский государственный технический университет).

• Система (Санкт-Петербургский государственный университет).

• Система РС2 (Калифорнийский университет, Сакраменто, США). Использовалась на финале чемпионата мира по программированию до 2009 г.

• Система К ЛТП Б (Королевский технологический институт, Стокгольм, Швеция). С 2010 г. используется на финале чемпионата мира по программированию.

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

Во второй главе разрабатывается методология проведения олимпиад по информатике и программированию.

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

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

Формулируются требования к системе автоматического управления соревнованиями по программированию.

1. Система должна поддерживать взаимодействие с участниками соревнований.

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

3. Система должна осуществлять взаимодействие с организаторами соревнований.

4. Система должна осуществлять промежуточное и окончательное подведение итогов соревнований, поддерживать различные системы подведения итогов.

5. Система должна предоставлять возможность организовывать соревнования параплельно в нескольких точках проведения.

6. Система должна предоставлять организаторам возможность по переиспользованию материалов соревнований.

7. Система должна быть надежной.

Отдельно формулируются требования к переиспользованию материалов.

1. Система должна предоставлять возможность использовать одну и ту же задачу в различных соревнованиях.

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

3. Один и тот же участник должен иметь возможность участвовать в нескольких соревнованиях, проводимых с помощью рассматриваемой системы.

4. Система должна быть способна одновременно обслуживать несколько соревнований.

5. Система должна предоставлять возможность для соревнования создавать различные таблицы результатов с разным набором участников.

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

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

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

Затем во второй главе формулируются требования к серии интернет-соревнований для школьников.

1. Соревнования должны проводиться рехулярно.

2. Проведение только для школьников, либо отдельный школьный зачет.

3. Соревнования должны иметь несколько уровней сложности.

4. Необходимо проведение как личных, так и командных соревнований.

5. Расписание соревнования с учетом наличия различных часовых поясов.

6. Задачи на соревновании должны быть представлены на русском языке.

7. Участники представлены на соревновании своими реальными именами.

Анализ существующих интернет-соревнований позволяет выявить также

другие аспекты интернет-соревнований, которые не являются необходимыми.

8. По результатам серии олимпиад участники могут иметь рейтинг.

9. Участники могут иметь возможность дорешивать задачи олимпиады после ее окончания.

Далее в главе проводится анализ существующих соревнований на соответствие сформулированным требованиям. Делается вывод о необходимости разработки схемы серии интернет-соревнований и предлагается схема, удовлетворяющая требованиям

1 - 7. Введение рейтинга для школьных интернет-соревнований признается не оправданным. Вместо возможности дорешивания на сайте соревнований предлагается размещать з открытом доступе материалы жюри после олимпиады. Результат анализа приведен в табл. 1, соответствие требованию обозначается символом «+», несоответствие— символом «-», частичное соответствие — символом « ±».

Таблица 1. Сравнительный анализ интернет-соревнований на соответствие требованиям

Сорсвнование\требование 1 2 3 4 5 6 7 8 9

Предлагаемая система интернет-олимпиад + + + + + + + - +

ТорСос/ег -г ± ± _ + _ - 4. +

Открытый кубок + ± + _ + + + +

та СО + + _ _ _ + _ ±

Хорватские иитернет-олимпиады по инфооматике + ± _ _ _ _ т _ _

Соревнования на базе интернет-архивов задач ± - - ± -г + - ± +

После этого рассматриваются основные принципы формирования комплектов задач для интернет-олимпиад и необходимые технические решения для проведения этой серии.

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

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

Левоконтекстной терминальной грамматикой, называется формальная грамматика, в которой все правила имеют вид тА —* где слово т состоит только из терминалов, а слово % может состоять из терминалов и нетерминалов.

Сформулированы и доказаны ряд теорем.

Теорема 1. Язык, порождаемый левоконтекстной терминальной грамматикой, является контекстно-свободным.

Контекстно-однозначной грамматикой называется грамматика, в которой для нетерминалов А для всех правил вида аА —* выполнено одно из двух: (1) для любых двух различных правил а А —> аЕ, и 15А —* выполнено: а не является суффиксом р, и Р не является суффиксом а, или (2) во всех таких правилах а = е и правые части начинаются с различных терминалов.

Теорема 2. Пусть Г — контекстно-однозначная левоконтекстная терминальная грамматика и — слово из терминалов. Тогда существует не более одного левостороннего вывода слова IV в грамматике Г.

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

Алгоритм 1. Проверка форсирования одним нетерминалом другого. По двум заданным нетерминалам А и В выясняется, верно ли, что если в выводе слова, состоящего только из терминалов, встречается А, то встретится и В.

Алгоритм 2. Проверка форсирование одним множеством нетерминалов другого. Пусть заданы множества нетерминалов и и V. Выясняется, верно ли, что если в выводе слова, состоящего только из терминалов, встречается нетерминал из и, то встретится и нетерминал из V.

Алгоритм 3. Проверка усиленного форсирования одним нетерминалом другого. По нетерминалам А и В выясняется, верно ли, что для любой, конечной или бесконечной, левосторонней цепочки порождений выполняется условие: если встречается нетерминал А, то встречается и нетерминал В.

Для доказательства корректности алг. 3 формулируется и доказывается теорема 3.

Теорема 3. Нетерминал А грамматики Г усиленно форсирует нетерминал В, если и только если выполнены следующие два условия: (1) А форсирует В; (2) в графе порождений без В грамматики Г ¡¡(Г) не существует бесконечного пути, из вершины 5, проходящего через помеченное ребро, где — начальный символ грамматики Г.

Алгоритм 4. Проверка усиленного форсирования одним множеством нетерминалов другого. По заданным множествам нетерминалов и и V выясняется, верно ли, что в любой левосторонней цепочке порождений выполняется условие: если встречается нетерминал из множества и, то встречается и нетерминал из множества V.

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

Алгоритм 5. Проверка того, что нетерминал является потенциально тупиковым.

Затем в третьей главе предлагается задание сценариев тестирования с использованием левоконтекстных терминальных грамматик.

Для каждого этапа работы над решением создадим нетерминал. Если этапы тестирования объединяются в группы, для каждой из них также создадим нетерминал. Для каждого действия над тестируемым решением каждый его исход

обозначим терминалом. Действия над решениями можно условно разделить на два класса.

К первому классу относятся основные этапы проверки решения, в результате которых состояние решения изменяется. Будем называть такие действия атомарными. Рассмотрим атомарное действие с нетерминалом А. Для каждого возможного исхода этого действия а добавим в грамматику правило А—>а.

Второй класс действий составляют операции принятия решения о дальнейшей проверке решения. Такие действия будем называть контролирующими. Рассмотрим контролирующее действие с нетерминалом С. Для каждого такого действия рассмотрим все возможные исходы к последних действий. Для каждой такой последовательности а длины к необходимые дальнейшие действия задаются строкой из нетерминалов 4- Тогда добавим в грамматику правило а С—* ас.

Пусть нетерминал О соответствует набору действий над решением, состоящей из действий, описываемых последовательностью нетерминалов В этом случае добавим в грамматику правило: О —>

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

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

Затем рассматривается реализация интерпретации сценария тестирования с использованием стековой машины, реализующий левосторонний вывод в задающей его грамматике.

На основании предложенных алгоритмов осуществляется анализ различных свойств сценариев. В диссертации рассматривается 10 примеров. Приведем наиболее интересные из них.

Пример 1. Возможность завершения тестирования. Существует последовательность исходов атомарных операций над решением, при которой тестирование решения успешно завершается.

Пример 2. Возможность выполнения действия. Существует последовательность исходов, при которой будет выполнено заданное атомарное действие.

Пример 3. Форсирование одним действием другого. При любых исходах если будет выполнено действие, которому соответствует нетерминал А, то будет выполнено действие, которому соответствует нетерминал В.

Пример 4. Обязательное завершение тестирования при выполнении заданного атомарного действия. По заданному атомарному действию выяснить, верно ли, что если выполнилось это действие, то тестирование будет завершено.

Для каждого примера приводится алгоритм анализа заявляемого свойства на основе преобразования левоконтекстной терминальной грамматики в

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

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

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

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

В четвертой главе рассматривается система автоматического управления соревнованиями по программированию РСМ5, в значительной мере разработанная, автором, который написал порядка 60 - 70% исходного кода в ней.

На рис. 1 представлена структура системы для проведения соревнований через интернет.

Икеокеры длп запуска оешеннй участников

Сервер РСМЗ

УУеЬ-сервер

Участники

Рис. 1. Организация работы системы РСМ$ для проведения соревнований через интернет

На рис. 2 представлена структура системы для проведения Всероссийской командной олимпиады школьников по информатике и программированию с использованием системы РСМ8,

Рис. 2. Организация работы системы PCMS для проведения Всероссийской командной олимпиады школьников по информатике и программированию

Рассмотрим основные принципы разработки системы. Логические модули организованы в форме компонент, взаимодействие между которыми происходит с использованием механизма предоставляемых сервисов. Компоненты, отвечающие за единый блок задач, образуют пакеты. Client — интерфейс для участников соревнований, Site — для взаимодействия на серверной стороне с пакетом Client, Judging — для автоматической проверки решений участников с помощью методов, предложенных в главе 3, Invoke — для безопасного запуск решений участников, Local —для обеспечения возможности управления соревнованием, Sync — для проведения соревнования в нескольких местах, Scoring —для подведения итогов соревнований, в соответствии с методом, предложенным в главе 3, Persistence — для хранения данных системы.

Предлагается модель данных, позволяющая обеспечить переиспользование материалов соревнований. Изменения, внесенные в любые материалы, при применении данной модели автоматически приводят к изменениям во всех использующих эти материалы соревнованиях. Например, в базе задач PCMS, используемой на кафедре «Компьютерные тенхнологии» НИУ ИТМО, каждая задача использована в среднем в 2,7 соревнованиях. При этом 17% задач встречается более чем в пяти соревнованиях. Таким образом, переиспользование материалов позволяет существенно снизить затраты времени администратора на внесение изменений.

Результаты сравнения с другими системами автоматического управления соревнованиями по программированию в аспекте переиспользования материалов, требования к которому сформулированы в главе 2, приведены в табл. 2.

Таблица 2. Сравнение возможностей по переиспользованию материалов в различных системах управления соревнованиями

Система управления соревнованиями 1 2 3 4 5

PCMS + + + + -r

ejudge - - + -t- ±

DOMJudge - _ - + +

dudge - - - -t- -

TestSys - - + 4- ±

PC - - - — -

jotrns - - - — +

Проведено сравнение разработанного унифицированного подхода к подведению итогов соревнований с методами, реализованными в других системах. Показано, что этот метод обладает преимуществами в части размера создаваемого и изменяемого исходного кода, необходимого для реализации новых систем оценки. Так, например, в системе eJudge, являющейся наиболее мощной из рассматриваемых альтернативных систем, модуль подведения итогов имеет исходный код размером 190 Кбайт, добавление новой системы оценки требует существенной модификации кода. В системе PCMS добавление новой системы оценки не требует модификации существующего кода. Типичный размер исходного кода плагина составляет 5-7 Кбайт.

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

В пятой главе рассмотрено внедрение разработанной методологии и автоматической системы управления соревнованиями по программированию в проведение олимпиад и учебный процесс.

Сначала рассматривается Всероссийская командная олимпиада школьников по информатике и программированию. Она проводится ежегодно, начиная с 2000 г., в соответствии со схемой проведения соревнований, рассмотренной в главе 2. Автор работы является председателем жюри олимпиады, членом оргкомитета и технического комитета олимпиады. Все годы на олимпиаде применяется система PCMS, рассмотренная в главе 4. За время использования существенных сбоев, влияющих на результаты олимпиады зафиксировано не было.

Затем рассматривается реализованная в соответствии с предложенной в главе 2 серия интернет-олимпиад школьников. Проводится сравнение с другими интернет-соревнованиями для школьников по численности участников и числу подготовленных задач. Сравнение позволяет сделать следующие выводы.

• Среднее число участников олимпиад существенно больше, чем у TopCoder High School, хотя в интернет-олимпиадах задачи предлагаются на русском языке.

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

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

• За время проведения олимпиад подготовлено 942 задачи, что почти в пять раз больше, чем за тот же период у TopCoder High School.

В рамках системы олимпиад Российским советом олимпиад школьников с 2009 г. проводится Индивидуальная олимпиада по информатике и программированию. Проведение олимпиады осуществляется в соответствии с методологией, разработанной в главе 2. Для технической поддержки олимпиады используется система PCMS.

В 2011 г. по инициативе компании Mail.Ru Group коллективом НИУ ИТМО было проведено соревнование Russian Code Сир, которое должно стать ежегодным. Автор стал председателем жюри. Жюри было сформировано на базе жюри интернет-олимпиад. Для обеспечения технической поддержки олимпиады использовалась система PCMS.

Успешная организация, например, этих олимпиад за короткий срок демонстрирует воспроизводимость результатов диссертации.

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

Рассматривается опыт внедрения результатов диссертации в работу со студентами на примере проведения лабораторных работ с автоматической проверкой. Анализируются затраты преподавателя на подготовку теоретических заданий для контрольных работ (КР) и практических заданий для лабораторных работ (ЛР) и дальнейшую проверку работ студентов. Результаты анализа приведены в табл. 3.

Таблица 3. Трудозатраты преподавателя на подготовку и проверку различных заданий

Рабшаоадашк Задание КРс ответом Задание КР надок-во Простая задача дта Л Р Сложная задача для ЛР

Подготовка задания пргподаагелем 15—20 мин 30-60мин 1-2ч*а 2-4 чха

FtooBefisa регшшя правдазвгшлем 1-2.\пш 5-10 мин нетребуется не требуется

Организация проведения работ а не требуется не требуется 5-10 Mini 5-10мин

C\M\Lp юе время (40 студентов) 1-2часа 4-5<исов 1-2часа 2-4чха

Организация и проверка (40 студентов) Oi-li'aa 3-4 часа 5-10мш 5-Юмин

Введение лабораторных работ позволило в 2-4 раза уменьшить затраты времени преподавателя. Кроме того, введение лабораторных работ позволило увеличить покрытие контрольными заданиями материалов курса с 40 - 50% до 70 - 85%.

Далее рассматривается вариант использования олимпиадного подхода для проверки некоторых научных результатов. На базе некоторого утверждения формулируется олимпиадная задача, решение которой воспроизводит его доказательство, либо алгоритм, базирующийся на этом утверждении. В качестве независимой проверки используются решения участников соревнования. Метод рассмотрен на примере задачи F «Formal Verification» сборов студенческих

команд в Петрозаводске в августе 2010 г., в которой требовалось решить задачу анализа свойства сценариев «Форсирование одним действием другого» (пример 4 из главы 3, алгоритм анализа этого свойства основан на теореме 3).

На основании изложенного в пятой главе делается вывод о высокой эффективности внедрения в учебный процесс методологии проведения олимпиад и автоматической системы управления соревнованиями.

Заключение

В результате диссертационных исследований получены следующие результаты.

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

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

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

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

5. Разработана методология проведения олимпиад по информатике и программированию с использованием автоматической системы проведения соревнованиями.

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

о Всероссийская командная олимпиада школьников по информатике и программированию (проводится под руководством автора с 2000 г. по настоящее время); о серия интернет-олимпиад школьников по информатике и

программированию; о индивидуальная олимпиада но информатике и программированию; о олимпиада Russian Code Сир.

7. Разработанные методология проведения олимпиад и система управления соревнованиями внедрены в учебный процесс в НИУИТМО и ФМЛ №239. Это позволило в 2-4 раза снизить временные затраты преподавателя на проверку работ и повысить качество покрытия материала конгрольными заданиями.

8. За организацию и проведение Всероссийской командной олимпиады школьников по информатике и протраммированию и разработку автоматической системы управления соревнованиями PCMS в 2003 г. автор в составе коллектива стал лауреатом премии Президента Российской Федерации в области образования за научно-практическую работу для образовательных учреждений высшего профессионального образования «Разработка концепции и создание организационной структуры, учебно-методического и программного обеспечения инновационной системы подготовки высококвалифицированных кадров в области информационных технологий».

Статьи в журналах из перечня ВАК

1. Станкевич А. С. Общий подход к подведению итогов соревнований по программированию при использовании различных систем оценки // Компьютерные инструменты в образовании. 2011. № 2, с. 27-38.

2. Станкевич А. С., Маврин П. Ю. Использование лево контекстных грамматик для описания сценариев автоматического тестирования программных решений //Дистанционное и виртуальное обучение. 2011. №8, с. 36-48.

Другие публикации

3. Станкевич А. С, Харченко Т. В. Всероссийские интернет-олимпиады по информатике и программированию // Компьютерные инструменты в образовании. 2002. № 3 - 4, с. 60 - 70.

4. Станкевич А. С., Елизаров Р. А. Система управления соревнованиями по программированию как система обработки данных // Телекоммуникации и информатизация образования. 2003. № 3, с. 64-85.

5. Станкевич А. С., Маврин П. Ю., Корнеев Г. А., Шалыто А. А. Моделирование жизненного цикла компоненты программного комплекса с использованием диаграмм состояний // Информатизация и связь. 2008. № 2, с. 20 - 23.

6. Станкевич А. С. Использование алгоритмов анализа левоконтекстных терминальных грамматик в задачах автоматического тестирования программ // Труды СПИИРАН. 2010. Вып. 13, с. 106 - 121.

7. Станкевич А. С. О проведении олимпиад школьников по программированию /Материалы VIII международной конференции «Современные технологии обучения». СПбГЭ'ГУ. 2002, с. 326,327.

8. Станкевич А. С., Васильев В. Н„ Елизаров Р. А., Казаков М. А., Парфенов В. Г. Использование олимпиад и творческих конкурсов при подготовке высококвалифицированных кадров в области информационных технологий /Труды XI Всероссийской научно-методической конференции «Телематика-2004». СПбГУ ИТМО. 2003, с. 437,438.

9. Станкевич А. С, Корнеев Г. А. Методы тестирования решений задач на соревнованиях по программированию / Труды II межвузовской конференции молодых учёных. СПбГУ ИТМО. 2005, с. 36 - 40.

10. Станкевич А. С., Корнеев Г. А., МавринП.Ю. Использование конечных автоматов с магазинной памятью для автоматизации тестирования программных решений / Труды XII Всероссийской научно-методической конференции «Телематика-2005». СПбГУ ИТМО. 2005, с. 510,511.

11. Станкевич А. С., Корнеев Г. А., Маврин П. Ю. Построение компонентных систем с поддержкой динамической реконфигурации / Труды XVI Всероссийской научно-методической конференции «Телематика-2009». СПбГУ ИТМО. 2009, с. 289.

12. Станкевич А. С., МавринП.Ю., Парфенов В. Г. Использование левоконтекстных грамматик для описания сценариев автоматического тестирования программных решений / Труды XVII Всероссийской научно-методической конференции «Телематика-2010». СПбГУ ИТМО. 2010, с. 197,198.

13.StankevichA., ParfenovV., Tsarev F. Internet Olympiads in Informatics for High School Students / Competitive Learning Institute Symposium 2010, Harbin, China.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197191, Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233-46-69. Объем 1,0 у.п.л.

Тираж 100 экз.

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 1. СОРЕВНОВАНИЯ ПО ПРОГРАММИРОВАНИЮ.

1.1. Обзор соревнований по программированию.

1.1.1. Соревнования по программированию среди студентов.

1.1.2. Соревнования по информатике и программированию среди школьников.

1.1.3. Учебно-тренировочные сборы.

1.1.4. Летние школы.

1.1.5. Интернет-архивы задач.

1.2. Сценарии тестирования программных решений.

1.3. Системы оценки и подведения итогов соревнований по программированию.

1.3.1. Система подведения итогов студенческого чемпионата мира по программированию.

1.3.2. Система международной олимпиады школьников по информатике {ЮГ), использовавшаяся до 2009 г.

1.3.3. Новая система международной олимпиады школьников по информатике (ЮГ).

1.3.4. Системы с баллами за задачу, зависящими от времени ( Торсо(1ег, Сойе^гсез).

1.4. Системы автоматического проведения соревнований по программированию.

1.5. Задачи, решаемые в диссертационной работе.

Выводы по главе 1.

ГЛАВА 2. МЕТОДОЛОГИЯ ПРОВЕДЕНИЯ СОРЕВНОВАНИЙ ПО

ИНФОРМАТИКЕ И ПРОГРАММИРОВАНИЮ.

2.1. Требования к проведению соревнований по программированию

2.1.1. Требования к проведению соревнований.

2.1.2. Требования к системе автоматического управления соревнованиями.

2.2. Организация очной командной олимпиады школьников по программированию.

2.2.1. Организационная структура олимпиады.

2.2.2. Схема проведения заключительного этапа.

2.2.3. Организация отбора на олимпиаду.

2.2.4. Принцип формирования комплекта задач.

2.3. Организация серии интернет-соревнований.

2.3.1. Требования к серии интернет-соревнований.

2.3.2. Сравнительный анализ существующих интернет-соревнований

2.3.3. Схема цикла интернет-олимпиад.

2.4. Методология проведения олимпиад по информатике и программированию с использованием автоматической системы управления соревнованиями.

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

Выводы по главе 2.

ГЛАВА 3. ФОРМАЛЬНЫЕ МЕТОДЫ ОПИСАНИЯ СЦЕНАРИЕВ ТЕСТИРОВАНИЯ ПРОГРАММНЫХ РЕШЕНИЙ И ПОДВЕДЕНИЯ

ИТОГОВ СОРЕВНОВАНИЙ.

3.1. Сценарии тестирования программных решений.

3.1.1. Левоконтекстные терминальные грамматики.

3.1.2. Задание сценариев тестирования левоконтекстными терминальными грамматиками.

3.1.3. Обработка ошибок при выполнении сценариев.

3.1.4. Реализация выполнения сценария тестирования с использованием стековой машины.

3.1.5. Алгоритмы анализа контекстно-свободных грамматик с возможностью бесконечных цепочек порождений.

3.1.6. Верификация свойств сценариев тестирования.

3.1.7. Пример задания и анализа сценария тестирования.

3.2. Унифицированный метод обработки результатов и подведения итогов соревнований для различных систем оценки.

3.2.1. Модель подведения итогов соревнования.

3.2.2. Реализация различных систем оценки с использованием предлагаемого подхода.

Выводы по главе 3.

ГЛАВА 4. СИСТЕМА АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ СОРЕВНОВАНИЯМИ.

4.1. Компонентная модель построения системы автоматического управления соревнованиями.

4.2. Модель данных в системе автоматического управления соревнованиями.

4.2.1. Описание классов в модели данных.

4.2.2. Сравнение с другими системами управления соревнованиями по программированию.

4.3. Работа со сценариями тестирования.

4.3.1. Реализация работы со сценариями тестирования.

4.3.2. Сравнение с другими системами управления соревнованиями по программированию.

4.4. Подведение итогов соревнований.

4.4.1. Реализация подведения итогов соревнований.

4.4.2. Сравнение с другими системами управления соревнованиями по программированию.

4.5. Итоговое сравнение с другими системами управления соревнованиями по программированию.

Выводы по главе 4.

ГЛАВА 5. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ.

5.1. Проведение олимпиад по информатике и программированию.

5.1.1. Всероссийская командная олимпиада школьников по информатике и программированию.

5.1.2. Цикл интернет-олимпиад.

5.1.3. Индивидуальная олимпиада школьников по информатике и программированию.

5.1.4. Кубок по программированию Russian Code Сир.

5.2. Внедрение в учебный процесс.

5.2.1. Обучение школьников.

5.2.2. Тестирования абитуриентов.

5.2.3. Обучение студентов.

5.2.4. Использование олимпиадного подхода для проверки некоторых научных результатов.

Выводы по главе 5.

Актуальность проблемы. Различные творческие конкурсы для школьников и студентов проводятся с конца XIX века [52]. Предметные олимпиады в СССР проводились с 1934 г., когда была проведена первая "олимпиада школьников Ленинграда по математике [52]. В 1985 г. в Ленинграде была проведена первая олимпиада школьников по информатике [29, 52]. В США в 1977 г. был проведен первый межвузовский чемпионат по программированию, который в дальнейшем был преобразован в чемпионат мира по программированию среди студентов, проводимый АСМ [78]. В России соревнования студентов по программированию проводятся с 1996 г., когда впервые был проведен полуфинал чемпионата мира по программированию, который также стал чемпионатом России по программированию [72]. С 2000 г. число различных соревнований по информатике и программированию для школьников и студентов постоянно растет.

Рост числа соревнований по информатике и программированию обусловлен рядом причин.

Олимпиады поддерживаются университетами, поскольку участие в олимпиадах позволяет сформировать у школьников и студентов интерес к информатике и программированию, вовлечь школьников в занятия информатикой и программированием, стимулировать тем самым поступление на специальности соответствующего профиля. Большое число олимпиад проводится Санкт-Петербургским национальным исследовательским университетом информационных технологий, механики и оптики (НИУ ИТМО) при участии автора данной работы [42, 51, 54, 56, 84, 88, 94], Московским государственным университетом, Саратовским государственным университетом, Новосибирским государственным университетом, Уральским федеральным университетом, Петрозаводским государственным университетом и многими другими университетами, в том числе за рубежом [6, 53, 57, 59, 62, 63, 66, 79]. Олимпиады позволяют найти и отобрать способных школьников и студентов, которые в дальнейшем могут обучаться по углубленным программам. Олимпиады способствуют усвоению фундаментальных знаний из области теоретической информатики, что позволяет привлечь победителей и призеров олимпиад к занятиям наукой

55]Г

Поддержка олимпиад осуществляется государством через гранты Министерства образования и науки РФ, а также компаниями, специализирующимися на разработке программного обеспечения. При этом, например, под руководством автора в 2011 г. НИУИТМО совместно с компанией Mail.Ru Group был проведен кубок Russian Code Сир. Соревнования по программированию проводятся компаниями Google, Microsoft, Facebook, Яндекс. С 1997 г. генеральным спонсором чемпионата мира по программированию является корпорация IBM. Для компаний олимпиады представляют собой способ поиска и отбора высококвалифицированных сотрудников, а также предоставляют возможность для распространения информации об инженерной и исследовательской работе, проводимой компаниями. Особую важность для России представляет популяризация профессии программиста как творческого труда, требующего высокой квалификации.

Одним из важных отличий соревнований по информатике и программированию от большинства предметных олимпиад является автоматизация проверки работ участников. Если проверку работ, например, на олимпиадах по математике, жюри проводит вручную, выставляя оценки, то при проведении олимпиад по информатике и программированию проверка осуществляется в реальном времени с использованием автоматизированных систем управления соревнованиями. Первые системы, например PC, разработанная в Калифорнийском университете [74] и использовавшаяся на чемпионате мира по программированию с 1989 по 2009 г., были лишь вспомогательным инструментом, предназначенным для технической поддержки жюри, осуществлявшего ручную проверку решений. В России одной из первых систем автоматической проверки решений была разработанная в СПбГИТМО (ТУ) и СПбГУ в 1996 г. система NPC. Она была написана в форме набора скриптов операционной системы Windows и осуществляла поддержку только используемой в то время формы соревнований. В дальнейшем при активном участии автора диссертации в СПбГУ ИТМО была разработана и внедрена в проведение олимпиад по информатике и программированию автоматическая система управления соревнованиями PCMS [85, 90, 92].

Поскольку проверка и подведение итогов соревнования по программированию происходят в реальном времени, важным является надежность системы управления соревнованиями. Например, в 2011 г. при проведении в Бухаресте и Виннице полуфинальных соревнований в Юго-Восточном Европейском регионе из-за проблем в автоматической системе проведения не удалось осуществлять надежное взаимодействие между двумя местами проведения. Кроме того, из-за недостаточной производительности использованной системы управления соревнованиями (PC, версия 8.6, 2009 г.), не удалось объективно подвести итоги соревнования и выявить победителей. В частности, ряд попыток решения задач вообще не был проверен [75, 80].

Помимо собственно олимпиад по информатике и программированию, на их основе был предложен и развивается соревновательный подход в образовании [6, 8, 15- 18, 21, 31, 38, 40, 43-49, 84]. Так, в 2003 г. оргкомитетом чемпионата мира по программированию среди студентов был организован Competitive Learning Institute (Институт соревновательного обучения). В России использование соревновательного подхода в обучении развивалось при активном участии автора [88, 89].

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

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

В соответствии с паспортом специальности 05.13.06. «Автоматизация и управление технологическими процессами и производствами (образование)» областями исследования, проводимыми в диссертации, в частности, являются «3. Методология, научные основы и формализованные методы построения автоматизированных систем управления технологическими процессами (АСУТП) и производствами (АСУП), а также технической подготовкой производства (АСТПП) и т. д.» и «18. Средства и методы проектирования технического, математического, лингвистического и других видов обеспечения АСУ».

Цель диссертационной работы — разработка методологических и технических решений для организации и проведения олимпиад по информатике и программированию. Для этого были поставлены и решены следующие задачи:

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

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

3. Создать автоматическую систему управления соревнованиями по программированию.

4. Внедрить разработанные методологию и автоматическую систему в практику проведения олимпиад по информатике и программированию.

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

Научная новизна. На защиту выносятся следующие результаты, обладающие научной новизной.

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

2. Унифицированный метод обработки результатов и подведения итогов соревнований в автоматической системе управления соревнованиями по программированию.

3. Модель представления данных о соревнованиях, позволяющая осуществлять эффективное переиспользование материалов соревнований.

Методы исследования. В работе использованы методы теории формальных языков, дискретной математики и теории алгоритмов.

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

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

1. При проведении олимпиад по информатике и программированию, в том числе: о Всероссийской командной олимпиады школьников по информатике и программированию, которая проводится под руководством автора с 2000 г. по настоящее время; о серии интернет-олимпиад школьников по информатике и программированию; о индивидуальной олимпиады по информатике и программированию; о олимпиады Russian Code Сир.

2. В учебном процессе на кафедре «Компьютерные технологии» НИУ ИТМО при проведении практических занятий по курсам «Дискретная математика и алгоритмы», «Алгоритмы и структуры данных», «Теория формальных языков», «Языки программирования и методы трансляции», «Алгоритмы алгебры и теории чисел».

3. В учебном процессе на кафедре «Компьютерные технологии» НИУ ИТМО при проведении вступительных тестирований абитуриентов с 2000 по 2007 г.

4. В дополнительном обучении информатике и программированию школьников, например, в Физико-математическом лицее № 239 (Санкт-Петербург).

Апробация результатов работы. Основные положения диссертационной работы докладывались на научно-методических конференциях «Современные технологии обучения» (СПбГЭТУ, 2002), «Телематика-2004» (СПбГУ ИТМО), «Конференция молодых ученых СПбГУИТМО» (2005), «Телематика-2005» (СПбГУ ИТМО), «Телематика

2009» (СПбГУ ИТМО), «Телематика-2010» (СПбГУ ИТМО), «Competitive Learning Institute Symposium» (Харбин, Китай, 2010).

Внедрение результатов работы. Результаты диссертации использованы при выполнении научно-исследовательских работ Министерства образования и науки РФ по темам «Создание информационной обучающей системы подготовки разработчиков программного обеспечения на основе методологии, используемой в международных олимпиадах по программированию», «Разработка концепции и методического обеспечения новой технологии обучения и контроля качества образования в области программирования», «Разработка технологии создания программного обеспечения систем управления на основе автоматного подхода», а также государственных контрактов «Выполнение работ (оказание услуг) по организации и проведению Всероссийской олимпиады школьников и студентов по информатике и программированию», «Выполнение работ (оказание услуг) по созданию системы повышения квалификации педагогических кадров в области информационных технологий на базе интегрированной информационной образовательной среды и комплекса интернет-олимпиад и творческих конкурсов».

Публикации. На тему диссертации опубликовано 13 научных работ, в том числе шесть статей, из которых две в журналах из перечня ВАК.

Награды. В 2003 г. автор в составе авторского коллектива стал лауреатом премии Президента Российской Федерации в области образования за научно-практическую работу для образовательных учреждений высшего профессионального образования «Разработка концепции и создание организационной структуры, учебно-методического и программного обеспечения инновационной системы подготовки высококвалифицированных кадров в области информационных технологий».

В 2004 г. автору была присуждена премия ACMICPC Founder's Award за вклад в развитие чемпионата мира по программированию в Европе.

В 2008 г. автору была присуждена премия ACM ICPC Distinguished Coach Award за выдающиеся достижения как тренеру команд НИУ ИТМО на чемпионате мира по программированию.

Автор является дважды призером чемпионата мира по программированию (2000 г.— четвертое место, 2001 г. — третье место), тренером трех команд — чемпионов мира по программированию (2004, 2008, 2009 гг.) и трех команд, занявших третье место на этом чемпионате (2003, 2005, 2007 гг.).

В 2009 г. автору присуждена Молодежная премия Санкт-Петербурга в области информационных технологий.

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

Выводы по главе 5

1. С использованием разработанной методологии в главе 2 при участии автора организованы Всероссийская командная олимпиада школьников по информатике и программированию, цикл интернет-олимпиад для школьников, индивидуальная олимпиада школьников по информатике и программированию, соревнование Russian Code Сир.

2. Для технической поддержки соревнований используется разработанная при участии автора и описанная в главе 4 система автоматического управления соревнованиями PCMS.

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

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

ЗАКЛЮЧЕНИЕ

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

В результате диссертационных исследований получены следующие результаты.

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

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

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

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

5. Разработана методология проведения олимпиад по информатике и программированию с использованием автоматической системы проведения соревнованиями.

6. С использованием разработанной методологии проведения олимпиад и созданной системы автоматического управления соревнованиями по программированию проведены различные олимпиады, в том числе: о Всероссийская командная олимпиада школьников по информатике и программированию (проводится под руководством автора с 2000 г. по настоящее время); о серия интернет-олимпиад школьников по информатике и программированию; о индивидуальная олимпиада по информатике и программированию; о олимпиада Russian Code Сир.

7. Разработанные методология проведения олимпиад и система управления соревнованиями внедрены в учебный процесс в НИУ ИТМО и ФМЛ № 239. Это позволило в 2 - 4 раза снизить временные затраты преподавателя на проверку работ и повысить качество покрытия материала контрольными заданиями.

8. За организацию и проведение Всероссийской командной олимпиады школьников по информатике и программированию и разработку автоматической системы управления соревнованиями PCMS в 2003 г. автор в составе коллектива стал лауреатом премии Президента Российской Федерации в области образования за научно-практическую работу для образовательных учреждений высшего профессионального образования «Разработка концепции и создание организационной структуры, учебно-методического и программного обеспечения инновационной системы подготовки высококвалифицированных кадров в области информационных технологий».

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

1. Печатные издания на русском языке

2. Алексеев A.B. Всероссийская олимпиада по информатике // Детская компьютерная газета «Компутер». Красноярск. 1991. № 2, с. 2, 3.

3. Андерсон Д. Дискретная математика и комбинаторика. М.: Вильяме, 2004. 960 с.

4. Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструментарий. М.: Вильяме, 2008. 652 с.

5. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции (Том 1. Синтаксический анализ). М.: Мир, 1978. -612 с.

6. Ахо А., Хопкрофт Д., Ульман Дж. Структуры данных и алгоритмы. М.: Вильяме, 2010. 400 с.

7. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя. М.: ДМК Пресс. 2001. 432 с.

8. Васильев В. Н., Елизаров Р. А., Парфенов В. Г., Столяр С. Е. Организация дистанционного обучения программистов / Тезисы докладов Всероссийской научно-методической конференции «Телематика'98». СПбГУ ИТМО. 1998, с. 172, 173.

9. Вельдер С. Э., Лукин М. А., Шалыто А. А., Яминов Б. Р. Верификация автоматных программ. СПб: Наука, 2011. 242 с.

10. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский Диалект, 2008.-352 с.

11. Волынский Ю. Задачи Всесоюзной олимпиады по основам информатики 1990 г. // Вычислительная техника и ее применение. 1991. №2, с. 36-40.

12. Гамма Э., Хэлм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2001. 325 с.

13. Гладкий A.B. Формальные грамматики и языки. М.: Наука, 1973. -368 с.

14. Дейтел Х.М., Дейтел П. Дж., Сантри С. И. Технологии программирования на Java 2. В трех томах. М.: Бином-Пресс, 2003. 560 с.

15. Иванов И. П., Чеповский A.M., Чернышев C.B. Воспитание программистов на базе олимпиад по программированию / Труды Седьмой международной конференции памяти академика А.П. Ершова «Перспективы систем информатики». Новосибирск. 2009, с. 56, 57.

16. Казаков М. А., Васильев В. H., Корнеев Г. А., Парфенов В. Г, Шалыто А. А. Три кита подготовки программистов // Открытые системы. 2009. № 3, с. 54 56.

17. Касаткин В. Н. Олимпиада по информатике: какой ей быть. // Информатика и образование. 1987. № 5, с. 95 96.

18. Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. Новосибирск: НГУ, 1995. 112 с.

19. Касьянова Е. В., Касьянова С. Н. Подготовка одаренных детей к олимпиадам по программированию / Труды Седьмой международной конференции памяти академика А.П. Ершова «Перспективы систем информатики». Новосибирск. 2009, с. 63, 64.

20. Кирюхин В. М. Информатика. Всероссийские олимпиады. Выпуск 1 М.: Просвещение, 2008.

21. Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. М.: Бином, 2007. -271 с.

22. Кирюхин В.М. Первая Международная олимпиада по информатике. // Квант. 1989. № 12, с. 64 66.

23. Кирюхин В.М. Методика проведения и подготовки к участию в олимпиадах по информатике: Всероссийская олимпиада школьников. М.: Бином, 2011. 271 с.

24. Кларк Э. М., Грамберг О., Пелед Д. Верификация моделей программ. Model Checking М.: МЦНМО, 2002. 416 с.

25. Кормен Т. X, Лейзерсон Ч. И., Ривест Р. Л., Штайн К Алгоритмы: Построение и анализ, М.: Вильяме, 2005. 1296 с.

26. Котляров В. П., Коликова Т. В. Основы тестирования программного обеспечения. М.: Бином, 2006. 288 с.

27. Матиясевич Ю. Задачи первых ленинградских олимпиад по информатике // Информатика и образование. 1988. № 3, с. 85 87.

28. Мелихов А. Н., Бернштейн Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.-352 с.

29. Непейвода Н. Н., Рыков В. В. Профессия программиста — это удача или ловушка? / Труды V международной научно-практической конференции «Современные информационных технологии и ИТ-образование» МГУ. 2010, с. 109 112.

30. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация. СПб.: Питер, 2002. 688 с.

31. Романовский И. В. Дискретный анализ. СПб.: Невский диалект, 1999.-240 с.

32. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ. Структуры данных. Сортировка. Поиск. М.: Б1а8ой, 2001. 687 с.

33. Фаулер М. Архитектура корпоративных программных приложений. М.: Вильяме, 2004. 544 с.

34. Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник. М.: Мир, 1965, с. 68-75.

35. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильяме, 2002. 528 с.

36. Чурина Т. Г. Методика подготовки к олимпиадам по программированию / Труды Седьмой международной конференции памяти академика А.П. Ершова «Перспективы систем информатики». Новосибирск. 2009, с. 138 143.

37. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 2004. 296 с.

38. Шилов Н. В., Шилова С. О. Головоломки для 1Т'ишников? / Труды V международной научно-практической конференции «Современные информационных технологии и ИТ-образование» МГУ. 2010, с. 352-359.

39. Командный чемпионат мира по программированию АСМ 2010/2011. Северо-Восточный Европейский регион / Под ред. проф. В. Н. Васильева и проф. В. Г. Парфенова. СПбГУ ИТМО, 2010.-244 с.

40. Одиннадцатая Всероссийская олимпиада школьников по информатике и программированию / Под ред. В. Н. Васильева, В. Г. Парфенова, А. С. Станкевича. СПбГУ ИТМО, 2010. 262 с.

41. Печатные издания на английском языке

42. Enström Е., Kreitz G., Niemelä F., Söderman P., Kann V. Five Years with Kattis Using an Automated Assessment System in Teaching /41st ASEE/IEEE Frontiers in Education Conference. 2011, pp. 123-128.

43. Gárcia-Mateos G., Fernández-Alemán J. L. A course on algorithms and data structures using on-line judging / ITiCSE '09: Proc. 14th ann. SIGCSE conf. on Innovation and technology in Comp. Sei. education, ACM. 2009, pp. 45-49.

44. Ihantola P. et al. Review of Recent Systems for Automatic Assessment of Programming Assignments. Koli Calling 2010. Koli. Finland, pp. 33 -38.

45. Rosenbloom A. Running a programming contest in an introductory computer science course. / ITiCSE '09: Proc. 14th ann. SIGCSE conf. on Innovation and technology in Comp. Sei. education. ACM. 2009, p. 347.

46. Suleman H. Automatic marking with Sakai / SAICSIT'08: Proc. 2008 ann. research conf. of the South African Inst, of Comp. Sei. and Information Technologists on IT research in developing countries. ACM. 2008, pp. 229 236.

47. Vlasov D. The Open Cup and Petrozavodsk Programming Training Camp / Collaborative Learning Institute Symposium. 2010, p. 37.

48. Werth T. DOMjudge An Automated Judging System for Programming Contests / Collaborative Learning Institute Symposium. 2010, p. 38.1721. Ресурсы сети интернет

49. Сайт Russian Code Сир. http://russiancodecup.ru.

50. Сайт Всероссийской командной олимпиады школьников по программированию, http://neerc.ifmo.ru/scliool.

51. Сайт Всероссийской олимпиады школьников, http://rosolymp.ru

52. Сайт Всесибирской олимпиады им. И. В. Поттосина. http://olimpic.nsu.ru.

53. Сайт индивидуальной олимпиады по информатике и программированию, http://neerc.ifino.ru/school/ioip.

54. Сайт инициативы «Сохраним в университетах лучших!», http:// savethebest.ru.

55. Сайт интернет-олимпиад по информатике. http://neerc.ifino.ru/school/io.

56. Сайт интернет-соревнований Саратовского государственного университета, http://acm.sgu.ru.

57. Сайт интернет-соревнований университета Вальядолид, Испания. http://acm.uva.es.

58. Сайт интернет-соревнований Уральского федерального университета, http://acm.timus.ru.

59. Сайт летней компьютерной школы, http://lksh.ru.

60. Сайт международной олимпиады по информатике. http://ioinformatics.org.

61. Сайт московских олимпиад по информатике, http://acm.msu.ru.

62. Сайт олимпиад школьников по информатике США. http ://www.uwp.edu/ sws/usaeo,

63. Сайт «Открытого кубка» по программированию им. Е.В. Панкратьева, www.opencup.ru.

64. Сайт открытой олимпиады школьников по программированию. http://olympiads.ru/zaoch.

65. Сайт Петрозаводских учебно-тренировочых сборов, http ://karelia. snarknews .info.

66. Сайт системы DOMjudge. http://domjudge.sourceforge.net.

67. Сайт проверяющей системы dudge. http://c0de.g00gle.c0m/p/dudge.

68. Сайт проверяющей системы KATTIS. / http://kattis.csc.kth.se.

69. Сайт Российского совета олимпиад школьников. / http://rsr-olymp.ru.

70. Сайт Санкт-Петербургского тренировочного центра. / http://spbtc.ru.

71. Сайт Северо-восточного Европейского полуфинала чемпионата мира по программированию. / http://neerc.ifmo.ru.

72. Сайт системы проведения соревнований по программированию eJudge. / http://ejudge.ru.2

73. Сайт системы проведения соревнований по программированию PC . http://www.ecs.csus.edu/pc2/.

74. Сайт соревнований по программированию CodeForces. http://codeforces.ru.

75. Сайт соревнований по программированию TopCoder. http://topcoder.com/tc.

76. Сайт Хорватских интернет-олимпиад по информатике. http://www.hsin.hr/coci.

77. Сайт чемпионата мира по программированию, http://cm.baylor.edu.

78. Сайт чемпионата Урала, http://acm.usu.ru.

79. Сайт Юго-восточного Европейского полуфинала чемпионата мира по программированию, http://acm.ro.

80. W3C XML Schema 2 specification, Duration description. http://www.w3 .org/TR/200 l/REC-xmlschema-2-20010502/#duration.1. Публикации автора

81. Статьи в журналах из перечня ВАК

82. Станкевич А. С. Общий подход к подведению итогов соревнований по программированию при использовании различных системоценки // Компьютерные инструменты в образовании. 2011. № 2, с. 27-38.

83. Станкевич А. С., МавринП. Ю. Использование левоконтекстных грамматик для описания сценариев автоматического тестирования программных решений // Дистанционное и виртуальное обучение. 2011. №8, с. 36-48.1. Другие статьи

84. Станкевич А. С., Харченко Т. В. Всероссийские интернет-олимпиады по информатике и программированию // Компьютерные инструменты в образовании. 2002. № 3 4, с. 60 - 70.

85. Станкевич А. С., Елизаров Р. А. Система управления соревнованиями по программированию как система обработки данных // Телекоммуникации и информатизация образования. 2003. № 3, с. 64-85.

86. Станкевич А. С, Маврин П. Ю., Корнеев Г. А., Шалыто А. А. Моделирование жизненного цикла компоненты программного комплекса с использованием диаграмм состояний // Информатизация и связь. 2008. № 2, с. 20-23.

87. Станкевич А. С. Использование алгоритмов анализа левоконтекстных терминальных грамматик в задачах автоматического тестирования программ // Труды СПИИРАН. 2010. Вып. 13, с. 106-121.1. Материалы конференций

88. Станкевич А. С. О проведении олимпиад школьников по программированию / Материалы VIII международной конференции «Современные технологии обучения». СПбГЭТУ. 2002, с. 326, 327.

89. Станкевич А. С., Корнеев Г. А. Методы тестирования решений задач на соревнованиях по программированию / Труды II межвузовской конференции молодых учёных. СПбГУ ИТМО. 2005, с. 36-40.

90. Станкевич А. С., Корнеев Г. А., Маврин П. Ю. Построение компонентных систем с поддержкой динамической реконфигурации / Труды XVI Всероссийской научно-методической конференции «Телематика-2009». СПбГУ ИТМО. 2009, с. 289.

91. Stankevich A., Parfenov V., Tsarev F. Internet Olympiads in Informatics for High School Students / Competitive Learning Institute Symposium 2010, Harbin, China.