При обучении программированию в курсе информатики наиболее сложным для учащихся оказывается самопроверка (отладка и тестирование собственных программ). Дальнейшая же проверка правильности выпол-нения учебных заданий преподавателем, в свою очередь, является наиболее трудоемкой частью процесса обучения и предполагает проработку методики будущего оценивания ожидаемых решений. Если при проверке решения теоретических задач основное внимание уделяется анализу хода решения и правильности полученногоответа, то при решении практических задач ситуация иная. Несмотря на важность работ в области доказательства правильности программ [1, 2], предлагаемые в них методы можно и нужно использовать в основном во время разработки алгоритма решения задачи. Завершением же этапа реализации (собственно программирования) является тестирование программы, то есть выявление особенностей представленного решения нанаборе специально подобранных тестов.

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

С другой стороны, никакая система тестирования не может быть самодостаточным инструментом для проверки решений задач в процессеобучения программированию. Так как, если программа уже успешно прошла все тестовые испытания, преподавателю имеет смысл просмотреть ее листинг в присутствии ученика, отметить недостатки (если таковые имеются) в эффективности программной реализации тех или иных элементов алгоритма и в стиле программирования. Если же в результате беседы выяснится, что решение было основано на имплицитном знании, то следует закрепить такое интуитивно верное решение в вербальной (эксплицитной, логической) форме [3]. Для этого необходимо в разбор заданий, проводимый для учащихся, включать и методику оценивания программ.Одним из вариантов развивающего обучения в дидактике признано проблемное обучение. Его целью, в отличие от традиционного обучения, является усвоение не только результатов научного познания и системы знаний,но и поиск самого пути. В результате формируется познавательная самостоятельность ученика и развиваются его творческие способности.

Таким образом, проблемное обучение — это оптимальное сочетание репродуктивной и творческой деятельности по передаче и усвоению системы научных понятий и приемов, способов логическогомышления. Это дидактический подход, учитывающий психологические закономерности мыслительной деятельности субъектов [4]. С внедрением компьютера в процесс обучения впервые появилась возможность, в несколькораз повысив активность учащихся, обеспечить цикличность функционирования традиционного контура обратной связи “преподаватель—ученик” в реальном масштабе времени.В результате намного проще стало реализовывать ведущие принципы развивающего обучения: индивидуализацию и дифференциацию. Кроме того, компьютер, позволяя ошибаться, разрешая ошибаться, создавая возможность ошибаться, дает возможность познавать через противоречия. А, как показано Ж.Пиаже [5], ошибочные теории учеников являются существенной частью процесса формирования мышления.

Постановка задачи с учетом ее дальнейшей автоматической проверки

Наиболее полно принципы тестирования промышленных программ были сформулированы в [6]. Однако они должны быть модифицированы и дополнены применительно к особенностям учебных программ. Если тестирование программы проводится интуитивно и без четкого плана испытаний, то этот процесс можно назвать искусством. Если же тестированию предшествует тщательный подбор данных для контрольных примеров, а само тестирование выполняется последовательно и аккуратно, то тестирование становится наукой. Тестовые испытания учебной программы направлены на то, чтобы проверить правильность работы программы во всех предполагаемых практических ситуациях, оговоренных в условии задачи, а также оценить ее эффективность. При этом программа учащегося, с точки зрения преподавателя, является “черным ящиком”. Проверку такой программы без непосредственного участия ученика можно провести лишь в том случае, когда задача поставлена четко и полностью. Особое внимание при этом следуетуделять описанию форматов входных и выходных данных, типам входных величин и диапазонам их допустимых значений. Полезным является включение тестовых примеров входных и выходных данных в условие задачи. Эта мера позволяет ученику проверить, правильно ли он понимает задачу. В последнее время неотъемлемой частью формулировки условия учебной или олимпиадной задачи по программированию является явное указание на максимальное допустимое время ее работы на любых данных, не противоречащих условию. Данное указание как раз и позволяет в дальнейшем оценить эффективность алгоритма, используемого при написании программы. Приведем пример неудачной и удачной формулировки условия учебной задачи с точки зренияее дальнейшего тестирования преподавателем.

