Model of representation of multivariate tasks for automated control of programming knowledge.pdf Вопросы автоматизации контроля знаний актуальны на протяжении многих лет. В частности, технологии автоматизированного контроля применяются для дисциплин укрупненных групп специальностей и направлений (УГСН) 02.00.00 «Компьютерные и информационные науки» и 09.00.00 «Информатика и вычислительная техника». Большинство профессиональных дисциплин данных УГСН связанно с программированием. Многие авторы ищут новые подходы для совершенствования традиционного метода обучения программированию. Автор [1] предлагает применять методики, использующие интерактивные технологии и стимулирующие методы. Проведен анализ успеваемости двух групп: экспериментальной, для которой лекционные занятия строились на основе специально созданного программного комплекса, и контрольной, в которой применялась традиционная методика преподавания. Автор отмечает, что уровень знаний в экспериментальной группе оказался выше, чем в контрольной. Сделан вывод, что при обучении программированию более эффективными будут отход от традиционных методов преподавания и внедрение в обучение новых методик, использующих интерактивные технологии и стимулирующие методы. Важную роль в учебном процессе играет контроль знаний. Основным методом автоматизированного контроля знаний является альтернативно-выборочный метод (тесты). Для изучения основ программирования такой метод применим. Например, в [2] описан разработанный авторами алгоритм генерации тестов для проверки теоретических знаний и навыков владения студентами языком программирования в рамках дисциплины «Основы программирования на языке Delphi 7.0». Отметим, что для проверки навыков применяются тесты в формате: «Что будет являтся результатом работы приведенного фрагмента программного кода?» Помимо тестов требуется более глубокий контроль, при котором обучающийся мог бы не просто выбирать один или несколько ответов из предложенных. Многие стараются решить этот вопрос, разрабатывая новые методики и техники контроля знаний или поддержки процесса обучения. Например, авторы [3] разрабатывают систему поддержки обучения тестированию программного обеспечения. Для этого они создали язык описания диаграмм, который основан на высказываниях, причем 110 Модель представления многовариантных заданий для автоматизированного контроля знаний каждое высказывание относится к одному из двух типов: «функция» или «ограничение». Язык может транслироваться в более «низкоуровневые» языки описания графов. Авторы [4] предлагают систему обучения программированию, в которой учащиеся составляют интеллект-карту для ответа на задание. Обсуждается идея игры по теме «Программирование», основанной на принципе интеллекткарты. Обучающемуся предлагается ряд задач, и ему следует выбрать несколько операторов, необходимых для решения задачи, их порядок, а затем выбрать типы данных для переменных. Особенности обучения будущих программистов заключаются в том, что необходимо огромное количество практики, а именно написание тысяч строк программного кода. В образовательных программах предусмотрены лабораторные работы, в рамках которых обучающиеся разрабатывают программы для решения поставленных учебных задач. Преподаватель оценивает знания и полученные навыки обучающихся в ходе личной беседы или чтения отчетов. Одним из способов автоматизации этого процесса является автоматическое тестирование программ. В таком случае применяется поведенческое тестирование, где в качестве спецификации, в которой описаны входные данные и ожидаемый результат, используются условия задачи. Поведенческое тестирование также называют тестированием черного ящика [5], или тестированием методом черного ящика. Такой подход, например, используют авторы [6], которые разработали систему поддержки процесса обучения программированию, предлагающую задания в форме тестов для проверки теоретических знаний и тестирование программ для проверки умений и навыков. Для тестирования программ авторы используют набор тестов, включающий в себя входные и выходные данные, а также максимально допустимое время выполнения программы. Является ли тестирование черного ящика решением проблемы автоматизации контроля практических навыков программирования? В [7, 8] рассматриваются различные подходы к автоматизации контроля знаний при обучении программированию. В работе [7] для контроля знаний по программированию, помимо тестирования теоретических знаний студентов, применяется автоматическое тестирование программ, написанных в рамках лабораторных работ. В [8] отмечена двойственность систем автоматизированного тестирования по программированию: для преподавателей выполняется формализованная проверка программы с отчетом о функциональности решений, а студентам необходимо применять творческие умения. Сделан вывод о недостаточности тестирования методом черного ящика, которое не позволяет определить реальные причины некорректной работы программы, так как полностью исключается семантический анализ программного кода. Заметим, что при обучении основам программирования студенты изучают определенный набор базовых алгоритмов. На лабораторных занятиях они пишут программный код, реализуя эти алгоритмы. Тестирование таких программ методом черного ящика не позволяет оценить уровень владения студентом тем или иным базовым алгоритмом. Например, проверка отсортированного массива свидетельствует только о том, произошла ли сортировка исходных данных, но не дает информации о степени владения студентом конкретными алгоритмами. Косвенным признаком может служить время исполнения программы, которое зависит от трудоемкости алгоритма. Однако единственным надежным способом является семантический анализ исходного кода программы. Таким образом, контроль ответа без контроля хода решения нельзя признать исчерпывающим. Тестирование методом черного ящика дает лишь представление о функционировании программы, но не о том, как она написана. Оценка преподавателем программного кода, написанного каждым обучающимся, при массовом обучении требует больших затрат времени. Поэтому актуален вопрос создания инструментов, осуществляющих первичный (предварительный) контроль знаний базовых алгоритмов. При обучении основам программирования полезно давать обучающимся задания на составление решения (программного кода) из предложенных фрагментов (компонентов). Следует учесть, что в программировании многие фрагменты даже простейших программ могут быть написаны разными способами, но выполнять одно и тоже действие. Такие задания будем в дальнейшем называть многовариантными. В данной статье рассматривается задача автоматизации контроля решения многовариантных заданий, при котором исключается семантический анализ программного кода преподавателем вручную. Для этого разработана модель представления многовариантных заданий, а также алгоритм контроля. 111 И.А. Жуков, Ю.Л. Костюк 1. Модель представления многовариантных заданий В [9] изложена идея конструктивно-выборочного метода, при котором обучающийся составляет свой ответ из элементов, являющихся допустимыми смысловыми единицами. В дальнейшем такие единицы будем называть компонентами. Авторы [10] отмечают, что конструктивно-выборочный метод является более удачным, чем альтернативно-выборочный, так как требует творческого подхода от обучающегося и уменьшает вероятность угадывания правильного ответа. В программировании в качестве компонента логично взять одну строку программного кода. Даже для простейшей программы существуют десятки компонент, образующих в различных комбинациях правильные решения. Для преподавателя возможно три способа подбора компонентов: 1) из предложенных компонентов можно составить единственное верное решение, причем каждый компонент входит в верное решение; 2) из предложенных компонентов можно составить единственное верное решение, причем часть компонентов не входит в верное решение (т.е. являются избыточными); 3) из предложенных компонентов можно составить несколько верных решений, причем в каждом случае некоторые компоненты не входят в верное решение, а также допустимы компоненты, не входящие ни в одно решение. Отметим, что каждый следующий способ подбора компонентов включает в себя предыдущие, которые для него являются частными случаями. В разработанной модели за основу взят третий способ подбора компонентов, так как в программировании правильным решением конкретной задачи может быть множество программ. Обучающийся предлагает свой вариант решения в виде упорядоченной последовательности, составленной из множества предложенных компонентов. С формальной точки зрения вариант решения - конкретная упорядоченная последовательность компонентов. Вариант решения может быть правильным (верным) или неправильным (неверным). Все правильные варианты решения должны быть описаны конечным множеством шаблонов. Каждый шаблон состоит из элементов. С точки зрения программирования элемент - какое-либо действие, состоящее из одной или нескольких строк программного кода. То есть элемент - последовательность компонентов. В модели выделено три типа элементов: один компонент, один из компонентов, перестановка компонентов. Элемент «один из компонентов» представляет собой список компонентов, каждый из которых удовлетворяет верному решению, но любое верное решение содержит только один компонент из этого списка. Элемент «перестановка компонентов» представляет собой список компонентов, любая перестановка которых удовлетворяет верному решению. Длиной шаблона будем называть количество элементов в шаблоне. Каждый шаблон для конкретного задания может иметь разную длину. Предложенный обучающимся вариант решения оценивается в баллах. Максимальная оценка принята равной единице. Итоговый балл складывается из оценок за каждый элемент. Если итоговый балл попадает в интервал (0, 1), то решение считается частично правильным. По умолчанию все элементы равнозначны, вес каждого элемента равен единице, деленной на длину шаблона. По усмотрению преподавателя элементам могут быть назначены разные веса. Каждый элемент может быть отмечен как рубежный или как допускающий отсутствие (опциональный). Отсутствие непомеченного элемента добавляет в итоговую оценку 25% его веса. Если в ответе отсутствует элемент, отмеченный как «допускается отсутствие», при расчете итогового балла добавляется 50% веса пропущенного элемента. Если отсутствует рубежный элемент, то в итоговую оценку не добавляется ничего. Если в приведенном ответе отсутствуют все рубежные элементы, ответ оценивается в ноль баллов. Элемент «перестановка компонентов» не может быть помечен как рубежный. Любой элемент, стоящий после элемента «перестановка компонентов», всегда считается рубежным. Следовательно, любой шаблон не может содержать два элемента «перестановка компонентов» подряд. Один компонент может встречаться в нескольких элементах внутри одного шаблона, но два соседних элемента не могу содержать одинаковые компоненты. 112 Модель представления многовариантных заданий для автоматизированного контроля знаний 2. Язык описания шаблонов Для записи шаблонов разработан специализированный формальный язык. Описание предыдущей версии языка и выбранного алгоритма синтаксического анализа приведено в [11]. В данной статье обсуждается расширенная версия языка. Основным нововведением является возможность пометки элементов. Приведем описание языка в расширенной форме Бэкуса-Наура (РБНФ), жирным шрифтом выделены метасимволы, относящиеся к РБНФ: Задание = Шаблон {"|" Шаблон} Шаблон = "{" Элемент {";" Элемент} Элемент = "["? ((ОдинКомпонент | ОдинИзКомпонентов) "*" | ПерестановкаКомпонентов)) "]"? ОдинКомпонент = ИдентификаторКомпонента ЦифрыБезНуля = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" Цифры = "0" | ЦифрыБезНуля ИдентификаторКомпонента = ЦифрыБезНуля {Цифры} ОдинИзКомпонентов = ОдинКомпонент "|" ОдинКомпонент {"|" ОдинКомпонент} ПерестановкаКомпонентов = "(" ОдинКомпонент ";" ОдинКомпонент {";" ОдинКомпонент} ")". В языке используются терминальные символы: круглые скобки, квадратные скобки, фигурные скобки, вертикальная черта («|»), точка с запятой и звездочка. Шаблоны разделяются вертикальной чертой. Компонент решения нумеруется целым числом, начиная с единицы. Элементы внутри шаблона разделяются точкой с запятой. В элементе «один из компонентов» компоненты разделяются вертикальной чертой. В элементе «перестановка компонентов» в круглых скобках записываются компоненты, разделенные точкой с запятой. Элемент, допускающий отсутствие, находится в квадратных скобках. Рубежный элемент помечается звездочкой. Задание, записанное на языке шаблонов, транслируется в массив массивов словарей (формат JSON). Процесс трансляции состоит из трех этапов: лексический анализ, синтаксический анализ, трансформация дерева разбора. На входе лексический анализатор получает запись на языке шаблонов, выходом будет список лексем, после этого список лексем передается в синтаксический анализ, который строит дерево разбора. Затем при помощи специального алгоритма каждой вершине дерева ставится в соответствие запись в массиве массивов словарей. Шаблон представляется массивом словарей, задание - массивом шаблонов. Каждый элемент описывается словарем с тремя ключами: type, components и flag. Ключ type соответствует типу элемента; значением является целое число в интервале [1, 3], где 1 - один компонент, 2 - один из компонентов, 3 - перестановка. Ключ flag соответствует метке элемента; значением является целое число в интервале [0, 2], где 0 - метка отсутствует, 1 - рубежный элемент, 2 - элемент, допускающий отсутствие. Ключ components соответствует массиву компонентов, из которых состоит элемент. Приведем пример задания по дисциплине «Основы программирования» на языке программирования Pascal и его записи на языке шаблонов. Пример. Из заданных ниже компонентов составьте программу, результатом работы которой будет вычисление суммы всех элементов массива т. Длина массива п. Результат суммирования должен быть записан в переменную S. 1. S:=0; 4. i:=1; 7. i:=i + 1; 10. repeat 13. i++; 2. for i:=1 to n do 5. while i n; 14. repeat do 3. S:=S + m[i]; 6. begin 9. end; 12. i += 1; 15. until i < n; Обучающемуся для составление варианта решения предложено 15 компонентов, среди них есть избыточные компоненты: компоненты 7 и 8 идентичны по сути, компоненты 12-14 являются неверными с точки зрения синтаксиса языка Pascal, а компонент 15 не входит в какое-либо правильное решение. Описания задания на языке шаблонов: {[1];2;3*}|{(1;4);5;6;3*;7|8;9}|{(1;4);10;3*;7|8;11} 113 И.А. Жуков, Ю.Л. Костюк Первый шаблон - [1];2;3*. Он состоит из трех элементов. Каждый элемент относится к типу «один компонент». Первый элемент помечен как допускающий отсутствие. Последний элемент помечен как рубежный. Для этого шаблона правильным вариантом решения будет упорядоченная последовательность компонентов 1, 2 и 3. Частично верным будет вариант 2;3. Второй шаблон - (1;4);5;6;3*;7|8;9. Он состоит из шести элементов. Первый элемент относится к типу «перестановка компонентов». Элементы со второго по четвертый - «один компонент», четвертый элемент при этом помечен как рубежный. Пятый элемент - «один из компонентов». Шестой элемент - «один компонент». Для этого шаблона правильными вариантами решения будут четыре последовательности: 1;4;5;6;3;7;9, 1;4;5;6;3;8;9, 4;1;5;6;3;7;9, 4;1;5;6;3;8;9. Эти последовательности содержат компоненты 1, 4 в любом порядке, компоненты 5, 6, 3 в указанном порядке, один из компонентов 7 или 8 (но не оба сразу) и компонент 9. Третий шаблон - (1;4);10;3*;7|8;11. Он состоит из пяти элементов. Первый элемент относится к типу «перестановка компонентов». Второй и третий элементы - «один компонент», при этом третий элемент помечен как рубежный. Четвертый элемент - «один из компонентов». Пятый элемент -«один компонент». Для этого шаблона правильными вариантами решения будут четыре последовательности: 1;4;10;3;7;11, 1;4;10;3;8;11, 4;1;10;3;7;11, 4; 1; 10;3;8; 11. Эти последовательности содержат компоненты 1, 4 в любом порядке, компоненты 10 и 3 в указанном порядке, один из компонентов 7 или 8 (но не оба сразу) и компонент 11. Для задания из примера 1 получим следующий массив массивов JSON-объектом: [[{"type": 1, "components": [1], "flag": 2}, {"type": 1, "components": [2], "flag": 0}, {"type": 1, "components": [3], "flag": 1}], [{"type": 3, "components": [1, 4], "flag": 0}, {"type": 1, "components": [5], "flag": 1}, {"type": 1, "components": [6], "flag": 0}, {"type": 1, "components": [3], "flag": 1}, {"type": 2, "components": [7, 8], "flag": 0}, {"type": 1, "components": [9], "flag": 0}], [{"type": 3, "components": [1, 4], "flag": 0}, {"type": 1, "components": [10], "flag": 1}, {"type": 1, "components": [3], "flag": 1}, {"type": 2, "components": [7, 8], "flag": 0}, {"type": 1, "components": [11], "flag": 0}]]. 3. Алгоритм контроля Для автоматизированной оценки варианта решения авторами статьи предложен следующий алгоритм. Введем понятие эксперта. Экспертом в дальнейшем будем называть автомат, оценивающий соответствие варианта решения (входной последовательности) одному шаблону. Эксперт считывает по два значения из входной последовательности, если текущий элемент не является «перестановкой компонентов» или не помечен как рубежный. Для рубежного элемента эксперт считывает только одно значение. Для элемента «перестановка компонентов» эксперт просматривает все значения до следующего рубежного элемента. Эксперт оценивает соответствие считанной последовательности и текущего элемента, а затем выставляет оценку. Возможно 5 случаев: 1) считанная последовательность полностью соответствует элементу, т.е. компоненты, входящие в элемент, расположены в допустимом порядке, начиная с первого считанного значения; 2) считанная последовательность частично соответствует элементу, т.е. компоненты, входящие в элемент, расположены в допустимом порядке, начиная с элемента n считанной последовательности, тогда количество лишних компонентов увеличивается на n - 1; 3) считанная последовательность не соответствует элементу, тогда количество отсутствующих элементов увеличивается на 1; 4) если текущий элемент является рубежным и считанное значение не соответствует текущему элементу, то количество пропущенных рубежных элементов увеличивается на 1; 5) если текущий элемент помечен как допускающий отсутствие и считанная последовательность не соответствует текущему элементу, то количество пропущенных опциональных элементов увеличивается на 1. В зависимости от результата сравнения эксперт перемещает метку текущего элемента на входной последовательности и независимо от результатов оценки переходит к следующему элементу. Эксперт выставляет представленному ответу оценку от 0 до 1. 114 Модель представления многовариантных заданий для автоматизированного контроля знаний Поскольку задание может быть описано более чем одним шаблоном, то один вариант решения может оцениваться более чем одним экспертом. Например, задание, описанное тремя шаблонами, оценивают три эксперта. Каждый из экспертов выставляет свою оценку, затем из них выбирается наибольшая. Альтернативой такому способу оценивания может быть алгоритм выбора эксперта. Алгоритм оценивает компетентность каждого эксперта для любого представленного варианта решения. Критерии оценки компетентности: 1. Насколько длина представленного варианта решения соответствует длине оцениваемой экспертом последовательности? 2. Насколько множество компонентов представленного ответа соответствует множеству компонентов оцениваемой экспертом последовательности? 3. Насколько множество компонентов оцениваемой экспертом последовательности покрывает множество компонентов, из которых может быть составлен ответ на задание? 4. Сколько рубежных для эксперта элементов присутствует в представленном варианте решения? Эксперту, получившему наибольшую оценку, алгоритм передает оцениваемую последовательность. Оценка, выставленная выбранным экспертом, будет оценкой представленного обучающимся варианта решения. Рассмотрим работу алгоритма оценивания на примерах. Будем использовать задание из примера, представленного выше. Пусть обучающимся предложен вариант решения “1;4;5;6;3;8;9”. Этот вариант решения является верным и соответствует шаблону 2, который оценивает эксперт 2. Результаты оценки экспертов приведены в табл. 1. Таблица 1 Результаты оценки предложенного варианта решения Эксперт Оценка Лишних Отсутствует Отсутствует опциональных Отсутствует рубежных компонентов элементов элементов элементов 1 0 3 1 0 1 2 1 0 0 0 0 3 0 1 4 0 2 Алгоритм выбора эксперта подтверждает, что эксперт 2 имеет наибольшую оценку компетентности для предложенного варианта решения. Результаты оценки компетентности приведены в табл. 2. Т аблица 2 Выбор эксперта для оценки предложенного варианта решения Эксперт Оценка компетентности Критерий 1 Критерий 2 Критерий 3 Критерий 4 1 3,106 2,333 0,273 0,667 1 2 3,186 1,167 0,273 0,875 1 3 2,408 1,4 0,636 0,571 0,5 Пусть обучающимся дан ответ “2;4;10;3;8;11”. Этот вариант решения является частично верным и частично соответствует шаблону 3, который оценивает эксперт 3. Результаты оценки экспертов приведены в табл. 3. Таблица 3 Результаты оценки предложенного варианта решения Эксперт Оценка Лишних Отсутствует Отсутствует опциональных Отсутствует рубежных компонентов элементов элементов элементов 1 0 0 3 0 0 2 0,167 0 4 0 1 3 0,75 1 1 0 1 Алгоритм выбора эксперта подтверждает, что эксперт 3 имеет наибольшую оценку компетентности для предложенного варианта решения. Результаты оценки компетентности приведены в табл. 4. 115 И.А. Жуков, Ю.Л. Костюк Т аблица 4 Выбор эксперта для оценки предложенного варианта решения Эксперт Оценка компетентности Критерий 1 Критерий 2 Критерий 3 Критерий 4 1 2,939 2 0,273 0,667 1 2 2,102 1 0,273 0,375 0,5 3 2,951 1,2 0,636 0,714 1 Из табл. 1-4 можно сделать вывод, что алгоритм выбора эксперта достаточно эффективен. Заключение В результате решения задачи автоматизации контроля знаний в области основ программирования разработаны модель представления многовариантных заданий, язык описания шаблонов и алгоритм контроля знаний. Их применение к реальным задачам дало положительные результаты. Разработанный алгоритм решает проблему автоматизированной проверки программ методом белого ящика и позволяет осуществлять полноценную интеллектуальную автоматизированную проверку знаний в области основ программирования.

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