Генерация вариантов заданий для лабораторных работ по программированию

УДК 004.023

В. В. Лаптев, В. В. Толасова

ГЕНЕРАЦИЯ ВАРИАНТОВ ЗАДАНИЙ ДЛЯ ЛАБОРАТОРНЫХ РАБОТ ПО ПРОГРАММИРОВАНИЮ

Введение

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

При разработке автоматизированной обучающей системы по программированию эта проблема стоит еще более остро. С нашей точки зрения, в составе обучающей системы должна быть реализована тренажерная подсистема [1], которая и обеспечивает формирование навыков написания программ. Поэтому в составе базы знаний системы должны содержаться задания для написания программ по разным темам, обычно изучаемым при начальном обучении программированию. Хорошим примером такого набора заданий является книга Т. А. Павловской [2] или сборник заданий одного из авторов данной статьи [3].

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

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

Предлагаемое решение

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

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

Рассмотрим первое предложение этого задания. Очевидными претендентами в параметры являются значения 100, -50 и +50. Можно обобщить эти значения до параметров К, хн, хк. Тогда первое предложение задания будет выглядеть так:

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

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

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

1) осуществить ввод с клавиатуры;

2) сгенерировать случайное число;

3) осуществить ввод из текстового файла;

4) задать в качестве параметра командной строки.

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

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

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

N = ш1 х ш2 х ... х шп.

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

1) р1 : тип первого файла; ш1 = 2;

2) р2 : способ задания имени файла; ш2 = 4;

3) р3 : способ ввода К; К > 0; ш3 = 4;

4) р4 : способ ввода хн, хк; хн < хк; ш4 = 4;

5) р5 : тип случайных чисел; ш5 = 2;

6) р6 : тип второго файла; ш6 = 2;

7) р7 : способ задания имени файла; ш7 = 5;

8) р8: способ обработки значений; ш8 = 20.

Количество вариантов обработки значений соответствует количеству вариантов заданий в сборнике [3].

Параметр р7 имеет большее количество вариантов, чем аналогичный параметр р2, т. к. имя второго файла можно формировать еще одним способом: модифицировать имя первого файла. Кроме того, можно определить дополнительный параметр, зависящий от типов файлов: если оба файла двоичные, то можно обрабатывать два файла, а можно - единственный, который является

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

метр: р9 : количество файлов; рі = р6 = двоичный; ш9 = 2.

Таким образом, имеем (без учета параметра р9):

N = 2 х 4 х 4 х 4 х 2 х 2 х 5 х 20 = 23 х 43 х 100 = 25 600.

С учетом параметра р9 к этому числу добавляется следующее количество вариантов:

N9 = р2 х р3 х р4 х р5 х р7 х р8 = 4 х 4 х 4 х 2 х 5 х 20 = 3 200.

Это - теоретический максимум. При условиях m3 = 4 и m4 = 3 (параметр р4 обязательно задается способом, не совпадающим со способом задания параметра р3), m2 = 4 и m7 = 4 (параметр р7 обязательно задается способом, не совпадающим со способом задания параметра р2) имеем N = 15 360. Но даже если из-за зависимости параметров нам придется ограничиться только 100 вариантами - этого с лихвой хватает, чтобы задать каждому студенту индивидуальный вариант. Очевидно, что при индивидуальном обучении студент, выполнивший хотя бы половину подобных заданий, приобретет устойчивый навык написания подобных программ.

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

Вычислить и вывести на экран в виде таблицы K значений функции y = F(x) на отрезке [хн, хк]. Значения K, хн, хк ввести с клавиатуры.

В данном задании, помимо типичных параметров, параметром является функция У = F(x). Параметр-функция y = F(x) может быть задан таким же способом, как и параметр р8 в предыдущем задании. Однако заметим, что фактически F(x) - арифметическое выражение, в котором операндами являются числовые константы, символы-переменные и элементарные функции. Генерация конкретного арифметического выражения из подобных операндов осуществляется по контекстно-свободной грамматике арифметических выражений, где терминалами являются перечисленные выше операнды. Такой подход фактически снимает ограничение на количество вариантов данного вида задания. В самом общем виде такая грамматика может выглядеть следующим образом:

