Разработка и применение моделей дискретной оптимизации при формировании тестов по информатике

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
Вестн. Ом. ун-та. 2011. № 2. С. 173−175.
УДК 519. 8
А. А. Колоколов, Л.В. Ларина
Омский государственный университет им. Ф. М. Достоевского
РАЗРАБОТКА И ПРИМЕНЕНИЕ МОДЕЛЕЙ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ
ПРИ ФОРМИРОВАНИИ ТЕСТОВ ПО ИНФОРМАТИКЕ
Представлен подход к компьютерному тестированию знаний студентов, основанный на использовании задач и методов дискретной оптимизации. Предлагаются математические модели для решения задачи построения оптимального теста, возникающей при контроле знаний по дисциплине «Информатика». Приводятся результаты экспериментальных исследований по этим моделям.
Ключевые слова: модели дискретной оптимизации, разработка теститующих систем, компьютерное тестирование.
Введение
В настоящее время во многих учебных заведениях широко используются рейтинговые системы оценки знаний студента, которые являются важной составляющей новых образовательных технологий и направлены на повышение эффективности процесса обучения. Рейтинговые системы применяются с целью формирования личностноориентированного процесса обучения, стимулирования регулярной работы студентов, раскрытия их творческих способностей. Такие системы способствуют развитию целостного представления об учебной дисциплине и её межпредметных связях, создают основу для построения новой системы оценки качества знаний.
Использование рейтинговых систем повышает объективность, достоверность и «прозрачность» оценки уровня подготовки студентов. Для получения рейтинговой оценки необходимо пройти несколько этапов контроля (текушдй, промежуточный, рубежный, итоговый), каждый из которых проводится с целью систематической проверки и оценки уровня знаний и практических навыков студента. Наиболее популярной формой промежуточного и рубежного контроля является тестирование, позволяющее дать объективную оценку знаний студентов по изучаемой дисциплине, снизить неоднородность предъявляемых требований и повысить производительность труда преподавателя [4- 5- 9].
Перспективным направлением в данной области является развитие и использование систем компьютерного тестирования, которые позволяют существенно сокращать затраты времени при обработке результатов, формировать базы данных об успеваемости, проводить математическую обработку результатов, обладают рядом других преимуществ по сравнению с традиционным подходом. В отличие от контроля в форме опроса, устного экзамена или зачета, который требует много времени, компьютерное тестирование проводится для студентов всей группы или подгруппы одновременно, тем самым направляя учебный процесс в сторону усиления самостоятельной работы студентов. Именно с помощью компьютерных технологий и заданий в тестовой форме можно создать современные обучающие и тестирующие системы.
© А А. Колоколов, Л. В. Ларина, 2011
174
А. А. Колоколов, Л.В. Ларина
Важное место в разработке тестирующих систем занимает задача формирования оптимального теста, состоящая в отыскании набора вопросов (заданий), который «проверяет» все элементы знаний рассматриваемой дисциплины и является наилучшим с точки зрения определенных критериев. Подбор указанных заданий в рамках традиционной технологии выполняется эмпирически на основе знаний и опыта преподавателя. Вместе с тем для решения этой задачи могут быть применены математические модели и методы.
В Омском филиале Института математики им. Соболева С О РАН и Омском государственном университете им. Ф. М. Достоевского развивается подход к построению систем компьютерного тестирования знаний студентов, основанный на использовании дискретной оптимизации [3- 4- 6−8]. В случае обязательной проверки всех элементов знаний некоторой дисциплины формирование оптимального теста сводится к решению известной задачи о наименьшем покрытии множества или её обобщений [2].
В настоящее время создается тестирующая система для дисциплины «Экономико-математические методы», проводится апробация указанной разработки в учебном процессе, ориентированном на студентов экономического факультета ОмГУ [3- 4]. Кроме того, указанный подход используется для контроля знаний студентов по дисциплине «Информатика» на юридическом факультете этого же университета [6−8].
В данной работе построены модели дискретной оптимизации для решения задачи формирования оптимального теста по учебному курсу, содержащему разделы «MS Excel» и «MS Word», проведены экспериментальные исследования, которые указывают на перспективность рассматриваемого подхода.
Постановка задачи
и математические модели
Дадим математическую постановку задачи. Пусть n — число вопросов, на основе которых формируется тест, m — число элементов знаний рассматриваемой дисциплины. Построим двудольный граф G = (V, W, E) с множествами вершин V = {v1,…, vn}, W = {w1,…, wm} и множеством дуг E е {(vj, w): i = 1,…, m- j = 1,…, n}- вершина vj соответствует вопросу j, а вершина Wj отвечает элементу знаний i, i = 1,…, m- j = 1,… n- V- множество вопросов, W- мно-
жество элементов знаний (см. рис.). Дуга (у,-,^) принадлежит множеству Е, если вопрос У проверяет элемент знаний I
V W
Вопросы Элементы знаний
Граф в = (V, Ш, Е)
Подмножество вершин V ^ V называется покрытием, если для любой вершины из V в множестве Е найдется входящая в нее дуга с началом в некоторой вершине множества V. Предположим, что заданы числа с,& gt- 0 (оценка в баллах }-го вопроса), = 1,., П и, а — число вопросов в тесте. Требуется найти покрытие, имеющее максимальную суммарную оценку и состоящее из, а вершин (вопросов).
Для решения сформулированной задачи используется следующая модель целочисленного линейного программирования (ЦЛП). Введем обозначения:
А — булева (m х n) — матрица с коэффициентами
I Г1, если вопрос j проверяет элемент i,
щ H [_0, иначе-
переменные модели:
I 1, если вопрос j включается в тест,
^ H [_0, иначе-
j=1 ,…, n.
Модель ЦЛП имеет вид:
Zcjxj ^ max (!)
j=1
при условиях:
n
Z ajxj ^ bi & gt-1 = 1& gt-->- m (2)
j=i
n
Z xj = а& gt- (3)
j=i
Разработка и применение моделей дискретной оптимизации
175
Xj ?{0,1}, j = 1,…, n. (4)
Целевая функция (1) состоит в максимизации суммарной оценки теста, ограничения (2) обеспечивают проверку i-го элемента знаний не менее bi раз, i = 1,…, m, условие (3) — требование включения в тест a вопросов. Значения b преподаватель может устанавливать отдельно для каждого элемента i в зависимости от его важности. Для решения задачи (1)-(4) могут применяться различные пакеты ЦЛП.
Следует отметить, что ранее нами были построены и апробированы некоторые другие модели, в частности в работе [6] использовалась задача следующего вида:
n
I xj ^ min (5)
j=1
при ограничениях (2), (4). Целевая функция (5) означает минимизацию числа вопросов, включаемых в тест.
Результаты вычислительного
эксперимента
Ранее в работе [6] в соответствии со стандартом курса «Информатика» нами было сформировано множество из 30 элементов знаний раздела «MS Excel» указанной дисциплины. Расчеты, проведенные на основе модели (2), (4), (5), показали, что число включаемых в тест вопросов может быть заметно сокращено по сравнению с существующей практикой (ранее использовался тест из 25 вопросов). В случае bi = 1, i = 1,…, m, получено 6 вариантов теста, включавших по 9 вопросов. При увеличении коэффициентов bi по желанию преподавателя число вопросов в тесте возрастало до 13−15.
С целью апробации модели (1)-(4) были проведены вычислительные эксперименты с различными значениями a, позволившие получить более широкое множество тестов по сравнению с работой [6]. Следует отметить, что для ряда элементов знаний встречалось небольшое число вопросов, с помощью которых они проверялись, поэтому многие из таких вопросов часто входили в оптимальное решение.
Кроме того, были построены такого же типа математические модели и проведены расчеты для раздела «MS Word». В этом эксперименте множество элементов знаний состояло из 17 элементов, а число включаемых в тест вопросов сократилось с 25 до 7. При увеличении значений bi число вопросов в тесте возрастало до 1012. Поиск наилучших значений параметра a для рассматриваемой дисциплины
предполагается продолжить в дальнейших исследованиях.
Расчеты проводились с помощью программы ЦЛП, разработанной в лаборатории дискретной оптимизации ОФ ИМ СО РАН. Экспериментальные исследования показали, что развиваемый подход является достаточно перспективным для создания компьютерной тестирующей системы по дисциплине «Информатика». В дальнейшем предполагается совершенствование полученных математических моделей, их применение к другим разделам указанного курса. Планируется создание компьютерной системы контроля знаний студентов по рассматриваемой дисциплине, разработка алгоритмов и создание программного обеспечения.
ЛИТЕРАТУРА
[1] Емеличев В. А, Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. — М.: Наука, 1981. — 344 с.
[2] Еремеев А. В., Заозерская Л. А, Колоколов А. А. Задачи о покрытии и их приложения // Вычислительные методы и решение оптимизационных задач: материалы междунар. семинара. Новосибирск: ИВМ и МГ СО РАН, 2004. С. 70−76.
[3] Заозерская Л. А, Колоколов А. А, Планкова В. А. Разработка алгоритмов перебора 1_-классов для одной задачи компьютерного тестирования // Ом. науч. вестник. 2008. № 1. С. 12−14.
[4] Заозерская Л. А., Планкова В. А. Применение моделей дискретной оптимизации для разработки автоматизированной системы контроля знаний // Вестн. НГУ. Серия «Информационные технологии». 2008. Т. 6. Вып. 1. С. 47−52.
[5] Калугин К. Х, Щербаков С. М. Компьютерная система тестирования знаний как компонент информационной научно-образовательной среды вуза // Вестн. Академии. 2005. № 1 (20). С. 61−66.
[6] Колоколов А. А., Ларина Л. В. Формирование проверочных тестов по информатике с использованием дискретной оптимизации // Применение новых технологий в образовании: материалы XIX Междунар. конф. Троицк: МОО фонд новых технологий в образовании «Байтик», 2008. С. 326−327.
[7] Колоколов А. А, Ларина Л. В. Применение дискретной оптимизации для решения задач формирования тестов // Единая образовательная информационная среда: проблемы и пути развития: материалы VII Междунар. науч. -практ. конф. -выставки. Томск: Дельтаплан — Омск, 2008. С. 118−119.
[8] Ларина Л. В. Применение дискретной оптимизации для решения задач формирования тестов по информатике // Проблемы оптимизации и экономические приложения: материалы IV Всеросс. конф. Ом. филиал Ин-та математики им. Соболева С О РАН. Омск: Полиграф. центр КАН, 2009. С. 228.
[9] Тягунова Т. Н. Культура компьютерного тестирования. Культура проектирования тестового задания: монография. М.: МгУП, 2006. 300 с.

ПоказатьСвернуть
Заполнить форму текущей работой