An extended assessment algorithm for multivariate task presentation model.pdf Решение проблемы автоматизированного контроля знаний для многовариантных заданий по программированию можно разделить на два этапа: создание модели представления заданий и разработка алгоритма контроля. Модель представления задания приведена в [1]. Эта модель описывает формальное представление множества правильных ответов с помощью компонентов, элементов и шаблонов. В проверке формализованных ответов существует подход, основанный на копировании простейших контролирующих действий человека, т.е. в процессе контроля ответ обучающегося сравнивается с некоторым эталоном (правильным ответом, образцом) [2]. Задачи сопоставления с образцом встречаются в различных областях информатики. В частности, они используются в компиляторах [3], системах верификации [4], поисковых системах [5] и анализе естественных языков [6]. Одним из способов задания образцов служат регулярные выражения. Они применяются, например, в текстовых редакторах [7]. Авторы [8] использовали регулярные выражения для анализа баз данных электронных медицинских библиотек. Характерной чертой заданий по программированию является существование множества правильных ответов. Для формализации в [1] предложено группировать правильные ответы по степени сходства. Средствами группировки в модели являются элементы, которые подобны регулярным выражениям, но в силу особенностей предметной области имеют свою специфику. В модели определены три типа элементов: «Один компонент», «Один из компонентов» и «Перестановка компонентов». Последовательность элементов (шаблон) задается на формальном языке. В результате правильный ответ на задание представлен множеством шаблонов. Поэтому алгоритм контроля должен обеспечивать сопоставление с множеством образцов. В модели вводится понятие эксперта. Экспертом назван автомат, оценивающий соответствие варианта решения (входной последовательности) одному шаблону. Следовательно, для одного задания ответ обучающегося оценивает множество экспертов. В данной работе понятие эксперта модифицировано и представлен расширенный алгоритм оценки соответствия, проводящий развернутый анализ ответа обучающегося с предоставлением максимально детализированной информации для преподавателя. 1. Модель эксперта Ответ обучающегося эксперт получает в виде последовательности номеров компонентов, которые являются натуральными числами. Для создания эксперта необходимо задать шаблон; множество 101 И.А. Жуков, Ю.Л. Костюк всех рубежных элементов из шаблона и количество считываемых компонентов п, по умолчанию равное 2. В процессе оценки вспомогательными средствами для эксперта служат считыватель и анализатор. Считыватель на основе информации о текущем и следующем элементе шаблона читает подпоследовательность из ответа по следующим правилам: - если текущий элемент не является «перестановкой компонентов» или не помечен как рубежный, считать п компонентов; - для рубежного элемента считать только один компонент; - для элемента «перестановка компонентов» считыватель просматривает все значения до ближайшего из компонентов следующего рубежного элемента, если ни один из компонентов следующего рубежного элемента не представлен, считывается пустая последовательность. Затем анализатор оценивает соотношение текущего элемента шаблона и прочитанной подпоследовательности. Для оценки соответствия подпоследовательности и элементов «Один компонент» и «Один из компонентов» достаточно регулярных выражений. Существует две спецификации регулярных выражений: POSIX [9] и Perl [10]. Задача оценки для приведенных двух типов элементов решается средствами любой из этих спецификаций. Элемент «Перестановка компонентов» не может быть представлен средствами спецификаций регулярных выражений. Существуют расширения, позволяющие определять перестановки, например описанное в [11]. Для нашей задачи достаточно определить, какие из компонентов перестановки присутствуют в подпоследовательности, при этом не уточняя, какая именно перестановка представлена. Для определения соответствия необходимы индекс элемента в подпоследовательности компонентов (далее - индекс элемента) и мощность пересечения множеств всех компонентов элемента и компонентов подпоследовательности (далее - мощность). Для элементов типа «Один компонент» или «Один из компонентов» мощность всегда равна 0. Мощность указывает количество компонентов перестановки в подпоследовательности. Индекс принимает целые значения от -1 до п - 1. Значение индекса равно -1, если элемент имеет тип «Перестановка компонентов» или в считанной подпоследовательности не найдено ни одного компонента данного элемента. Индекс равен 0, если подпоследовательность начинается с одного из компонентов текущего элемента. Индекс больше 0 означает, что какой-либо из компонентов элемента присутствует в подпоследовательности, но не первым. В таком случае индекс показывает позицию первого встретившегося компонента данного элемента. Оценкой соотношения элемента и подпоследовательности является одно из трех значений: 0 -подпоследовательность полностью удовлетворяет элементу, 1 - подпоследовательность частично удовлетворяет элементу, 2 - подпоследовательность не удовлетворяет элементу. Алгоритм анализа представлен деревом принятия решения, изображенным на рис. 1. В процессе анализа также вычисляется коэффициент ошибки, выявляются отсутствующие и «лишние» компоненты. Коэффициент ошибки определяется следующим образом: - если подпоследовательность полностью удовлетворяет элементу, то коэффициент равен 0; - если подпоследовательность не удовлетворяет, то коэффициент равен 1; - для частично удовлетворяющих: если элемент имеет тип «Перестановка компонентов», то коэффициент ошибки равен разности длины элемента и мощности, делннной на длину элемента; для остальных типов элементов - индекс элемента, деленный на длину подпоследовательности. Отсутствующими компонентами будем считать компоненты, которые входят в элемент, но не входят в подпоследовательность. Для элемента типа «Один из компонентов», если любой из компонентов присутствует в подпоследовательности, то отсутствующие компоненты не вычисляются. «Лишними» компонентами будем считать компоненты, которые входят в подпоследовательность, но не входят в элемент. В результате анализа получается запись, имеющая следующую структуру: элемент, считанная из ответа подпоследовательность, индекс элемента, мощность, оценка соответствия, коэффициент ошибки, отсутствующие компоненты, «лишние» компоненты. 102 Расширенный алгоритм контроля знаний для модели представления многовариантных заданий По результатам анализа считыватель выставляет позицию начала следующего считывания согласно алгоритму: - если индекс элемента и мощность меньше 1, сместить позицию в ответе обучающегося вправо на 1; - если элемент не помечен как опциональный, сместить позицию в ответе обучающегося вправо на длину считанной подпоследовательности; - если элемент помечен как опциональный, позиция не меняется. Индекс элемента равен -1? Нет Мощность больше О? Индекс элемента больше О? Мощность меньше длины элемента? Іодпоследовател ьность' не удовлетворяет элементу у /Подпоследовател ьность\\ полностью удовлетворяет V элементу J Подпоследовательность частично удовлетворяет У элементу / /Подпоследо вател ь ность\\ полностью удовлетворяет) у элементу J Подпоследо ватель ность частично удовлетворяет ^ элементу , Рис. 1. Дерево принятия решений для оценки соответствия элемента считанной последовательности из ответа обучающегося Fig. 1. Analysis algorithm represented by decision tree В ходе работы эксперт сохраняет результаты анализа. В итоге записи о процессе работы эксперта состоят из трех частей: записей о результатах анализа, списка «лишних» компонентов и причины завершения анализа. Записи о результатах анализа делаются последовательно для каждого элемента шаблона, т.е. одна запись соответствует одному элементу. Список «лишних» компонентов относится к компонентам, которые остались несчитанными после завершения работы с шаблоном. Причина завершения классификации может иметь одно из трех значений: закончился шаблон, закончился ответ, закончился и шаблон, и ответ. Результатом работы является мнение эксперта, которое содержит оценку в виде обыкновенной дроби, таблицу ошибок и записи о процессе работы эксперта. Записи в таблице ошибок имеют вид: позиция элемента в шаблоне, элемент, характеристика ошибки, отсутствующие компоненты, «лишние» компоненты. Характеристика ошибки может иметь одно из четырех значений: 0 - элемент отсутствует, 1 - элемент частично присутствует (часть компонентов отсутствует), 2 - элемент присутствует с лишними компонентами, 3 - элемент присутствует, но часть компонентов отсутствует, и имеются лишние компоненты. 2. Алгоритм работы эксперта На рис. 2 приведена диаграмма деятельности, описывающая алгоритм работы эксперта. Остановимся на некоторых шагах алгоритма. В начале работы алгоритма вычисляется пересечение множеств всех компонентов рубежных элементов и всех компонентов ответа. Если множество 103 И. А. Жуков, Ю.Л. Костюк всех рубежных элементов непустое, а пересечение множеств - пустое, то эксперт оценит соответствие на 0, в таблицу ошибок заносятся все рубежные элементы, все ошибки буду иметь характеристику «элемент отсутствует». Вычислить мощность пересечения множеств всех компонентов рубежных элементов и всех компонентов ответа [Нет] Больше 0 Проанализировать соотношение каждого рубежного элемента с пустой последовательностью Получить текущий и следующий элемент Построить таблицу ошибок на основе записи о процессе работы эксперта Текущий элемент 'ществуету Записать информацию о оставшихся компонентах ответа и элементах Выставить оценку 0 Считать подпоследовательность из ответа Построить таблицу ошибок на основе записи о процессе работы эксперта Вычислить оценку Ответ считан полностью? Проанализировать соотношение считанной последовательности и текущего элемента Записать результаты анализа Сдвинуть позицию в ответе Перейти к следующему элементу Рис. 2. Диаграмма деятельности для алгоритма оценки Fig. 2. Activity diagram for assessment algorithm 104 Расширенный алгоритм контроля знаний для модели представления многовариантных заданий Если причина завершения анализа - «закончился ответ», проанализировать соотношение каждого оставшегося элемента с пустой последовательностью. То есть в записи о процессе работы эксперта это будет отражено как элемент, не удовлетворяющий подпоследовательности, при этом отсутствуют все компоненты элемента и не присутствует «лишних». Таблица ошибок строится по следующему алгоритму: - если соответствие элемента и подпоследовательности оценено как «подпоследовательность не удовлетворяет элементу», соответствующий элемент характеризовать как «элемент отсутствует»; - если соответствие элемента и подпоследовательности оценено как «подпоследовательность частично удовлетворяет элементу» и количество отсутствующих компонентов не равно 0, характеризовать как «элемент частично присутствует»; - если количество «лишних» компонентов не равно 0, характеризовать как «присутствует с лишними компонентами»; - если и количество отсутствующих компонентов, и количество «лишних» компонентов не равно 0, характеризовать как «присутствует, но часть компонентов отсутствует, и имеются лишние компоненты». Список отсутствующих компонентов и список «лишних» компонентов скопировать. Оценка M вычисляется по формуле П М = 1 - Z w&pif,) - wdpextra(a extra ^ aee ) , (1) i=1 где Wi - вес i-го элемента, в, - коэффициент ошибки i-го элемента, p(fi) - множитель штрафа для метки i-го элемента, Wd - вес элемента, по умолчанию равный единице, деленной на длину шаблона, Pextra - множитель штрафа для «лишних» компонентов, aextra - количество «лишних» компонентов, не привязанных к элементам, авв - количество «лишних»" компонентов в элементах. Если вычисленная оценка получилась меньше 0, оценка будет приравнена к 0. 3. Пример работы алгоритма Разберем работу эксперта на примере. Для примера возьмем один шаблон из задания, приведенного в [1]. Рассмотрим работу эксперта, который оценивает соответствие ответа шаблону {(1;4);5;6;3*;7|8;9}. Пусть ответ обучающегося будет «2;1;5;10;6;3;8;11». Все программы, соответствующие полностью правильным ответам: S:=0; S:=0; i:=0; i:=0; i:=0; i:=0; S:=0; S:=0; while i

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