Use tree and/or for generation of the questions and tasks.pdf Генераторы вопросов и тестовых заданий становятсяважным элементом системы контроля знаний в вузе. Они ис-пользуются при выдаче индивидуальных заданий студентам,проведении тестовых экзаменов и контрольных работ, созда-нии различных тренажеров, компьютерных учебных про-грамм и мультимедийных учебников[1−3].Центральным узлом генератора является база знаний, кото-рая обеспечивает формализованное представление знаний неко-торой предметной области. Структура этой базы определяетосновные характеристики генератора: вариантность, сложность,надежность, перечисляемость. Вариантность определяет общеечисло вопросов и тестовых заданий, которое может быть полу-чено данным генератором. Надежность определяет корректностьгенерируемых заданий, поэтому необходимо иметь генератор,который генерирует только корректные задания. Перечисляе-мость определяет возможность однозначного соответствия меж-ду некоторым номером и конкретным вопросом, полученнымгенератором.При создании генераторов могут использоваться различ-ные модели представления знаний [4]. Одной из возможныхмоделей является дерево И/ИЛИ, основные понятия и пере-числительные свойства которых даны в [5].Ниже предлагаются оригинальные модели и алгоритмыгенераторов вопросов и тестовых заданий, основанные наиспользовании деревьев И/ИЛИ.ГЕНЕРАЦИЯ ТЕКСТА ТЕСТОВОГО ЗАДАНИЯДерево И-ИЛИ можно использовать для многовари-антного представления тестового задания. Для этоготекст задания разбивается на фрагменты. Обычнофрагменты разбиваются на классы: постоянные {T} ипеременные {V}. Для переменных фрагментов записы-ваются множества реализаций, каждый из которыхпредставляет собой конкретный текст. Затем каждыйиз выделенных фрагментов реализаций анализируетсяи, если есть возможность, разбивается на переменные ипостоянные подфрагменты.Рассмотрим использование данного метода на конкрет-ном примере. Пусть дано конкретное тестовое задание:«Дана следующая функция, написанная на языкепрограммирования Си:int Sum(int v[], int n){int sum=0;for(int i=0; i v1*t1 => s-s2;(5) s2 => v2*t2 => s-s1;(6) v1 => s1/t1 => v2-k;(7) v2 => s2/t2 => v1+k;(8) t1 => s1/v1;(9) t2 => s2/v2.Дано s=10, t1=t2=t=2, k=1.Найти v1.Первым шагом поиска решения является построе-ние дерева решений. Дерево решений для нашего при-мера показано на рис. 3. Построение начинается с за-писи искомой переменной v1 (см. описание алгоритмапостроения дерева И-ИЛИ). Далее записываются фор-мулы, с помощью которых определяется искомая пе-ременная (это формулы s1/t1 и v2-k). Использованиевторой формулы приводит к решению через нахожде-ние переменной v2. Для краткости этот вариант рас-сматриваться не будет. Рассмотрим ветвь для формулыs1/t1. Для данного узла будут записаны два сына − пе-ременная s1 и переменная t1. Переменная t1 известнапо условию задачи. Она становится листом. Далее рас-сматривается переменная s1. Для нее в базе знанийимеется две формулы s−s2 и v1*t1. Использование вто-рой формулы не приведет к решению, т.к. происходитсокращение переменных. Для формулы s−s2 необходи-мо найти s2, т.к. переменная s известна. Для перемен-ной s2 в базе знаний имеется две формулы: v2*t2 иs−s1. Использование второй формулы приводит к ре-курсии, т.к. ранее подстановка для переменной s1 ужеиспользовалась. Рассмотрим формулу v2*t2. Здесь не-известная переменная v2. Для нее производим подста-новки. Это формулы s2/t2 и v1+k. Первая и втораяформула приводит к рекурсии. Таким образом, процесспостроения дерева заканчивается.решение для V2V1 KS 2/t2V t 1 1SS1 t1S1/t1V1V2 t2S2V t 2 2известнаизвестнаизвестнарекурсияРекурсиярекурсия- и-узел- или-узелРис. 3. Дерево решенийПосле построения дерева решений производится егоанализ. Анализ включает: подсчет количества вариантов,анализ каждого варианта с использованием алгоритмовэквивалентных преобразований. Всего вариантов реше-ний, без учета ветви v2+k, будет 4 (см. рис. 2). Решениебудет получено при использовании варианта с номером 1(см. алгоритм нумерации И/ИЛИ дерева). Этот вариантпоказан на рис. 4. В этом дереве записаны подстановкиформул, приводящие к построению уравнения.v1 KV2 t2V t 2 2S S2S1 t1S1/t1V1Рис. 4. Вариант решенияРассмотрим эти подстановки:(1) v1; v1 => s1/t1;(2) s1/t1; s1 => s−s2;(3) (s−s2)/t1; s2 => v2*t2;(4) (s−(v2*t2))/t1; v2 => v1+k;(5) (s−((v1+k)*t2))/t1.ГЕНЕРАЦИЯ МЕНЮ ВОПРОСОВКак известно, используя ограничения рекурсии, кон-текстно-свободные грамматики можно представить де-ревьями И/ИЛИ [3].1. Записывается два дерева И/ИЛИ: первое описы-вает грамматику правильных, второе - грамматику не-правильных выражений.2. Вычисляем количество правильных и неправиль-ных выражений, получаемых из соответствующих де-ревьев m и n.3. Вопрос формулируется следующим образом: «Сре-ди перечисленных выражений укажите верные (или не-верные).4. Используя метод нумерации вариантов в деревеИ/ИЛИ и алгоритм генерации меню-вопросов, генери-руем меню вопрос[3].4. Общее число вопросов будет вычисляться поформуле, lnkmv=C ⋅Cгде k - количество правильных вариантов ответа в во-просе; l - количество неправильных вариантов ответа.ПОСТРОЕНИЕ МЕНЮ-ВОПРОСОВНА ОСНОВЕ КЛАССИФИКАЦИЙКлассификации являются одним из важных элемен-тов знаний преподаваемого курса или дисциплины. Обы-чно классификации представляются в виде некоторойтаблицы или иерархии. Ниже предлагается метод гене-рации меню вопросов на основе классификации, пред-ставленной в виде И/ИЛИ дерева (рис. 5).Этот метод заключается в следующем:1. По данной классификации признаков строитсяИ/ИЛИ дерево.2. Определяется количество вариантов в И/ИЛИ де-реве.3. Строится таблица соответствий между вариантомИ/ИЛИ дерева и конкретным классифицируемым объ-ектом или явлением. Эта таблица содержит название по-нятия, объекта или явления и соответствующие номеравариантов.4. Выбирается одна строчка таблицы и строится ва-риант, соответствующий номеру данного названия(понятия, объекта или явления).5. Случайно выбираются еще несколько строк таб-лицы.6. Вопрос формулируется так: «Даны следующие при-знаки: . Укажите пра-вильное название (понятия, объекта или явления)».Перечисляются случайно перемешанные названия, по-лученные на шаге 4 и 5. Правильным ответом будет на-звание, полученное на шаге 4.Рассмотрим данный метод на конкретном примере.Пусть дано дерево И-ИЛИ, классифицирующее легко-вые автомобили (это дерево является условным, поско-льку реальное дерево содержит тысячи узлов, а табли-ца содержит десятки тысяч строк).Используя алгоритм подсчета вариантов, получим:v = (9) × (3) × (1 + (1 + 1) +1) × 3 × 2 = 648.Вариант дерева с номером 0 будет:Автомобиль:кузов: хэтчбек,колеса: 19 дюймов,двигатель: электрический,привод: задний,коробка: механика.Предположим, что этот вариант соответствует авто-мобилю марки «Мерседес» модели 123. Аналогично ста-вим соответствие с другим вариантом классификацион-ного дерева. Затем строим табл. 2 соответствий:Т а б л и ц а 2Название модели автомобиля Номера вариантов«Мерседес-123» 0«Ауди-530» 1«Тойота-127» 2«Запорожец» 3«Москвич-413» 4Рис. 4. Дерево И-ИЛИ для представления классификацииИспользуя описанный метод, можно получить следу-ющий вопрос: «Даны следующие узлы (характеристики)автомобиля: кузов: хэтчбек; колеса: 19 дюймов; двига-тель: электрический; привод: задний; коробка: механика.Укажите марку: 1) «Ауди-530»; 2) «Тойота-127»; 3)«Мерседес-123»; 4) «Москвич-413».Правильный ответ здесь третий: !Мерседес-123».Подсчет числа вопросов можно произвести следую-щим образом:3 ,−1 = ⋅ Nv nCnгде Nv − общее число вопросов; n − число строк табли-цы; 3Cn−1 − число сочетание из (n − 1) марок автомоби-лей по 3 для формирования списка неверных ответов.ЗАКЛЮЧЕНИЕПрактическая реализация генераторов и использо-вание их в учебном процессе, как в дистанционных тех-нологиях обучения, так и в очном обучении, показыва-ет их эффективность.Применение деревьев И/ИЛИ для представления мо-дели знаний предметной области позволяет строить раз-нообразные алгоритмы генерации вопросов и тестовыхзаданий. Кроме этого, они дают возможность строитьалгоритмы семантической проверки на наличие реше-ний при генерации тестовых заданий.Предложенные модели и алгоритмы использовалисьпри разработке генераторов контрольных работ и экза-менов, которые успешно эксплуатируются в Томскоммежвузовском центре дистанционного образования.

Скачать электронную версию публикации