Пример входных данных:

3

4  —1

2

Возможный файл OUTPUT.TXT для приведенного примера входных данных:

—1 2 4

Таким образом, постановка задачи (спецификация задания) должна обладать свойствами четкости и полноты.

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

Другой пример вырожденности —нарушение общности входных данных , требующее специальной их обработки. Так, если в учебной задаче требуется решить уравнение ax²+bx+c для любых дейcтвительных значений a, b и c, то при a=0 квадратное в общем случае уравнение становится линейным, что программа учащегося, несомненно, должна учитывать. Причем только в этом случае существенным становится равенство нулю значения параметра b.

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

a = 0, b = 0, c = 0;
a = 0, b = 0, c = 1;
a = 0, b = 1, c = 2 .

Если же в задаче входными параметрами являются координаты N точек на плоскости, а требуется, например, найти такую точку на той же плоскости, расстояние от которой до наиболее удаленной из N точек минимально, то очевидно, что при решении задачи случаиN = 1 и N = 2 следует рассматривать отдельно. Если программа учащегося обрабатывает подобные входные данные некорректно, то при автоматической проверке возможны следующие типы диагностики ошибок:

Runtime Error — ошибка выполнения программы (в основном врезультате деления на ноль) или Wrong Answer — неверный ответ (программа не учитывает, что при вырожденных входных данных алгоритм их обработкиможет иметь специфические отличия от основного алгоритма).

3. Следующая группа тестов должна проверять граничные случаи (входные и выходные данные принимают граничные значения). Основное назначение подобных тестов — обнаружить возможные программистские ошибки, которые могли быть сделаны учащимися при реализации в том числе и правильного алгоритма. Прежде всегов данном случае следует проверить, что при написании программы для переменных были выбраны подходящие типы данных. Так, если программа вычисляет сумму целых чисел, каждое из которых по модулю не превосходит32 767, то есть для представления таких чисел можноиспользовать двухбайтовый знаковый тип данных, то для вычисления результата такого типа уже явно недостаточно. Причем может даже оказаться, что получение точного результата возможно только с помощью так называемой “длинной арифметики” [7] — организации выполнения арифметических действий с помощью массивов,что существенно меняет сложность решения.

В задачах, при решении которых используются численные методы, к граничным можно отнести тестовые данные, для обработки которых требуется максимальная точность вычислений, в частности, большие или очень маленькие, но отличные от нуля значения для входных параметров.Часто критичным для программы является количество оперативной памяти, которое используется во время ее выполнения. Если все переменные располагаютсяв статической памяти, то наиболее распространенная ошибка при программировании — выход за границу массива данных во время выполнения программы, причем проявиться эта ошибка может зачастую лишь на входных данных максимального объема. Если же максимально допустимое количество данных по условию задачи таково, что программист должен использовать динамическую память, то обязательно должны присутствовать тесты, проверяющие программу на корректность работы с ними. Так, начинающий программист может неправильно выделять необходимую оперативную памятьво время работы программы и/или неаккуратно к ней обращаться. Также память в программе может использоваться неэффективно. В этом случае возможно подобрать тест, на котором программа учащегося работать не будет как раз в силу недостатка динамической памяти, хотя эталонная программа в подобных условиях функционирует нормально.При работе со строками программа учащегося часто не может обрабатывать корректные с точки зрения условия задачи строки текста, длина которых превышает 255 символов. Это связано с особенностями используемого языка программирования или применением массива символов фиксированной длины вместо одной-двух символьных переменных. Если по условию задачи требуется обработать файл, состоящий из заранее неизвестного количества чисел или строк, то для многих программ критичным оказывается наличие пробелов после последнего числа и пустых строкв конце файла. Иногда при тестировании подобная небрежность в программировании намеренно прощается,тогда при подготовке тестов приходится следить, чтобы признак конца файла располагался непосредственно за последним значащим символом входных данных, причем обязательно в той же самой строке.