E -> T{+T|-T}

t -> f{*f|/f}

F -> S{^S}

S -> Name I Number|Function

Function -> sin|cos|_|exp|log Number -> integer|real

В данной грамматике нетерминал Name задает возможные имена переменных в арифметическом выражении, а нетерминал Function - допустимые имена функций. Нетерминал Number задает возможные типы операндов-констант в арифметическом выражении. Хотя в грамматике не определены нетерминалы integer и real, программа при генерации операнда-числа может генерировать случайное число соответствующего типа. Кроме того, очевидно, что при генерации F(x) можно задавать некоторые дополнительные условия генерации, например ограничить количество операндов арифметического выражения.

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

<body - начало тела>

Вычислить и вывести <p1> в виде таблицы <p2> значений функции y = <p5> на отрезке [<р3>]. Значение <p2> задать: <p4>, границы отрезка [<p3>] задать: <p4>.

</body - конец тела>

<param - параметры>

<p1 - начало описания параметра>

<type = text - тип параметра>

<select - начало выбора> <v = на экран> <v = в текстовый файл> </select - конец выбора> </p1- конец описания параметра >

<p2 - начало описания параметра>

<type = numer, integer - тип параметра>

<condition - условие> <v = random> <v > 20> </condition - конец условия>

</p2- конец описания параметра >

<p3 - начало описания параметра>

<type = numer, real - тип параметра>

<condition - условие> <v1 = random> <v2 = random> <v1 < v2>

</condition - конец условия>

</p3- конец описания параметра >

<p4 - начало описания параметра>

<type = text - тип параметра>

<select - начало выбора>

<v = ввод с клавиатуры > <v = ввод из текстового файла>

<v = генерировать случайное число> <v = параметр командной строки>

</select - конец выбора>

</p4- конец описания параметра >

<p5 - начало описания параметра>

<type = expression - тип параметра>

<condition - условие <v = generate, n < 20> </condition - конец условия>

</p5- конец описания параметра >

</param - конец параметров>

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

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

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

Заключение

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

СПИСОК ЛИТЕРАТУРЫ

1. Лаптев В. В., Толасова В. В. Предпроектный анализ архитектуры интеллектуальной обучающей среды по программированию // Информационные технологии и математическое моделирование (ИТММ-2008): Материалы VII Всерос. науч.-практ. конф. с междунар. участием (14-15 ноября 2008 г.). -Томск: Изд-во Том. ун-та, 2008. - Ч. 1. - C. 76-80.

2. Павловская Т. А. С/С++. Программирование на языке высокого уровня. - СПб.: Питер, 2004. - 461 с.

3. Лаптев В. В., Морозов А. В., Бокова А. В. C++. Объектно-ориентированное программирование. Задачи и упражнения. - СПб.: Питер, 2007. - 288 с.

4. Sosnovsky S., Shcherbinina O., Brusilovsky P. Web-based Parameterized Question as a Tool for Learning, in Allison Rossett (ed): Proceedings of E-Learn 2003, Phoenix, Arizona USA, November 7-11, 2003. -P. 2151-2154.

Статья поступила в редакцию 7.12.2009

TASK VARIANTS GENERATION FOR LABORATORY WORKS ON PROGRAMMING

V. V. Laptev, V. V. Tolasova

The article describes the problem of one-type task variants creation for trainings programming. It is proposed to generate task variants according to the principle of the morphological synthesis. Every task is represented as a parameterized template. The automated training system selects or generates values of parameters, substitutes them in a template, and creates a special task variant. The particularized description template language is offered.

Key words: task variant, description template, generation of variant, description template language.