Содержание к диссертации
Введение
ГЛАВА 1. Соревнования по программированию
1.1. Обзор соревнований по программированию 15
1.1.1. Соревнования по программированию среди студентов 15
1.1.2. Соревнования по информатике и программированию среди школьников 20
1.1.3. Учебно-тренировочные сборы 23
1.1.4. Летние школы 24
1.1.5. Интернет-архивы задач 24
1.2. Сценарии тестирования программных решений 25
1.3. Системы оценки и подведения итогов соревнований по программированию 26
1.3.1. Система подведения итогов студенческого чемпионата мира по программированию 27
1.3.2. Система международной олимпиады школьников по информатике {ЮГ), использовавшаяся до 2009 г 29
1.3.3. Новая система международной олимпиады школьников по информатике (ЮГ) 31
1.3.4. Системы с баллами за задачу, зависящими от времени (Topcoder, Codeforces) 32
1.4. Системы автоматического проведения соревнований по программированию 33
1.5. Задачи, решаемые в диссертационной работе 35
Выводы по главе 1 36
ГЛАВА 2. Методология проведения соревнований по информатике и программированию 37
2.1. Требования к проведению соревнований по программированию .37
2.1.1. Требования к проведению соревнований 37
2.1.2. Требования к системе автоматического управления соревнованиями 39
2.2. Организация очной командной олимпиады школьников по программированию 42
2.2.1. Организационная структура олимпиады 43
2.2.2. Схема проведения заключительного этапа 46
2.2.3. Организация отбора на олимпиаду 47
2.2.4. Принцип формирования комплекта задач 51
2.3. Организация серии интернет-соревнований 52
2.3.1. Требования к серии интернет-соревнований 52
2.3.2. Сравнительный анализ существующих интернет-соревнований 54
2.3.3. Схема цикла интернет-олимпиад 57
2.4. Методология проведения олимпиад по информатике и программированию с использованием автоматической системы управления соревнованиями 62
2.5. Использование соревнований для поиска, отбора и обучения школьников и студентов, одаренных в области информатики и программирования 65
Выводы по главе 2 66
ГЛАВА 3. Формальные методы описания сценариев тестирования программных решений и подведения итогов соревнований 67
3.1. Сценарии тестирования программных решений 67
3.1.1. Левоконтекстные терминальные грамматики 70
3.1.2. Задание сценариев тестирования левоконтекстными терминальными грамматиками 75
3.1.3. Обработка ошибок при выполнении сценариев 77
3.1.4. Реализация выполнения сценария тестирования с использованием стековой машины 80
3.1.5. Алгоритмы анализа контекстно-свободных грамматик с возможностью бесконечных цепочек порождений 83
3.1.6. Верификация свойств сценариев тестирования 91
3.1.7. Пример задания и анализа сценария тестирования 99
3.2. Унифицированный метод обработки результатов и подведения итогов соревнований для различных систем оценки 104
3.2.1. Модель подведения итогов соревнования 104
3.2.2. Реализация различных систем оценки с использованием предлагаемого подхода 105
Выводы по главе 3 110
ГЛАВА 4. Система автоматического управления соревнованиями 112
4.1. Компонентная модель построения системы автоматического управления соревнованиями 114
4.2. Модель данных в системе автоматического управления соревнованиями 122
4.2.1. Описание классов в модели данных 123
4.2.2. Сравнение с другими системами управления соревнованиями по программированию 130
4.3. Работа со сценариями тестирования 134
4.3.1. Реализация работы со сценариями тестирования 134
4.3.2. Сравнение с другими системами управления соревнованиями по программированию 134
4.4. Подведение итогов соревнований 136
4.4.1. Реализация подведения итогов соревнований 136
4.4.2. Сравнение с другими системами управления соревнованиями по программированию 137
5 4.5. Итоговое сравнение с другими системами управления соревнованиями по программированию 141
Выводы по главе 4 147
ГЛАВА 5. Внедрение результатов работы 148
5.1. Проведение олимпиад по информатике и программированию 148
5.1.1. Всероссийская командная олимпиада школьников по информатике и программированию 148
5.1.2. Цикл интернет-олимпиад 150
5.1.3. Индивидуальная олимпиада школьников по информатике и программированию 154
5.1.4. Кубок по программированию Russian Code Сир 155
5.2. Внедрение в учебный процесс 156
5.2.1. Обучение школьников 156
5.2.2. Тестирования абитуриентов 157
5.2.3. Обучение студентов 158
5.2.4. Использование олимпиадного подхода для проверки некоторых научных результатов 161
Выводы по главе 5 163
Заключение 164
Список источников 167
- Соревнования по информатике и программированию среди школьников
- Организационная структура олимпиады
- Задание сценариев тестирования левоконтекстными терминальными грамматиками
- Компонентная модель построения системы автоматического управления соревнованиями
Введение к работе
Актуальность проблемы. Различные творческие конкурсы для школьников и студентов проводятся с конца XIX века [52]. Предметные олимпиады в СССР проводились с 1934 г., когда была проведена первая олимпиада школьников Ленинграда по математике [52]. В 1985 г. в Ленинграде была проведена первая олимпиада школьников по информатике [29, 52]. В США в 1977 г. был проведен первый межвузовский чемпионат по программированию, который в дальнейшем был преобразован в чемпионат мира по программированию среди студентов, проводимый АСМ [78]. В России соревнования студентов по программированию проводятся с 1996 г., когда впервые был проведен полуфинал чемпионата мира по программированию, который также стал чемпионатом России по программированию [72]. С 2000 г. число различных соревнований по информатике и программированию для школьников и студентов постоянно растет.
Рост числа соревнований по информатике и программированию обусловлен рядом причин.
Олимпиады поддерживаются университетами, поскольку участие в олимпиадах позволяет сформировать у школьников и студентов интерес к информатике и программированию, вовлечь школьников в занятия информатикой и программированием, стимулировать тем самым поступление на специальности соответствующего профиля. Большое число олимпиад проводится Санкт-Петербургским национальным исследовательским университетом информационных технологий, механики и оптики (НИУ ИТМО) при участии автора данной работы [42, 51, 54, 56, 84, 88, 94], Московским государственным университетом, Саратовским государственным университетом, Новосибирским государственным университетом, Уральским федеральным университетом, Петрозаводским государственным университетом и многими другими университетами, в том
7 числе за рубежом [6, 53, 57, 59, 62, 63, 66, 79]. Олимпиады позволяют найти и отобрать способных школьников и студентов, которые в дальнейшем могут обучаться по углубленным программам. Олимпиады способствуют усвоению фундаментальных знаний из области теоретической информатики, что позволяет привлечь победителей и призеров олимпиад к занятиям наукой |55]Г
Поддержка олимпиад осуществляется государством через гранты Министерства образования и науки РФ, а также компаниями, специализирующимися на разработке программного обеспечения. При этом, например, под руководством автора в 2011 г. НИУИТМО совместно с компанией Mail.Ru Group был проведен кубок Russian Code Сир. Соревнования по программированию проводятся компаниями Google, Microsoft, Facebook, Яндекс. С 1997 г. генеральным спонсором чемпионата мира по программированию является корпорация IBM. Для компаний олимпиады представляют собой способ поиска и отбора высококвалифицированных сотрудников, а также предоставляют возможность для распространения информации об инженерной и исследовательской работе, проводимой компаниями. Особую важность для России представляет популяризация профессии программиста как творческого труда, требующего высокой квалификации.
Одним из важных отличий соревнований по информатике и программированию от большинства предметных олимпиад является автоматизация проверки работ участников. Если проверку работ, например, на олимпиадах по математике, жюри проводит вручную, выставляя оценки, то при проведении олимпиад по информатике и программированию проверка осуществляется в реальном времени с использованием автоматизированных систем управления соревнованиями. Первые системы, например PC, разработанная в Калифорнийском университете [74] и использовавшаяся на чемпионате мира по программированию с 1989 по 2009 г., были лишь вспомогательным инструментом, предназначенным для технической
8 поддержки жюри, осуществлявшего ручную проверку решений. В России одной из первых систем автоматической проверки решений была разработанная в СПбГИТМО (ТУ) и СПбГУ в 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].
В связи с изложенным актуальными являются две проблемы: разработка методологии проведения олимпиад по информатике и
9 программированию, и разработка и внедрение технических решений для проведения олимпиад.
Методология должна систематизировать накопленный опыт организации и проведения олимпиад в стране и за рубежом. В рамках методологии необходимо сформулировать и обосновать требования к проведению олимпиад, включающие требования к автоматической системе управления соревнованиями. Технические решения должны поддерживать разработанную методологию и включать разработку автоматической системы управления соревнованиями по программированию, удовлетворяющую требованиями, сформулированным в рамках предложенной автором методологии.
В соответствии с паспортом специальности 05.13.06. «Автоматизация и управление технологическими процессами и производствами (образование)» областями исследования, проводимыми в диссертации, в частности, являются «3. Методология, научные основы и формализованные методы построения автоматизированных систем управления технологическими процессами (АСУТП) и производствами (АСУП), а также технической подготовкой производства (АСТПП) и т. д.» и «18. Средства и методы проектирования технического, математического, лингвистического и других видов обеспечения АСУ».
Цель диссертационной работы — разработка методологических и технических решений для организации и проведения олимпиад по информатике и программированию. Для этого были поставлены и решены следующие задачи:
Разработать методологию проведения олимпиад по информатике и программированию с использованием автоматической системы управления соревнованиями.
Разработать формальные методы описания сценариев тестирования программных решений, унифицированный метод обработки результатов и подведения итогов соревнований, модель
10 представления данных в системе, обеспечивающую эффективное переиспользование материалов олимпиад.
Создать автоматическую систему управления соревнованиями по программированию.
Внедрить разработанные методологию и автоматическую систему в практику проведения олимпиад по информатике и программированию.
Внедрить разработанные методологию и автоматическую систему в учебный процесс при работе со школьниками, абитуриентами и студентами.
Научная новизна. На защиту выносятся следующие результаты, обладающие научной новизной.
Формальный метод описания сценариев тестирования программных решений на основе левоконтекстных терминальных грамматик, позволяющий проводить автоматическую верификацию некоторых свойств сценариев.
Унифицированный метод обработки результатов и подведения итогов соревнований в автоматической системе управления соревнованиями по программированию.
Модель представления данных о соревнованиях, позволяющая осуществлять эффективное переиспользование материалов соревнований.
Методы исследования. В работе использованы методы теории формальных языков, дискретной математики и теории алгоритмов.
Достоверность научных положений, выводов и практических рекомендаций, полученных в диссертации, подтверждается корректным обоснованием постановок задач, точной формулировкой критериев, а также результатами внедрения методологии и технических решений, предложенных в диссертации, на практике.
Практическое значение. В результате исследований, проведенных в диссертации, разработаны методология проведения олимпиад по информатике и программированию и автоматическая система управления соревнованиями по программированию PCMS, которые используются:
1. При проведении олимпиад по информатике и программированию, в том числе: о Всероссийской командной олимпиады школьников по информатике и программированию, которая проводится под руководством автора с 2000 г. по настоящее время; о серии интернет-олимпиад школьников по информатике и программированию; о индивидуальной олимпиады по информатике и программированию; о олимпиады Russian Code Сир.
В учебном процессе на кафедре «Компьютерные технологии» НИУ ИТМО при проведении практических занятий по курсам «Дискретная математика и алгоритмы», «Алгоритмы и структуры данных», «Теория формальных языков», «Языки программирования и методы трансляции», «Алгоритмы алгебры и теории чисел».
В учебном процессе на кафедре «Компьютерные технологии» НИУ ИТМО при проведении вступительных тестирований абитуриентов с 2000 по 2007 г.
В дополнительном обучении информатике и программированию школьников, например, в Физико-математическом лицее № 239 (Санкт-Петербург).
Апробация результатов работы. Основные положения диссертационной работы докладывались на научно-методических конференциях «Современные технологии обучения» (СПбГЭТУ, 2002), «Телематика-2004» (СПбГУ ИТМО), «Конференция молодых ученых СПбГУИТМО» (2005), «Телематика-2005» (СПбГУ ИТМО), «Телематика-
12 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 таблицами.
Соревнования по информатике и программированию среди школьников
Исторически первыми в России появились именно олимпиады школьников. Первая олимпиада школьников по информатике была проведена в Ленинграде в 1985 г.
Всероссийская олимпиада школьников по информатике проводится с 1988 г [1, 19]. Первая олимпиада была проведена в Свердловске, она носила название Всесоюзной, в ней приняли участие 80 школьников [11]. Олимпиада проводилась в два тура: один письменный и один на компьютере. Начиная с Третьей Всесоюзной олимпиады, прошедшей в 1990 г. в Харькове, оба тура олимпиады проводятся с использованием компьютеров.
В 1992 г. в Могилеве прошла единственная Межгосударственная олимпиада школьников, в ней приняли участие школьники из практически всех государств бывшего СССР.
Одновременно с Всесоюзными с 1989 по 1991 г. проводились и Всероссийские олимпиады, являвшиеся республиканским этапом Всесоюзной олимпиады. Начиная с 1992 г., Всероссийские олимпиады полностью заменили Всесоюзные олимпиады по информатике.
С 2003 г. автор является членом жюри и научного комитета Всероссийской олимпиады школьников по информатике. В 2003 г., а также с 2005 г. по настоящее время автор является председателем научного комитета олимпиады.
До 2002 г. тестирование решений участников на олимпиаде проводилось с помощью скриптов в полуавтоматическом режиме в присутствии участников. В связи с ростом числа участников олимпиады, появилась необходимость внедрения на олимпиаде автоматической системы управления соревнованиями.
В отличие от студенческих олимпиад, где рассматриваются только полные решения задач, на школьных олимпиадах традиционно использовалась система оценки, когда баллы начисляются за каждый пройденный тест. Соответственно, система управления соревнованиями должна поддерживать возможность подведения итогов соревнований в соответствии с различными системами оценки.
Международная олимпиада школьников по информатике проводится с 1989 г. под эгидой ЮНЕСКО. Каждую страну представляет до четырех участников. Проводится два компьютерных тура. До 2008 г. на олимпиаде использовалась система оценки по тестам. Начиная с 2009 г., используется система оценки на основе подзадач. В каждой задаче выделяется несколько подзадач различной сложности, решение подзадачи приносит частичные баллы. Баллы за отдельные тесты обычно не начисляются. С 2011 г. Всероссийская олимпиада также использует систему оценки на основе подзадач.
Организационные и технические проблемы международной олимпиады школьников по информатике не рассматривается в данной диссертации, поскольку автор не принимал участия в ее проведении.
Городские командные олимпиады школьников по информатике и программированию проводятся в Санкт-Петербурге с 1993 г. Начиная с 1998 г., на олимпиаду в Санкт-Петербург приглашаются представители других городов. В 1998 и 1999 гг. были проведены первый и второй пилотные командные чемпионаты школьников по программированию. Проведение этих олимпиад показало, что интерес школьников к участию в командных соревнованиях высок и актуальной является задача создания масштабного очного командного соревнования для школьников, которое охватило бы по возможности школьников из всех регионов России и ближнего зарубежья.
В 2008 г. Российским союзом ректоров был создан Российский совет олимпиад школьников (РСОШ), которому было поручено курировать все олимпиады, кроме олимпиад цикла Всероссийской олимпиады. В рамках РСОШ олимпиады должны стать альтернативным способом поступления в вузы, наряду с ЕГЭ. В связи с этим актуальной является задача организации олимпиады для школьников по информатике и программированию в рамках олимпиад РСОШ.
1.1.3. Учебно-тренировочные сборы
Для подготовки к олимпиадам для студентов и школьников регулярно проводятся учебно-тренировочные сборы.
Студенческие сборы проводятся с 2002 г. в Петрозаводске два раза в год — в январе и августе. На сборы приглашаются команды, успешно выступившие на полуфинальных соревнованиях чемпионата мира. Сборы проходят в течение 9-11 дней, каждый день проводится тренировочное соревнование. С 2003 г. автор является членом жюри сборов, за период с 2003 по 2011 гг. им для сборов были разработаны 40 учебных соревнований, содержащие около 400 задач.
Организационная структура олимпиады
Организационный комитет осуществляет формирование всех остальных органов олимпиады. Организационный комитет осуществляет выбор места проведения олимпиады, ведет общую работу по проведению олимпиады.
Технический комитет осуществляет функционирование компьютеров и необходимого телекоммуникационного оборудования для проведения олимпиады. Сотрудники технического комитета подготавливают рабочие места участников, организуют доступ участников через сеть к серверам, осуществляющим управление соревнованием и проверку решений. При проведении отдельных туров олимпиады через интернет технический комитет осуществляет поддержку функционирования соответствующих вебсерверов.
Жюри олимпиады готовит задачи для олимпиады. Подготовка задачи включает в себя:
Формулировку идеи задачи, основанную на математической либо технической проблеме, решение которой возможно с использованием компьютерной программы.
Написание условия задачи, содержащего необходимые для решения: постановку задачи, формат входных и выходных данных, ограничения на входные данные.
Подготовку решения задачи.
Разработку проверяющей программы, позволяющей проверять корректность решения задачи участниками соревнования.
Разработку системы тестов для задачи.
Тестирование комплекса материалов задачи с использованием автоматической системы управления соревнованиями.
Кроме того, жюри олимпиады занимается рассмотрением апелляций участников принятием решений в спорных ситуациях во время олимпиады.
Команда волонтеров является промежуточным звеном между организаторами олимпиады (оргкомитетом, техническим комитетом и жюри) и участниками. Волонтеры осуществляют доставку материалов олимпиады до участников, помогают с настройкой и конфигурированием оборудования, осуществляют контроль за соблюдением участниками правил соревнований.
Российский союз ректоров, начиная с 2008 г., курирует проведение олимпиад. Для этого был создан Российский совет олимпиад школьников (РСОШ) [70]. В требованиях к проведению олимпиад содержится организационная структура, которую необходимо создать для проведения любой олимпиады под контролем РСОШ. Отметим, что организационная структура Всероссийской командной олимпиады школьников по информатике и программированию, описанная в работе и созданная при участии автора, разрабатывалась ранее — начиная с 2000 г.
Рассмотрим основные отличия описанной структуры от структуры, предлагаемой РСОШ.
1. Организационная структура РСОШ выделяет отдельно методическую комиссию и жюри олимпиады. Методическая комиссия занимается разработкой заданий для олимпиады, а жюри— проверкой заданий. Данное разделение не актуально для олимпиад по информатике и программированию с автоматической системой проверки. Можно считать, что функции методической комиссии в разработанной структуре выполняет жюри, а функции жюри выполняет автоматическая система управления соревнованиями. Однако часть функций жюри, например принятие решений в спорных ситуациях, остается у жюри.
2. РСОШ не требует формирования технического комитета. Однако проведение олимпиад по информатике и программированию требует монтажа и настройки сложного оборудования и программного обеспечения, поэтому для проведения олимпиады необходим технический комитет.
3. РСОШ не требует привлечения команды волонтеров. Для проведения любой олимпиады необходимы помощники, однако этот вопрос не рассмотрен в документе РСОШ.
4. РСОШ требует, чтобы сформированные оргкомитет, методическая комиссия и жюри не имели общих членов. Это требование недостаточно обосновано и, по нашему мнению, не является существенным.
Задание сценариев тестирования левоконтекстными терминальными грамматиками
Рассмотрим процесс тестирования программного решения. Для каждого этапа работы над решением создадим нетерминал. Если этапы тестирования естественным образом объединяются в группы, для каждой из них также создадим нетерминал. При этом группы могут быть произвольным образом организованы в иерархическую структуру.
Для каждого действия над тестируемым решением рассмотрим все возможные его исходы. Каждый такой исход обозначим терминалом. Исходы, аналогичные по смыслу, можно обозначить одинаковыми терминалами.
Действия над решениями можно условно разделить на два класса.
К первому классу относятся основные этапы проверки решения, в результате которых состояние решения изменяется. Примерами таких действий являются: компилирование решений, запуск решения на тесте, отправка сообщения о результатах проверки решения участнику соревнования. Будем называть такие действия атомарными.
Рассмотрим атомарное действие с нетерминалом А. Для каждого возможного исхода этого действия а добавим в грамматику правило:
А — а.
Второй класс действий составляют операции принятия решения о дальнейшей проверке решения. При выполнении этих действий анализируются исходы одного или нескольких последних действий (обычно атомарных) и принимается решение о дальнейших действиях по проверке решения. Такие действия будем называть контролирующими.
Рассмотрим контролирующее действие с нетерминалом С. Для каждого такого действия рассмотрим все возможные условия, которые анализируются этим действием. В соответствии с моделью, это исходы одного или нескольких последних действий. Пусть анализируются исходы к последних действий. Рассмотрим последовательности длины к из терминалов, которые описывают исходы последних к действий с тестируемым решением. Для каждой такой последовательности а рассмотрим соответствующие действия, которые надо провести с решением в этом случае. Пусть эти действия задаются строкой из нетерминалов . Тогда добавим в грамматику правило:
При этом обычно последним символом строки Ъ, является нетерминал, соответствующий контролирующему действию, в котором принимается решение о дальнейшем процессе проверки. Типичным использованием подобной конструкции является организация цикла (например, для последовательной проверки на тестах). В этом случае в конце используется тот же контролирующий нетерминал С.
Если в результате выполнения контролирующего действия выясняется, что контролируемая им часть проверки завершена, то строка , может быть пустой, в этом случае правило имеет вид
Нетерминалы, соответствующие иерархической группировке действий, используются для организации последовательного исполнения этапов проверки. Пусть нетерминал G соответствует группе действий над решением, состоящей из действий, описываемых последовательностью нетерминалов Ъ, (в этой последовательности могут, в частности, встречаться нетерминалы других групп действий). В этом случае добавим в грамматику правило:
Для всего процесса тестирования также заведем отдельный нетерминал S. Этот нетерминал будет стартовым нетерминалом грамматики. Пусть в процессе тестирования требуется выполнить некоторые действия, заданные строкой из нетерминалов , после которых принимается решение о дальнейшем ходе тестирования. Пусть это решение принимается при выполнении контролирующего действия С. Тогда добавим в грамматику правило:
Рассмотрим теперь организацию обработки ошибок в процессе тестирования, которые требуют для своего устранения вмешательства человека.
Для начала рассмотрим случай, когда только атомарные действия способны породить подобную ошибку. Существует два варианта для задания обработки таких ошибок в грамматике:
попытка повторения действия после устранения ошибки; принятие решения о дальнейших действиях с использованием контролирующих действий.
Первый вариант следует использовать в случае ошибок тестирования, после устранения которых тестирование всегда следует продолжить с того же места.
В этом случае создадим специальный нетерминал Е, которому будет соответствовать действие «устранение ошибки». Добавим в грамматику правило Е — є, которое будет применяться к нетерминалу Е после устранения ошибки.
Нетерминал, соответствующий действию, породившему ошибку, порождает нетерминал ошибки Е и повторно порождает себя, что позволяет возобновить тестирование.
Если требуется сохранить в порождаемой строке информацию о том, что при тестировании возникали ошибки, заведем терминал е, соответствующий ошибке. В атрибутах этого терминала можно сохранить информацию о возникшей ошибке. Для каждого атомарного действия А, которое способно вызвать ошибку, требующую обработки человеком, добавим в грамматику правило:
При возникновении ошибки нетерминал А раскрывается по этому правилу, и вызывается операция обработки ошибки, ассоциированная с нетерминалом Е. После устранения причины ошибки нетерминал Е будет раскрыт по правилу - ЕИ тестирование продолжится с того же места.
Если не требуется сохранять в порождаемой строке информацию об ошибках, то в вышеприведенном правиле можно терминал е не использовать, добавив вместо него в грамматику правило:
А ЕА, отметим, правда, что этого нельзя делать, если требуется получить контекстно-однозначную грамматику.
Компонентная модель построения системы автоматического управления соревнованиями
В основу архитектуры системы положена компонентная модель [12, 32, 35, 86, 92]. Различные логические модули организованы в форме компонент, взаимодействие между которыми происходит с использованием механизма предоставляемых сервисов. Компоненты, отвечающие за единый блок задач, образуют пакеты.
Каждая компонента предоставляет некоторый набор сервисов и, в свою очередь, требует для работы набор сервисов. При таком построении системы разработка отдельных компонент может вестись независимо и параллельно, а результирующая система обладает большей гибкостью и допускает обновление части функциональности или добавления новой функциональности путем переработки лишь некоторых компонент, либо добавления новых. К недостаткам компонентной модели можно отнести относительную трудность замены межкомпонентных интерфейсов.
В качестве языка разработки был выбран язык Java, как обеспечивающий кроссплатформенность и относительно высокую надежность разработанного кода. Исключение составляет пакет контролируемого запуска программ участников, при реализации которого требуется учет специфики используемых операционных систем. Он разработан на языке C++.
Рассмотрим основные пакеты, реализованные в системе (рис. 5), и входящие в них компоненты. Local ( і іі I--1 ч!/ ч!/ Persistence ( Рис. 5. Основные пакеты, входящие в систему PCMS Пакет Client
Для удовлетворения требования (1) — взаимодействия с участниками соревнований — разработан пакет Client, содержащий компоненты клиентской части системы.
Основные компоненты взаимодействия с участниками:
Login — предоставляет возможность аутентификации и далее возможность клиентской часть системы выступать от имени участника во взаимодействии с серверной часть.
Contestlnfo — предоставляет информацию о текущем соревновании.
Submit — осуществляет отправку решений на проверку.
Monitor — осуществляет показ текущих результатов соревнований, если это предполагается регламентом.
Messenger — позволяет просматривать сообщения от организаторов соревнований и сообщения о результатах проверки.
FeedbackViewer — позволяет просматривать подробные результаты проверки решений.
Поскольку система может использоваться как для проведения очных соревнований, так и для проведения соревнований через Интернет, для пакета Client разработано две реализации: отдельный клиент в форме GUI-приложения на языке Java и сервлет — 0 6-приложение.
На рис. 6, 7 приведены скриншоты (7//-клиента. На рис. 6 показана таблица текущих результатов проводимой с использованием системы лабораторной работы по курсу «Дискретная математика».