4. В следующую группу можно объединить тесты, проверяющие правильность алгоритма решения задачи в целом. Они делятся на общие тесты и тесты специального вида. Последние должны проверить работоспособность программы в случае специальной организации входных данных. Например, входные данные могут быть отсортированы сначала в порядке возрастания, а затем в порядке убывания, хотя по условию определенный порядок над ними не предполагается, однако алгоритм решения может использовать сортировку входных величин. Или значения всех параметров можно сделать равными между собой. Помимо выявления специфики работы программ учащихся на таких тестах, они хороши тем, что зачастуюпозволяют проверяющему определить правильность выходных данных “вручную”. Это уменьшает объем работы по проверке компьютерных результатов.Общие тесты должны проверить все ветви логической схемы алгоритма, такая проверка называется испытанием ветвей [6].

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

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

6. Если прогон программы на предыдущих группах тестов показал ее правильность в целом, то тогда следует приступить к проверке эффективности используемых алгоритмов. Данное качество является наиболее уязвимым как в учебных программах, так и в решениях олимпиадных задач по информатике. Упрощая для себя решение задачи или его реализацию, учащиеся неоправданно увеличивают вычислительную сложность алгоритма, зачастую делая его непригодным для работы над большими, однако допустимыми по условию входными данными. Осознать данный факт самостоятельно они при этом не всегда могут. Соответственно возрастает значимость подобного рода тестирования. Если в результате выбора способа решения задачи алгоритм полиномиальной сложности был заменен на экспоненциальный, то проверить это несложно. Например, при вычислительной сложности N!, где N — количество входных данных, программа не сможет завершить свою работу за одну минуту даже при N < 16 (точная верхняя граница работоспособности подобного алгоритма зависит от быстродействия компьютера, но при увеличении скорости процессора в 100 раз не может быть повышена более чем на 2). Наиболее часто подобный ошибочный выбор алгоритма происходит, когда задачу дискретной математики решают методом полного перебора вариантов вместо, например, динамического программирования, вычислительная сложность которого обычно не превышает N ³. В этом случае с помощью уже средних по объему тестовых входных данных можно определить, что работа программы не укладывается в отведенное в условии для ее работы время. При автоматической проверке это соответствует диагностике Time limit exceeded. Та же самая диагностика в предыдущих группах тестов скорее всего обозначает, что программа “зацикливается”.

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

7. Последнюю группу составляют так называемые случайные тесты. Такие тесты должны отражать реальные в полном объеме входные данные. Генерация входных данных для такой группы тестов (часто достаточно одного-двух тестов) не представляет труда. Однако проверка правильности работы программы учащегося сложна именно на таких тестах. Объясняется это тем, что в данном случае трудно проверить “вручную” результаты работы программы. Зачастую для этого необходимо написать специальную программу, по сложности не уступающую решению исходной задачи. Особенно это характерно для “большого случайного теста”, которым обычно завершается тестирование программы.

Тестовый драйвер

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

Наиболее известный в нашей стране тестовый драйвер разработан в Санкт-Петербургском государственном институте точной механики и оптики А.Сухановым и модифицирован Р.Елизаровым. Именно он используется при проверке задач большинства студенческих и школьных командных соревнований по программированию и школьных олимпиад по информатике. Данный драйвер написан для операционной системы DOS и требует доработки в случае его использования для проверки учебных программ. На факультете ВМиК МГУ им. М.В. Ломоносова А.Черновым для московских студенческих соревнований по программированию была создана система, успешно функционирующая в операционных системах UNIX и Windows NT. Данная программа создает исчерпывающий протокол тестирования, что позволяет использовать ее и при проверке учебных задач. В СУНЦ МГУ специально для испытания учебных задач при активном участии студента мехмата МГУ И.Никокошева был создан свой тестовый драйвер. Любая из упомянутых программ может работать и сама по себе для проверки решения одним учащимся одной учебной задачи. Рассмотрим на примере последнего из упомянутых тестовых драйверов условия успешного их применения.

