Информационно-образовательный портал СОДРУЖЕСТВА НЕЗАВИСИМЫХ ГОСУДАРСТВ
ИНФОРМАТИЗАЦИЯ ОБРАЗОВАНИЯ
И ДИСТАНЦИОННОЕ ОБУЧЕНИЕ В СНГ
Информационно-образовательный портал СОДРУЖЕСТВА НЕЗАВИСИМЫХ ГОСУДАРСТВ  

Страны
Азербайджанская Республика
Республика Армения
Республика Беларусь
Республика Казахстан
Кыргызская Республика
Республика Молдова
Российская Федерация
Республика Таджикистан
Туркменистан
Республика Узбекистан
Украина

Типы материала
Информационно-коммуникационные технологии
Дополнительные информационные материалы
Нормативно-правовое обеспечение
Организация и методики обучения
Экономика образования
Межгосударственное сотрудничество
Образовательные центры
Методики обучения
Межвузовское сотрудничество
Повышение квалификации
Международные проекты и гранты, конкурсы
Конференции, симпозиумы, семинары и др.
Библиотека
 
Журнал «Вестник РУДН» серия «Информатизация образования»
 
2014, №4
2014, №3
2014, №2
2014, №1
2013, №4
2013, №3
2013, №2
2013, №1
2012, №4
2012, №3
2012, №2
2012, №1
2011, №4
2011, №3
2011, №2
2011, №1
2010, №4
2010, №3
2010, №2
2010, №1
2009, №4
2009, №3
2009, №2
2009, №1
2008, №4
2008, №3
2008, №2
2008, №1
2007, №4
2007, №3
2007, №2-3
2007, №1
2006, №1(3)
2005, №1(2)
2004, №1
Научные и специальные электронные ресурсы
Учебная, научная и специальная литература
Комиссия по дистанционному обучению совета по сотрудничеству в области образования государств-участников СНГ
Новости

Оценка веса заданий для формирования иерархической системы тестирования по информатике


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

Текст документа

С.В. Криволапов

Кафедра программного обеспечения и администрирование информационных систем

Курский государственный университет

 

 

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

Представим систему обучения в виде графа (рис. 1).

Рис 1. Классическая система обучения

 

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

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

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

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

Рассмотрим схему, представленную на рис. 2, более подробно с математической точки зрения.

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

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

Рис. 2. Двухуровневая система проверки знаний

 

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

Причем в зависимости от результатов этот путь может быть представлен в виде цепи (в случае всех правильных ответов) или иметь ветвление из вершин графа.

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

Система предназначена для проверки знаний и уточнения, на каком уровне обучаемый допускает ошибку.

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

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

Задача о кратчайшем решении. Пусть задана адаптивная система тестовых заданий из n+1 вопросов, в которой выделены две вопроса - вход (нулевая вопрос) и выход (вопрос с номером n). Для каждой ответа заданы числа, называемые весом ответа.

Весом решения системы тестовых заданий называется сумма весов входящих в него ответов (если веса ответов не заданы, то вес решений определяется числом входящих в него ответов). Задача заключается в поиске кратчайшего решения (решения минимального веса) от нулевого вопроса до вопроса с номером n.

Известно, что для существования решения с минимальным весом не­обходимо и достаточно отсутствия в решение ответов отрицательного веса.

Предположим, что в решении нет повторов. Тогда всегда можно пронумеровать вопросы таким образом, что для любого ответа (i, j) имеет место j > i. Такая нумерация называется правильной. Легко показать, что в системе заданий без повторов всегда существует правильная нумерация. Обозначим Lij вес ответа (i;j). Кратчайший решение в системе заданий, имеющей правильную нумерацию, определяется следующим алгоритмом (рис. 3).

Алгоритм 1:

Шаг 0: Помечаем нулевое задание индексом λо = 0;

Шаг k: помечаем задание k индексом .

Индекс ответа λn будет равен длине кратчайшего решения. На рисунке __ приведен пример применения алгоритма 1 для опреде­ления кратчайшего решения (числа у дуг равны весам ответов, индексы вопросов помещены в квадратные скобки, кратчайшие решение выделено двойными линиями).

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

 

 

 

 

Рис. 3. Поиск кратчайшего пути решения

 

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

Алгоритм 2 (алгоритм Форда).

Шаг 0: Помечаем нулевое задание индексом , все ос­тальные задания индексами , ;

Шаг k: Рассматриваем все ответы. Если для ответа (i;j), , то вычисляем новое значение .

Индексы устанавливаются за конечное число шагов. Обозначим: { } - установившиеся значения индексов, которые обладают следующим свойством: величина  равна весу кратчайшего решения из нулевого задания в задание i. Кратчайшие решение из задания 0 к заданию i определяется методом обратного хода.

