Аннотация
В данной статье показана возможность эффективного применения автоматической проверки знаний студентов по дисциплинам «Языки и методы программирования», «Теория конечных графов и ее приложения». «Прикладные задачи теории графов». Рассмотрены методические аспекты и описаны конкретные примеры задания и набор необходимых материалов для проверки. Достоинства данного подхода - оптимизация работы преподавателя, круглосуточный доступ к системе проверки знаний, самостоятелность студента при проверке заданий.
Введение
В настоящее вреся компьютеры целиком интегрированы в образовательный процесс. Дистанционные образовательные технологии, тест классы, промежуточная и итоговая аттестация, все это напрямую использует образовательное программное обеспечение. Тем самым в долгосрочной перспективе существенно снижается нагрузка на преподавателя, с пополнением базы электронных метриалов растет качество курсов. Все это стало возможно благодаря внедрению компьютеров в образовательный процесс, в том числе в дисциплинах предельно далеких от компьютерных технологий.
Рассмотрим ближе, как проходите ВУЗах обучение дисциплинам напрямую связанных с программированием, таких практикум на ЭВМ у профильных специальностей.
На первом этапе студенты учатся писать простейшие программы на бумаге, осваивают синтаксис изучаемого языка программироания. Единственной возможной системой проверки на данном этапе является проверка преподавателем вручную.
Далее обучающиеся знакомятся с системой программивания, т.е. совокупностью программных средств я помощью которой текст на формальном языке (языке программирования) преобразуется в исполняемый файл для конкретной вычислительной системы. Студенты пишут простейшие программы, направленные на освоение алгоритмических конструкций, на этом этапе главным критерием проверки является работоспособность написанной программы, которая проверяется преподавателем в присутствии студента.
К моменту освоения обучающимися основных алгоритмических конструкций добалявтся дополнительные критерии качества программы, такие как: 1) оформление, которое обеспечивает читабельность кода; 2) эффективность, т.е. время и объем ресурсов, затраченных на решение задачи; 3) масштабируемость, т.е. потенциал расширения функционала прогаммы, сложность его сопровождения, модификации. Здесь уже преподаватель предоставляет необходимые спецификации заданий, которые определяют требования к эффективности, используемые подходы к проектированию программ и актуальным становится процесс адекватной оценки результата. Визуальное оценивание преподавателем в данном случае неприменимо, в силу трудоемкости процесса. Проверка работоспособности на простейших примерах также не дает информации об эффективности тестируемого программного обеспечения.
В случае промышленной разработки в рамках команды все решается примением тестирования на всех этапах разработки, в том числе, привлечение специалистов, чьей единственной задачей является выявление ошибок в функционировании программного обеспечения - тестировщиков.
К образовательному процессу такой подход в чистом виде не применим, поскольку требует настройки всей инфраструкуры разработки, о которой, на данном этапе обучения, студенты имеют весьма отдаленное и поверхностное представление.
Таким образом, задача оценки качества программ в образоватлельном процессе по указанным критериям является актуальной.
Обратимся к опыту олимпиад по программмированию, в ходе их проведения приходится проверять большое количество программ участников на правильность и эффективность предлагаемого решения. Этим целям служат системы автоматической проверки программ, без них ни обходится ни одна современная олимпиада по программированию. Начиная от внутрифакультетских соревнований и заканчивая финалами чемпионатов мира по программированию. Очевидные плюсы подобного подхода к проведению соревнований: оперативность проверки, монитор соревнования, доступный участникам и жюри в режиме реального времени, неизбежные издержки: все задания должны быть очень четко сформулированы, и повышенные требования к оргкомитету (техническая поддержка, подготовка тестов). Олимпиады - передний край образовательного процесса, именно на олимпиадах впервые появляются задания на использование самых научных современных разработок.
Развитие вычислительной техники и оснащенность учебных заведений достигли уровня, позволяющего содержать достаточный серверный парк, а студентам использовать компьютерные классы и/или собственные компьютеры и Интернет-соединение для взаимодействия с образовательными ресурсами.
Сама специфика олимпиадного движения вовлекает в процесс лишь самых сильных студентов. При этом даже задачи уровня ниже среднего «вводят студентов в ступор», что делает применение готовых олимпиадных наборов в учебном процессе напрямую невозможным. Тем не менее, часть олимпиадного опыта может быть перенесена, об этом и пойдет речь ниже.
Рассмотрим некоторые методические аспекты применения систем автоматической проверки заданий, опробованные на практических занятий по дисциплинам «Языки и методы программирования», «Теория конечных графов и ее приложения», «Прикладные задачи теории графов».
- Четкая формулировка задания не допускающая двояких трактовок.
Основное требование для автоматической проверки задания это жесткий формат входных и выходных данных. Это требование относится в первую очередь к преподавателю, тем самым повышается качество и продуманность заданий в курсе.
Остановимся на этом моменте чуть более подробно. В тот момент, когда студент, выполняющий типовое задание получает после запуска программы верные значения, его первым порывом является демонстрация задания преподавателю, с практически полным пренебрежением к оформлению. Если проверку осуществляет человек, то в первую очередь в программе проверяется ее «читаемость», т.е. оформление кода и комментариев. На следующем этапе проверки проверяется работоспособность на простейших примерах. Однако проверяющий-человек легко воспринимает практически любой осмысленный формат ввода и вывода, тем самым остается очень большой разброс в форматах используемых студентами.
Специфика выполнения заданий на первичное освоение техники программирования обязывает выводить в программе подсказки пользователю, формат которых предназначен для восприятия человеком. На начальном этапе обучения студентов программированию основной упор сделан на разработку консольных приложений с максимально удобным консольным интерфейсом, т.е. с большим количеством подсказок, но без жесткой формализации содержания подсказок, их формата и т.д.
При взаимодействии же с автоматической проверяющей системой на первый план выходит именно четкое следование описанному формату, ввода-вывода, любые посторонние символы на выводе программы засчитываются системой как ошибочный ответ, наибольшую трудность представляют лишние пробельные символы, зачастую неразличимые в текстовом редакторе.
- Важным методическим аспектом является формирование у обучающегося умения формализовать задачу, свести к уже известным ему алгоритмам, разбиению крупной задач на более мелкие подзадачи.
Умение формализовать задачу можно прививать уже на первых шагах в курсе «Языки и методы программирования», например, оберткой для задачи нахождения максимального элемента в последовательности чисел на заданном отрезке может быть следующая формулировка: «Камера на трассе между городами XXX и YYY фиксирует дату-время и скорость каждого проезжающего автомобиля. Оператору камеры поступают запросы вида, какова была максимальная скорость автомобиля, проехавшего за период времени [ts; tf]». При составлении прикладной формулировки важно учесть пункт 1, т.е., задача должна остаться четкой, а формулировка однозначной.
Задания из курсов «Теория конечных графов и ее приложения», «Прикладные задачи теории графов», как правило, изначально имеют некоторую исторически сложившуюся прикладную формулировку, в этом случае весьма полезно замаскировать известный алгоритм с помощью обертки, однако это сама по себе нетривиальная методическая задача.Развитие творческих способностей с помощью решения слабо формалиованных задач подробно рассматривается в соответствующей методической литературе.
- Различные ограничения на размер входных данных соответствуют различным уровням исполнителя, от начинающего программиста до продвинутого, знакомого с основными приемами решения задач. Небольшой размер исходных данных требует лишь первичных навыков, объемы данных превышающие сотни тысяч элементов и запросов требуют знания эффективных алгоритмов и специальных структур данных.
- Опыт работы с группами студентов показывает, что более сильным студентам достаточно единожды объяснить требования к оформлению и быстродействию программы, в то время как менее внимательные будут каждый подходить с одними и теми же ошибками и недочетами. Это снижает общую эффективность занятия и существенно сужает список тем, которые можно успеть осветить в курсе. Тестирующая система берет на себя большую часть работы по первичной проверке, дисциплинируя обучающихся. Время занятия целиком расходуется на объяснение нового материала и помощь отстающим.
- Одним из практически бесплатных бонусов является проверка на плагиат, поскольку все посылки хранятся непосредственно в системе, а также ведению журнала успеваемости.
Рассмотрим, как должно выглядеть задание и набор необходимых для проверки материалов в соответствии с изложенными выше методическими аспектами на относительно простом примере.
Ограничения программы на всех тестовых наборах:
Ограничение по времени: 0.5 секунды
Ограничение по памяти: 256 мегабайт
Условие:
Имеется последовательность из N целых чисел: ац аг, .-,ах, а также К различных запросов вида Si, fi, (l<s;<fi <N), 1<і<К). Для каждого запроса s, f требуется найти максимальное число на интервале [as, af].
Входные данные (файл input.txt):
В первой строке входного файла записаны через пробел числа N и К, во второй строке записаны N чисел ац аг,...,ах - элементы последовательности, далее следует К строк, описывающих запросы: каждый запрос - два числа разделенные пробелом.
Выходные данные:
В выходном файле ваша программа должна записать К чисел по одному в каждой строке - ответы на запросы.
C точки зрения математической постановки и составления алгоритма, решающего поставленную задачу, приведенная выше постановка вполне достаточна и корректна, однако с точки зрения программиста - абсолютно неприемлема. В частности, не прописаны ограничения на количество элементов последовательности N и количество запросов и их «ширину». Эти значения являются ключевыми для выбора структуры данных и алгоритма для решения поставленной задачи.
Согласно методическому аспекту из пункта 3 разные ограничения и, следовательно, различные тестовые наборы соответствуют разным уровням, например, возможны следующие градации:
- Тестовые наборы с (1<N< 100), (1<К< 100), т.е. задача может быть решена непосредстенно («в лоб»),
- Тестовые наборы с (1<N< 100), (1<К< IO5), для решения с этими ограничениями необходимо проявить смекалку и предварительно просчитать и запомнить ответы для всех возможных запросов [as, af], а затем выводить нужные ответы.
- Тестовые наборы с (1<N< IO5), (1<К< IO5), эти ограничения уже требуют дополнительно знания основ динамического программирования и частичного предпросчёта, что позволит отвечать на запрос за время 0(1).
Программа, корректно работающая на всех тестовых наборах одной группы, получает фиксированное количество баллов.
Подготовка тестовых наборов и пакета задачи
Помощь в составлении пакета для загрузки в систему автоматического тестирования предоставляет сайт https://polygon.codeforces.com/
Рисунок 1. Заглавная страница системы polygon
Пакет задачи состоит из условия, генератора тестов, программы, проверяющей корректность ответа, правильных решений, в том числе, правильных частичных решений.
Подготовка тестовых наборов для проверки эффективности представляет собой отдельную задачу, в данном случае, для преподавателя. Вручную сформировать тест с IO5 значениями практически нереально, следовательно, требуется автоматизировать генерацию тестовых данных, написать программу- генератор тестов.
Далее требуется написать программу-чекер ответа, поскольку ответ может быть в задаче не единственным, то должна осуществляться проверка соответствия ответа условиям задачи. При длине вывода порядка IO5 осуществить ее вручную невозможно.
Далее следует этап интеграции тестовых наборов, правильных решений, программы-генератора, программы-чекера в пакет, предназначенный для загрузки непосредственно в тестирующую систему.
Страница подготовленного пакета выглядит следующим образом:
Выводы
Опыт успешного применения систем автоматической проверки, показывает, что автоматическая проверка оптимизирует работу преподавателя, повышает дисциплинированность и заинтересованность студентов. Обеспечивая круглосуточный доступ к системе проверки задания, возрастает качество и количество самостоятельной работы студентов. Подобная практика отвечает самым современным тенденциям образовательного процесса.
Литература:
- 1. Корнеев Г.А., Елизаров Р.А. Автоматическое тестирование решений на соревнованиях по программированию // Телекоммуникации и информатизация образования №1. - Москва. - 2003. - с. 61-73.
- 2. Быстрова Ю.Ю., Иномистов В.Ю. Применение системы автоматического тестирования программ в учебном процессе // Труды III Международной научно-практической конференции "Современные информационные технологии и ИТ-образование" 6-9 декабря- Москва- 2008- Доступно по адресу: http://2008.it-
- edu.ru/docs/2/2%206%20P%20Bistrova%20Ino mistov.doc.