Для проверки той или иной программы с помощью системы тестов прежде всего необходимо создать набор тестовых входных данных согласно принципам, сформулированным выше, и записать их в файлы с идентичными именами. Обычно последние 1—2 символа в имени файла обозначают его порядковый числовой номер в системе тестов. В правильно составленном наборе тестов их сложность с увеличением номеров должна возрастать. Затем, для того чтобы “научить” тестовый драйвер проверять решение какой-либо задачи, необходимо создать определенный конфигурационный файл. Минимальная информация, которую должен содержать такой файл, следующая:

1) название задачи;

3) количество тестов (при отсутствии данной информации осуществляется проверка программы на всех тестах, находящихся в текущем каталоге);

4) шаблон для имен тестовых входных файлов;

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

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

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

Компаратор numbers проверяет, что в обоих сравниваемых файлах содержится один и тот же набор чисел, причем в том же самом порядке. Вид разделителей между числами (пробелы и символы перевода строки) и их количество, в том числе и после последнего числа, при этом несущественны. Если числа не являются целыми, то сравнение производится с точностью, определяемой количеством цифр после точки в каждом из чисел правильного ответа. При сравнении текстовых файлов используются два компаратора: exactly — сравнивающий два файла на точное совпадение и tokens — игнорирующий при сравнении пробельные символы в конце каждой строки и символы перевода строки в конце файла. Кроме того, программа sets позволяет сопоставлять между собой множества чисел, расположенных в анализируемых файлах. То есть здесь не учитывается порядок расположения чисел в ответе.

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

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

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

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

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

Система “клиент — сервер” для организации компьютерного задачника 

Современная визуальная технология конструирования программ, а также создание мощных процессоров баз данных, например BDE [8], сделали возможным написание программы оболочки для компьютерного задачника без привлечения коллективов профессиональных программистов. В подобной программе, реализованной в сетевой архитектуре “клиент — сервер”, обработку поступающих запросов клиентов и передачу им результата на низком уровне берет на себя стандартный процессор баз данных, который занимается установкой соединения между СУБД и приложением. Запросами со стороны клиента(ученика) в нашем случае являются заявка на получение условия той или иной назначенной учащемуся задачи и посылка на проверку файла с текстом ее решения на том или ином языке программирования

В СУНЦ МГУ под руководством автора был создан сетевой программный комплекс для проверки учебных и олимпиадных задач в автоматическом режиме и тестирования знаний учащихся по теоретическим основам информатики. Непосредственное участие в его реализации принимал студент мехмата МГУ Ю.Спорынин. Работа с сетью как в программе сервера, так и в программах клиентов осуществляется через протокол TCP/IP. Это позволяет использовать данную систему не только в локальной сети, но и в сети Интернет.

Система успешно применяется в учебном процессе с1999/2000 уч. года. На нее возложены функции автоматической проверки заданий практикумов по программированию в СУНЦ МГУ, проведение олимпиад в режиме on-line (по принципам студенческих командных соревнований по программированию) и тестирование знаний учащихся по любым предметам. Система постоянно пополняется. Однако набор задач и тестов по информатике, проверка которых уже автоматизирована в настоящее время, позволяет считать ее компьютерным задачником, пригодным для широкого использования в преподавании информатики.

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

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

1.        Грис Д. Наука программирования. M.: Мир, 1984.

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

3.        Пинаев В.Н. Олимпиады по информатике. Информатика, № 22/2001.

4.        Окулов С.М., Пестов А.А., Пестов О.А. Информатика в задачах. Киров: Вятский государственный педагогический уни-верситет, 1998.

5.        Пейперт С. Переворот в сознании: дети, компьютеры и плодотворные идеи. М.: Педагогика, 1989 .

6.        Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. M.: Мир, 1985.

7.        Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.

8.        Дарахвелидзе П.Г., Марков Е.П. DELPHI 4. С.-Петербург:БХВ, 1998.