Если вес всех ответов неотрицательны, то для поиска кратчай­шего решения применим следующий алгоритм.

Алгоритм 3.

Шаг 0: Помечаем нулевое задание индексом ;

Шаг k: П??сть уже помечено некоторое множество заданий. Обозначим Q - множество непомеченных заданий, смежных с помеченными. Для каждой задания k  Q вычисляем величину , где минимум берется по всем помеченным заданиям i, смежным с заданием k. Помечаем задание k, для кото­рой величина  минимальна, индексом .

Подобную процедуру повторяем до тех пор, пока не будет помечено задание n. Длина кратчайшего решения равна , а само кратчайшее решение определяется так, как это было описано выше.

Запишем задачу о кратчайшем решение как задачу линейного про­граммирования (ЛП). Пусть , если ответ (i;j) входит в решение , , если ответ (i;j) не входит в решение .

Задачу о минимальном решения можно записать в виде:

                                                                                                       (1)

,                                                                                                       (2)

.                                                                                                  (3)

Любое решение системы неравенств (2)-(3) определяет решение в системе заданий без повторов (но не в системе заданий с повторами).

Пусть все повторы имеют строго положительный вес, то есть нет повторов отрицательного и нулевого веса. Тогда решение задачи (1)-(3) определяет путь кратчайшего решения.

Сформулируем задачу ЛП, двойственную задаче (1)-(3), по­ставив в соответствие ограничениям (2) двойственные переменные  и , а ограничениям (3) - двойственные переменные { }, :

                                                                                                             (4)

.                                                                                                     (5)

По теореме двойственности линейного программирования , для оптимальных решений задач (1)-(3) и (4)-(5) значения целевых функций совпадают.

Задача (4)-(5) называется задачей о потенциалах заданий тестовой системы. Общая ее формулировка такова: найти потенциалы задания i}, удовлетворяющие системе неравенств (5) и максимизирующие некоторую функцию Ф(λ), где λ=(λ0, λ1,…, λn). Примером является задача о ближайших потенциалах,   в   которой , где  могут интерпретироваться как желательные потенциалы.

Аналогично задаче о кратчайшем решение формулируется и ре­шается задача о максимальном (длиннейшем) решении системы задании - достаточно изменить знаки ответов на противоположные и решить задачу о крат­чайшем решение. Для существования решения задачи о максимальном решении необходимо и достаточно отсутствия повторов положительной длины.

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

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

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

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

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

 

ЛИТЕРАТУРА

 

[1] Айсмонтас Б.Б. Теория обучения: схемы и тесты. – М.: Владос-Пресс, 2002. – 208 с.

[2] Дубров С.И., Иечаев Ю.И., Резников Ю.Е. Рейтинговая система оценки знаний как способ стимулирования работы студентов // URL: http://www. ict.edu.ru/vconf/index.php.

[3] Образцов П.И. Обеспечение учебного процесса в условиях информатизации высшей школы // Педагогика. – 2003. – № 5. – С. 27–32.

[4] Кузо??лева. К.Т. Конструирование педагогических тестов на основе современных математических моделей // URL: http:// www.informika.ru.

[5] Криволапов С.В. Средства информатизации проверки результативности обучения, основанные на иерархических системах заданий // Вестник РУДН. Серия: Информатизация образования. 2010. №3. С.5-12

[6] Попкова В.А., Коржуев А.В. Дидактика высшей школы: Учеб. пособие для студентов педвузов. – М.:Академия, 2008. – 228 с.


Автор оригинала: С.В. Криволапов
Источник оригинала: Журнал Вестник РУДН серия «Информатизация образования», №2, 2011

Новости
16.06.2017

Российский университет дружбы народов объявляет о проведение первой волны вступительных испытаний среди иностранных граждан для обучения на программах магистратуры на контрактной основе. Первая ...

13.10.2016

26 октября-27 октября 2016 года Российский университет дружбы народов проводит Международную конференцию «Сетевые университеты и международный рынок труда (пространства БРИКС, СНГ, ШОС)».

19.05.2016

The Peoples’ Friendship University of Russia (PFUR) announces the beginning of admission of foreign citizens who graduated from Bachelor and Specialist Degree programs of PFUR and other Russian and ...

19.05.2016

Российский университет дружбы народов (РУДН) объявляет о наборе иностранных граждан -выпускников бакалавриата и специалитета РУДН и других российских и зарубежных ВУЗов на программы магистратуры на ...

11.12.2015

Проект рекомендаций Семинара-совещания научной общественности по проблемам международного научно-технического и образовательного сотрудничества