автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и анализ стохастической и аппроксимационной моделей адаптивного тестирования для информационно-управляющих систем

На правах рукописи

004Ь Я1 Фоминова Наталья Ссргссвпа

РАЗРАБОТКА И АНАЛИЗ СТОХАСТИЧЕСКОЙ И АППРОКСИМАЦИОННОЙ МОДЕЛЕЙ АДАПТИВНОГО ТЕСТИРОВАНИЯ ДЛЯ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в приборостроении)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

И 3 май 2010

Москва-2010

004601847

Работа выполнена на кафедре «Информатики и программного обеспечения вычислительных систем» Московского государственного института электронной техники (технического университета)

Научный руководитель

Доктор технических наук, профессор Гагарина Лариса Геннадьевна

Официальные оппоненты Доктор физико-математических наук,

доцент

Гончаров Виктор Анатольевич

Кандидат технических наук, Степанов Андрей Михайлович

Ведущая организация

Институт системного анализа Российской академии наук (ИСА РАН)

Защита состоится « » ьссал 2010 года в /// : „ЪО на заседании диссертационного совета Л 212.134.02 при Московском государственном институте электронной техники (техническом университете) по адресу: 124498, Москва, Зеленоград, проезд 4806, д.5.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электронной техники (технического университета).

Автореферат разослан « £0 » Оп/бепЛ 2010 г.

Ученый секретарь

диссертационного совета Д 212.134.02 до,сгор технических наук, доцент

А.В. Гуреев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

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

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

Научной проработки этой проблемы касались специалисты в области тестирования технических устройств (Яблонский C.B., Тоценко В.Г., Чжен Г., Малышенко Ю.В. и др.); тестирования программного обеспечения (МайерсГ., ДастинЭ., Канер С., ЛипаевВ.В., Кларк Э.М. и др.); контроля знаний и разработки педагогических тестов (Аванесов B.C., Нейман Ю.М., Рудинсккй И.Д., Симанков B.C., Луценко Е.В. ' и др.). Существуют публикации в периодической печати, материалы научно-практических конференций и семинаров, посвященные проблеме тестирования в отдельных предметных областях, однако единой концепции тестирования не существует. Таким образом, проблема разработки моделей и алгоритмов адаптивного тестирования в настоящее время является актуальной.

Объект и предмет исследования

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

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

Цель и задачи исследования

Целью работы является разработка моделей и алгоритмов адаптивного тестирования и программная реализация системы интеллектуального тестирования на основе разработанных алгоритмов. Для достижения цели в работе решены следующие задачи:

- анализ современных подходов к тестированию в различных предметных областях;

- разработка стохастической и аппроксимационной моделей адаптивного тестирования;

- создание алгоритмов адаптивного тестирования согласно" стохастической и аппроксимационной моделям для решения задач наискорейшего поиска ошибки и определения наилучшего приближения соответственно;

- верификация алгоритмов в инструментальных средах математического моделирования;

- разработка и опытная эксплуатация программно-аналитического комплекса интеллектуального тестирования (ПАК ИТ) на основе предложенных алгоритмов.

Методы исследования

Для решения задач использована теория адаптивного управления, теоретико-графовые и теоретико-вероятностные методы, ■ апгтроксимационные методы вычислительной математики, методы матричного анализа и математической статистики. Теоретические положения подтверждены результатами моделирования в инструментальных средах математического моделирования. Методы модульного программирования использованы при создании ПАК ИТ. Научная новизна

Диссертация содержит научно-обоснованные модели адаптивного тестирования, алгоритмь1, основанные на разработанных моделях, а также пример программной реализации алгоритмов. В процессе исследований получены следующие новые научные результаты:

1. На основе проведенного анализа подходов к тестированию , определены критерии адаптивного тестирования и требования к

математической модели.

2. Предложена стохастическая модель адаптивного тестирования для решения задачи наискорейшего поиска ошибки.

3. Предложена аппроксимационная модель адаптивного тестирования для определения наилучшего приближения.

4'. Доказано, что метод выбора последовательности запросов при тестировании не зависит от непрерывности или дискретности входных/выходных параметров.

5. Разработаны алгоритмы адаптивного тестирования на основе стохастической и аппроксимационной моделей тестирования для задачи наискорейшего поиска ошибки и определения наилучшего приближения.

6. Осуществлена программная реализация алгоритмов адаптивного тестирования в виде программно-аналитического комплекса интеллектуального тестирования. Получено свидетельство об официальной регистрации программы для ЭВМ №2007611826 «Программно-аналитический комплекс интеллектуального тестирования «Logos» (ПАК ИТ «Logos»)».

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

Самостоятельное практическое значение имеют:

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

- алгоритмы адаптивного тестирования на основе разработанных моделей;

- программная реализация алгоритмов адаптивного тестирования.

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

Достоверность полученных результатов

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

Личный вклад автора

Основные результаты диссертационной работы получены автором лично.

1. Исследованы современные подходы к тестированию, определены критерии адаптивного тестирования и требования к математической модели.

2. Разработаны стохастическая и аппроксимационная модели и алгоритмы адаптивного тестирования для задач наискорейшего поиска ошибки и определения наилучшего приближения соответственно.

3. Проведена верификация алгоритмов в существующих инструментальных средах математического моделирования.

4. Осуществлена программная реализация разработанных алгоритмов, разработка и внедрение программно-аналитического комплекса интеллектуального тестирования.

Реализация и внедрениё результатов работы 1 ' Диссертационная работа выполнялась в соответствии с планом научно-технических Исследований кафедры ИПОВС МИЭТ и является составной частью следующих научно-исследовательских работ, проводимых в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг.:

- «Разработка моделей и алгоритмов тестирования знаний с динамической логической структурой»;

- «Исследование интеллектуальных алгоритмов определения уровня усвоения учебного материала и разработка концептуальных теоретических основ построения интегрированных систем адаптивного тестирования».

' Разработанный в рамках исследования ПАК ИТ «Logos» отмечен медалью на Всероссийской выставке научно-технического творчества молодежи «НТТМ-2007» (г. Москва, ВВЦ, 27.06.07) и внедрен в ФГОУ В ПО «Калининградский государственный технический университет» для автоматизированного контроля знаний. Разработанные модели и алгоритмы внедрены в ОАО «ПроРеск Сервис» для тестирования программного обеспечения интегрированной информационной системы

«Мегсигу-СГ». Результаты диссертационной работы используются также в учебном процессе кафедры ИПОВС МИЭТ в курсах «Интеллектуальные информационные системы», «Компьютерные технологии в науке и образовании», «Системный анализ и моделирование процессов и систем». Внедрение подтверждено актами.

На защиту выносятся следующие положения:

1. Использование стохастической модели адаптивного тестирования позволяет сформировать обоснованный критерий выбора тестовых запросов для задачи наискорейшего поиска ошибки.

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

3. Разработанные алгоритмы на основе предложенных моделей адаптивного тестирования позволяют реализовать выбор запросов по сформированным критериям, что позволяет ' учитывать динамические свойства тестируемой системы.

4. Применение алгоритмов позволяет увеличить быстродействие поиска ошибки более чем в 2 раза; увеличить точность приближения при фиксированном количестве запросов на 3 - 58 % в зависимости от их количества; уменьшить количество тестовых запросов при фиксированнойточности тестирования в среднем на 20%.

5. Программная реализация разработанных алгоритмов может быть использована в интеллектуальных системах контроля знаний.

Апробация работы

Основные положения, выводы и предложения, сформулированные в диссертации, представлены на 15 научных конференциях, из Них 7 международных и 8 всероссийских.

Публикации

По теме диссертации опубликовано 20 печатных работ, в том числе 5 статей (одна в журнале, рекомендованном ВАК), 15 тезисов и докладов. Без соавторов опубликовано 7 работ. Список опубликованных работ приведен в конце автореферата.

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы из 110 наименований и четырех приложений. Диссертация включает 119 страниц основного текста, 59 рисунков, 3 таблицы, 69 страниц приложений. Приложения содержат акты о внедрении и использовании результатов, копию свидетельства о регистрации, листинги программ.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, сформулированы цель и задачи исследования, приведено краткое содержание работы.

В первой главе проанализированы современные подходы к тестированию, рассмотрены отличия адаптивных систем тестирования от адаптивных систем управления, определены задачи тестирования.

Исследованы труды, посвященные тестированию технических устройств, программного обеспечения и уровня усвоения учебного материала. Среди работ по тестированию технических устройств (диагностики неисправностей), основополагающей является теория тестирования С.В. Яблонского, которая предполагает наличие информации обо всех видах неисправностей для построения тестовых таблиц или о структуре эталонной системы и тестируемого устройства, что в большинстве случаев практически не достижимо. Также в тестировании технических устройств широко используется байесовский подход, который также требует большого количества априорной информации (начальная модель системы с распределением вероятностей всех внутренних параметров), но направлен на ее максимальное использование, непрерывный пересмотр и переоценку с учетом получаемых выборочных данных об исследуемом процессе. Байесовский подход можно считать адаптивным, однако он трудно реализуем ввиду большой вычислительной сложности. Учитывая эти особенности, можно сделать вывод, что актуальной является разработка моделей и алгоритмов по аналогии с байесовским подходом, но с использованием меньшего количества априорной информации (или полного ее отсутствия), с постепенным ее дополнением.

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

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

наилучшим образом оценивать уровень знаний тестируемого с заданной точностью и предсказывать его ошибки на тестовом запросе.

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

Цель тестирования - установление эквивалентности тестируемого объекта эталону. Необходимыми компонентами задачи тестирования являются: объект тестирования, эталон (идеальная система), критерий эквивалентности (определяет меру схожести эталона и объекта тестирования) и мера эквивалентности, с которой достижим критерий эквивалентности. Алгоритм тестирования можно построить в том случае, если задана некоторая информация, которая используется для выбора измерений И определения достигнутых результатов тестирования. Использование априорной информации позволяет сформировать модель тестируемого, на основе которой возможен осмысленный выбор тестовых запросов.

Процесс тестирования решает одну из двух задач: ; - наискорейший поиск ошибки (задача актуальна в случае тестирования устройств или программного обеспечения);

- определение наилучшего приближения, другими словами получение большего количества информации о системе (педагогическое тестирование и тестирование программного обеспечения).

С точки зрения модели тестируемая система F есть отображение из множества входных сигналов А во множество выходных сигналов В, т.е. F: 'A-> В. Поскольку входные и выходные сигналы могут быть как дискр(етными, так и непрерывными, то целесообразно рассмотреть каждый из случаев для каждой задачи.

Построение математических моделей адаптивного тестирования осуществляется методом «черного ящика», причем: - заранее ничего не известно о структуре системы, возможны только предположения;

-. a priori известны входные/выходные параметры системы, и

существуют предположения о связи входных и выходных параметров;

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

- исключено внешнее воздействие;

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

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

Пусть /г : а -» В - отображение, соответствующее идеальной

системе (номинальное значение, определяемое требованиями к тестируемой системе, документацией). На множестве А определим отношение: Уа,,а2еЛ (а, = я2) «> (F(c,) = Ft{ax) о F{a2) = F,(a2)), где F,(a{) - ответ идеальной системы на a,, F(a,) - ответ тестируемой системы на а,. В работе доказана рефлексивность, симметричность и транзитивность данного отношения, т.е. оно является отношением эквивалентности. Критерием эквивалентности будем считать совпадение реакций эталона и тестируемой системы на тестовые запросы. Тестом назовем множество % = {{a, F,(a))| а е а}- Успешным

тестом - r:3(a,Fl (а)) е г : F, {а) ^ F {а), где и - длина теста т .

Предположим, что задана априорная информация о связи некоторых тестовых запросов. Тогда, установив численную меру взаимосвязи запросов, получим модель системы.

Пусть G = (F, Е) - дерево, вершинами которого являются запросы V-A. 3!veV: определена р(у) - вероятность того, что на запросе произойдет ошибка: F(v) # F, (v) ■ Отображение f \Е -> [0,1] с R /((v,,v2)) = p(vl = v2) назовем вероятностью эквивалентности вершин, которая выражает вероятность существования ребра.

Проведем расширение дерева G(V, Е) до полного графа G'(V\ Е') по следующему алгоритму: Шаг 1. Положим Е'=Е и V'=V■

Шаг 2. Для любых троек v,,v2,v3 е V, таких что ребра (v„v2) и (v2,v3) принадлежат Е\ при условии определенности /((v,,v2)) и /((v2,v3))

^определим новое ребро (у,,у3)еЕ (если оно еще не существует).

И положим /((V,, у3 ))=/((у,, у2))* /((у2, у3)) =

= /((^^2))/((у2)у3))+(1-/((у1,у2))Х1-/((у2>у3))) при условии что:

- /((у,,у3)) еще не определено;

£ - |/оИ((^,г3))-0.5|<|/((у1,у3))-0.5|, где /оИ((у„у3)) ранее

определенное значение /((у,,у3))-

В работе доказана коммутативность и ассоциативность операции *, что упрощает построение полного графа.

Шаг 3. Если граф С= (У',Е') не полный, повтор Шага 2, иначе выход.

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

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

Для статического тестирования:

д(г) = 1 - (1 - д(«))П № - а, )(1 - 2р{а)) + р(а)), р(а) > 0.5

1=1

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

а, : (тах(р(а = а,)), р(а) > 0,5)л (тт(р(а = а,)), р(а) < 0,5) •

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

р(г) = 1-(1-р(а))П ( Р(а] -а, ))' пРичем а, выбирается так,

1=1 , <l|taj<=л

что достигается тт(/?(а = а)) > т.е. следующим выбирается тестовый

запрос, минимально эквивалентный всем заданным. !' На основе правил выбора тестовых запросов получены алгоритмы статического и динамического тестирования для решения задачи наискорейшего поиска ошибки в дискретном случае (рис.1).

а б Рис. 1. Схема алгоритма решения задачи наискорейшего поиска ошибки: а - статическое тестирование; б - динамическое тестирование

Численный анализ разработанных алгоритмов показал, что вероятность нахождения ошибки на тестовом запросе для динамической стратегии тестирования выше, чем для статической (рис.2, верхняя ломаная - вероятность ошибки при динамической стратегии, нижняя -при статической). Средний шаг обеспечения необходимой вероятности успеха теста у динамической стратегии в два раза меньше, чем у статической (рис. 3, левый пик гистограммы соответствует динамическому тестированию, правый - статическому).

« 1

У 0.95 я 0.9

. '*§ ".в : >• 0,75

л

5 0,7 I 0.65

к

I 0,6

т 0,651 23456789 10 * " 3 4 5 в 7 6 9 10 Номер шага Номер шага

Рис.2. Зависимость вероятности Рис.3. Гистограмма количества заданий успеха на тесте от шага для достижения вероятности успеха 0.95

Также в работе построена математическая модель многокритериального тестирования (для систем, имеющих большое число измеряемых характеристик) для решения задачи наискорейшего поиска ошибки, проведены численные эксперименты, подтверждающие эффективность разработанных алгоритмов адаптивного тестирования. ■

В диссертации установлена связь между задачей наискорейшего поиска ошибки в случае исследования непрерывной функции и уже решенной задачей для дискретного случая. Введем функцию верности результата: [1, = С(а>) [0

Определим эквивалентность, учитывая введенную функцию: а, =аг ос(а,) = с(а2), причем П(с) = А, Е(с)={0,1}, в общем случае для перехода к непрерывному случаю расширим область значений: Е(с) = [од]с Я ■ Определим вероятность эквивалентности р(а1 =а2) как вероятность того, что значения функций с(а,) и с(а2) совпадают, т.е. р(с(йГ[) = с(а2)) ■ Однако, вероятность совпадения двух точек на отрезке мала. Тогда считаем, что две точки попадут в один интервал и совпадут

■

с точностью е, т.е. р|с(а,)-с(д2)|<г} при малом е, и определим'

вероятность эквивалентности, как р(ах ¿а2) = р\ с(о,)-с(я2)| < е],

причем Е(с) = [0, l], D(c) = [-1, l].

Определим функцию плотности вероятности как р{с(х) = у} для^; всех уsЕ(с(х)) и фиксированного хеА. Аналогично определим ' плотность' вероятности эквивалентности р{с(х1)-с(х2) = у] для всех пар {х„х2} из А2 и всех уе[-1,1]сЛ- При этом наиболее вероятно, что р{с{хх)-с(х2) = у} = g(| х, -х21) = g(p(x,,х2)).

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

р{сЫ<а}= )p{c(x,-) = e}ds = )P%AS)*pf^S)ds' гДе pf " о о

ошибка на Xjlx, также р{ф/а)-0 = у} = р{с(х^) = у). Положим, что ошибка происходит при запросе , если р{с{хх )<а), где а -фиксированная малая величина. Обозначим данную функцию за р(х,) и

рассмотрим два способа проведения тестов.

При статическом тестировании вероятность ошибки на тесте:

/7(г) = 1 - а - /»(*д,))ПС1 - ' при4ем />(*;*) >0.5- Максимизация /=1

проводится' по правилу выбора тестовых запросов, аналогично дискретному случаю.

Для динамического тестирования вероятность ошибки на тесте:

р(г) = 1-(1-^))П ( 1 - )р{с(х,)-c(Xj) = h})p\c(Xj) = S-h}d5 dh)> , ]

'=i -i о . . f<

г i

причем x, выбирается так, что достигается максимум вероятности':1

большого различия с(>у)-с(х().

В результате численного эксперимента получен график, представленный на рис.4 (нижняя ломаная иллюстрирует алгоритм динамического тестирования, верхняя - случайного). Можно сделать вывод, что динамическое тестирование дает лучшие результаты, чем случайное или статическое тестирование.

Рис. 4. Логарифм произведения значений функции по выбранным точкам в зависимости от шага

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

1. Наличие априорной информации предоставляет преимущество статическим и динамическим стратегиям над случайными, однако динамические стратегии лучше статических.

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

3. В модели очевидна взаимосвязь между количеством запросов и точностью получаемого при тестировании результата.

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

Задача наилучшего приближения функции верности ответов системы, определенной на множестве запросов с: V -> {0,1} (множеству вершин соответствует множество запросов), заключается в наилучшем «предсказании» ошибок на тестовом запросе. Поскольку известна связь ме'экду ' вероятностями ошибки для любых двух тестовых запросов (определяемая через вероятность эквивалентности), то изменение вероятности ошибки на одном тестовом запросе влияет на вероятности ошибки на остальных запросах.

Пусть функция тт(р(у), 1-/1^)) характеризует неопределенность

в ' наступлении одного из событий: с (у) = 0, с(у) = 1. Мерой качества приближения функции с(у) положим остаток аппроксимации К = тах(гшп(рО)Д-р(у)))> гДе максимум определяется по вершинам у,

иеУ

принадлежащим графу. Поскольку известны связи между вершинами в графе, то при увеличении числа зафиксированных вершин (для которых '1- известно, наступило ли одно из событий с(у) = 0 или с(у) = 1) остаток Л будет монотонно стремиться к нулю. Выбор такой функции произведен по аналогии с чебышевской мерой отклонения функций в С[а,Ь] ■ Теперь задачу можно сформулировать следующим образом -наискорейшим способом устремить остаток аппроксимации Л к нулю.

В случае выбора вершин при статическом тестировании следует взять те запросы, на которых находятся максимумы, определяющие Я, т.е. у' = а^(тах(тт(р(у),1 - р{у))))> где V* - множество уже

уеУ\У*

• выбранных вершин (уже заданных тестовых запросов).

В случае динамического тестирования в качестве следующего тестового запроса следует выбрать:

V = а^

/

тах

тт

Ч

'1 - тах^у, )/>(у, = У2 ) + (1 - р(у, ))(1 - />(п = У2 ))),'

тахМ^О', = у2) + (1 - р(у,))(1 - р(у, = у2)))

Внешний максимум берется по всем невыбранным вершинам графа. Внутренний максимум берется по всем выбранным вершинам графа для определения, в Какой вершине фиксирование события с(у) = 0 или с(у) = 1 накладывает наиболее сильное ограничение на предположение о вероятностях выявления ошибки для других вершин графа. Алгоритмы соответствуют правилам выбора запросов при определении наилучшего приближения в статическом и динамическом случаях (рис.5).

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

с

<

Начало

3

Пока можно передавать запросы

I ~

тах =

1=2..|У|"

т = ггип(р(у),1-рМ)

Да ^ \ Нет

шах=т ¡пйех=1

Передаем системе запрос Эмех и фиксируем ее отклик

У=\Л{ам<*} -1-

^ Конец ^

С

<

Начало |

3

Пока можно передавать запросы

>

С

Конец

3

Рис. 5. Схема алгоритма решения задачи наилучшего приближения: а - статическое тестирование; б - динамическое тестирование

Номер шага Остаток аппроксимации за заданное число шагов

Рис. 6. Сравнение статического и Рис,7. Гистограмма попадания остатка динамического тестирования аппроксимации в заданную область

Для аппроксимационной модели можно отметить следующее:

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

2. С увеличением числа запросов точность оценки повышается.

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

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

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

Пусть, выбирая точки в узла!х отличных от системы Чебышева, удалось найти решение уравнения р'(х) = 0. Меньший остаток можно получить, проведя интерполяцию по Эрмиту. Для доказательства этого предположения проанализируем отношение остатков Лагранжа () и Эрмита(91д):

0 + 1)! if

ч л л

(Л +1J! i=i ы

Пусть получено только одно такое условие N = n+1,3z', е К': С, = 2, fm(z\) = О- Тогда остаток можно оценить как

a = max|9lf| обозначим z\ = z,+er Учитывая i _ ,

тах|Э1* | шах |/(л+2) (77)|

tjeA

оценим математическое ожидание логарифма отношения остатков интерполяции (т.е. меру неопределенности приближения), при условии, что все отклонения имеют один знак:

M[ln(«)] = £с, Jin|sign(s) + zl+s\f(e)d£ + nln(2)-ln((w + 2)d)

M -<o

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

В четвертой главе описана программная реализация разработанных алгоритмов в виде программно-аналитического комплекса интеллектуального тестирования ПАК ИТ «Logos».

Особенностью комплекса является интеллектуальный режим тестирования, который позволяет точнее и глубже оценить знания тестируемого, используя то же количество вопросов, что и при тестировании со случайным выбором

вопросов. Это возможно благодаря тематическому упорядочиванию вопросов, что позволяет, не зная смысла заданий, выстраивать логическую структуру опроса, с целью получения большего количества информации о тестируемом. Структура ПАК ИТ «Logos» представлена на рис.8.

В ходе опытной эксплуатации комплекса проведена верификация полученных результатов. Тестирование знаний репрезентативной выборки студентов проводилось'случайным образом и с помощью ПАК ИТ «Logos». Результаты оценивались по остатку аппроксимации исследуемых параметров объектов и оценке его математического ожидания. Графическая интерпретация полученных результатов (рис. 9) позволяет сделать вывод, что динамическое тестирование лучше случайного, т.к. остаток аппроксимации первого меньше.

с - • Изменение 1

| Система запуска I [ графических | > настроек '

1 Система 1 антивирусной ■ч проверки ! * I Инсталлятор \ ! обновлений I ч _ _. »

Модуль анализа

результатов психологического тестирования

Психологическое тестирования

Центр настроек психологического тестирования

Печать списка сгенерированных вариантов

Генератор I—

Постобработчик сгенерированных вариантов

Центр настроек тестирования

Случайное I тестирование Г

Повторитель тестового профиля

Вывод в МАТ1-АВ

Модуль расчета

статистики (стат. анализа)

Интеллектуальное тестирование

\

Рис.8. Структура ПАК ИТ

8 1Ф 12 14 Количество вопросов

Рис.9. Зависимость оценки математического ожидания остатка аппроксимации от количества заданных вопросов (нижняя кривая - динамическое тестирование,

верхняя - случайное)

В заключение диссертационной работы сформулированы основные выводы и полученные результаты.

В приложениях приведены программы для проведения численных экспериментов по анализу разработанных моделей, фрагменты кода ПАК ИТ «Logos», копия свидетельства о регистрации и акты о внедрении результатов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1. Предложена стохастическая модель адаптивного тестирования для задачи наискорейшего поиска ошибки.

2. Разработана аппроксимационная модель адаптивного тестирования для определения наилучшего приближения.

3. Получен алгоритм адаптивного тестирования на основе стохастической модели для задачи наискорейшего поиска ошибки.

4. Получен алгоритм адаптивного тестирования на основе аппроксимационной модели для определения наилучшего приближения.

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

6. Обоснована связь между дискретным и непрерывным случаями, т.е. доказано, что метод выбора последовательности запросов при тестировании не зависит от непрерывности или дискретности входных/выходных параметров.

7. Разработанные алгоритмы адаптивного тестирования обеспечивают:

- увеличение быстродействия поиска ошибки (задача наискорейшего поиска ошибки) более чем в 2 раза;

- увеличение точности приближения при фиксированном количестве запросов (задача определения наилучшего приближения) на 3-58% в зависимости от количества тестовых запросов;

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

8. Разработан и внедрен программно-аналитический комплекс

интеллектуального тестирования (ПАК ИТ «Logos»), опытная эксплуатация которого доказывает повышение эффективности тестирования обучаемых в среднем на 12%.

Публикации по теме диссертации

1. Свидетельство об официальной регистрации программы для ЭВМ №2007611826. Программно-аналитический комплекс интеллектуального тестирования «Logos» (ПАК ИТ «Logos») / Гагарина Л.Г., ПортновЕ.М., Калинников И.С., ФоминоваН.С., Румянцева Е.Л., Трояновский В.М.; заявитель и правообладатель ГОУ ВПО Московский государственный институт электронной техники (технический университет) - заявка №2007610823, заявл. 13.03.2007; зарег. 28.04.2007.

2. Гагарина Л.Г., Кемарская Е.Б., Фоминова Н.С. Применение сетевых технологий в обучении дисциплине «Информатика» // Профессиональный учебник. - М.: ЮНИТИ-ДАНА, 2006. -№4(10). - С.32-33.

3. РумянцеваЕ.Л., Калинников И.С., ФоминоваН.С. Программно-аналитический комплекс интеллектуального тестирования // Электроника-2006. Всероссийский молодежный научно-инновационНый конкурс-конференция: Тезисы докладов. М.:МИЭТ, 2006. - С.58.

4. Гагарина Л.Г., Калинников И.С., ФоминоваН.С. Принципы интеллектуального тестирования // Приоритетные направления развития' науки и технологий. Всероссийская научно-техническая конференция: Тезисы докладов. - Тула: Изд-во ТулГУ, 2006. - 4.2. -С.86-88.

5. Гагарина Л.Г., Калинников И.С., Фоминова Н.С. Инновационные технологии интеллектуального тестирования с помощью программно-аналитического комплекса кафедры образовательного учреждения // Современное образование: инновационный потенциал «умной экономики» России. Международная научно-методическая конференция: Материалы конференции. - Томск: Изд-во ТУ СУР, 2007; - С. 142 - 143.

6. Калинников И.С., Фоминова Н.С. Теоретические аспекты построения систем интеллектуального тестирования // Микроэлектроника и информатика-2007. 14-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов; - М.:МИЭТ, 2007. - С. 147.

7. Калинников И .С., Фоминова Н.С. Теоретические подходы к разработке автоматизированных систем интеллектуального тестирования // Новые информационные технологии. XV международная студенческая школа-семинар: Тезисы докладов. -М.: МИЭМ, 2007. - С.175-176.

8. Калинников И.С., Фоминова Н.С. Архитектура систем интеллектуального тестирования // Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем. Всероссийская межвузовская научно-практическая конференция: Материалы конференции. - М.: МИЭТ,2007. -С.105.

9. Гагарина Л.Г., Калинников И.С., Фоминова Н.С. Теоретические основы и принципы реализации интеллектуального тестирования // Информационные технологии. - М.: Новые технологии, 2008. -№8(144). - С.64-70. (ВАК)

10. Гагарина Л.Г., Калинников И .С., Фоминова Н.С. Методы разработки автоматизированных систем интеллектуального тестирования на основе когнитивных технологий // Моделирование, алгоритмизация и программирование при проектировании информационно-управляющих систем: Сборник научных трудов. -М.: МИЭТ, 2008. - С.238-243.

11. Фоминова Н.С. Применение адаптивных методов в системах автоматизированного контроля знаний // Информационные технологии в науке, проектировании и производстве. XXV всероссийская научно-техническая конференция: Тезисы докладов,-Нижний Новгород: Изд-во ННИМЦ «Диалог», 2008. - С.24-25.

12. Калинников И.С., Фоминова Н.С. Архитектура систем интеллектуального тестирования // Современное образование: вызовам времени - новые подходы. Международная научно-методическая конференция: Материалы конференции. - Томск: Изд-во ТУ СУР, 2008. - С. 133-134.

13. Фоминова Н!С. Проблемы построения систем автоматизированной оценки знаний // Современные проблемы информатизации в моделировании и социальных технологиях. XIV международная открытая научная конференция: Сб. трудов. - Воронеж: Научная книга, 2009.-С. 186-189.

14. Фоминова Н.С. Методы оценки знаний. Интеллектуальное тестирование // Современные информационные технологии в образовании: Южный федеральный округ. Научно-методическая

конференция: Материалы конференции. - Ростов-на-Дону: Изд-во ЮГ'ИНФО, 2009. - С.333-334.

15. ФоминоваН.С. Вероятностная модель процесса тестирования // Информационные технологии в профессиональной деятельности и научной работе. Всероссийская научно-практическая конференция с международным участием: Материалы конференции. - Йошкар-Ола: Изд-во Марийский государственный технический университет, 2009.-4.1.-С.78-83.

16. ФоминоваН.С. Модели адаптивного тестирования. ПАК ИТ «Logos» // Тестирование в сфере образования: проблемы и перспективы развития. II всероссийская научно-практическая конференция с международным участием: Материалы конференции. - Красноярск: Изд-во СибГТУ, 2009. - С. 209 - 217.

17. ФоминоваН.С. Адаптивное тестирование. Вероятностная и интерполяционная модели // Гибридный интеллект. Международная научно-практическая конференция: Материалы конференции. — Воронеж: Изд-во ВИЭСУ, 2009. - С. 205-208.

18. Калинников И.С., Фоминова Н.С., Нестерова С.С. Проектирование систем динамического тестирования. Задача наискорейшего поиска ошибки // Инновации в науке и образовании - 2009. VII Юбилейная международная научная конференция: Материалы конференции. — Калининград: Изд-во КГТУ, 2009. - 4.2. - С.164-167.

19. Калинников И.С., Фоминова Н.С., Нестерова С.С. Проектирование систем динамического- тестирования. Задача наилучшей аппроксимации отображения // Инновации в науке и образовании — 2009. VII Юбилейная международная научная конференция: Материалы конференции. - Калининград: Изд-во КГТУ, 2009. - 4.2. -С.160-163.

20. ФоминоваН.С., Калинников И.С., Нестерова С.С. Некоторые принципы проектирования систем автоматизированного тестирования // Оборонный комплекс - научно-техническому прогрессу России: Межотр. науч.-техн. журнал. - М.: ФГУП «ВИМИ», 2009. - №4. - С.105-118.

21. Фоминова Н.С. Адаптивные системы. Задача наискорейшего поиска ошибки // Актуальные проблемы современной науки. - М.: Спутник+, 2009. - №6 (50). - С.191-192.

Подписано в печать:

Формат 60x84 1/16 Уч.-изд.л. 1,3

Тираж 100 экз. Заказ № ¿0

Отпечатано в типографии ИПК МИЭТ

124498, Москва, Зеленоград, проезд 4806, д.5, МИЭТ

Введение.

Глава 1 Анализ подходов к тестированию и контролю в различных предметных областях.

1.1 Адаптивные системы управления и адаптивные системы тестирования.

1.2 Тестирование технических устройств.

1.3 Тестирование программного обеспечения.

1.4 Тестовые технологии в образовательной деятельности.

1.5 Постановка задачи тестирования.

Выводы по главе 1.

Глава 2 Формализация процесса тестирования. Стохастическая модель.

2.1. Задача наискорейшего поиска ошибки. Дискретный случай.

2.1.1 Одно критериальная модель тестирования.

2.1.2 Анализ однокритериальной модели тестирования при отклонении от оптимального выбора тестовых запросов.

2.1.3 Результаты численных экспериментов на случайных деревьях для однокритериальной модели.

2.1.4 Многокритериальная модель тестирования.

2.1.5 Численное моделирование тестирования на основе многокритериальной модели.

2.2 Обоснование независимости метода выбора тестовых запросов от дискретности или непрерывности входных / выходных параметров.

2.3 Задача наискорейшего поиска ошибки. Непрерывный случай.

2.4 Анализ задачи наискорейшего поиска ошибки в дискретном случае для систем с памятью.

Выводы по главе 2.

Глава 3 Формализация процесса тестирования. Аппроксимационная модель.

3.1 Задача определения наилучшего приближения. Дискретный случай.

3.1.1 Постановка задачи наилучшего приближения.

3.1.2 Численный эксперимент по приближению на графах.

3.2 Задача определения наилучшего приближения. Непрерывный случай.

3.2.1 Интерполяция функции вероятности ошибки по Лагранжу и Эрмиту.

3.2.2 Результаты сравнения остатков интерполяции.

Выводы по главе 3.

Глава 4 Практическая реализация и анализ результатов.

4.1 Программно-аналитический комплекс интеллектуального тестирования (ПАК ИТ «Logos»).

4.1.1 Структура и основные функциональные возможности.

4.1.2 Требования к программно-аппаратным средствам.

4.2 Внедрение и апробация ПАК ИТ «Logos».

4.5 Анализ результатов тестирования с использованием ПАК ИТ «Logos».

Выводы по главе 4.

Актуальность

В настоящее время одним из основных требований, предъявляемых к создаваемым информационным системам, программному обеспечению, техническим объектам, является надежность (отказоустойчивость), т.е. способность объекта сохранять свою функциональность под влиянием широкого спектра воздействий. Тестирование является одним из основных этапов проектирования и разработки. С ростом сложности систем растут расходы на их тестирование, которые в результате могут превышать прочие производственные затраты. [38] Тестирование в таком понимании является важной частью современной науки и техники и используется, к примеру, для проверки технических устройств на корректность функционирования при проектировании и изготовлении; проверки параметров любых конструкций, устройств и программ на соответствие нормам при сдаче проектов; тестирования способностей, знаний, состояния человека.

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

Проблема разработки методов и алгоритмов тестирования заключается в том, что разрабатываемые и исследуемые системы могут динамически изменяться, поэтому статический тест, состоящий из случайно-выбранных измерений и не имеющий динамически изменяемой структуры, не учитывает в полной мере динамику изменения системы. Таким образом, необходимо проектирование адаптивных тестов. Адаптивным тестированием назовем процесс проведения измерений, связанный с выполнением теста, одновременно с его изменением и дополнением на основе результатов измерений.

Научной проработки этой проблемы касались специалисты в области тестирования технических устройств (Яблонский С.В., Тоценко В.Г., Малышенко Ю.В., Чипулис В.П., Шаршунов С.Г., Кудрявцев В.Б., Чжен Г., Мэннинг Е., Метц Г.); тестирования программного обеспечения (Майерс Г.,

Тамре JI., Бейзер Б., Дастии Э., Рэшка Д., Пол Д., Калбертсон Р., Браун К., Кобб Г., ФолкД., НгуенЕ.К., Канер С. Винниченко И.В., ЛипаевВ.В., Коликова Т.В., Котляров В.П., Кларк Э.М.); контроля знаний, разработки педагогических тестов и автоматизированных систем контроля знаний (Майоров А.Н., Аванесов B.C., Нейман Ю.М., Хлебников В.А., Рудинский И.Д., Симанков B.C., Луценко Е.В., Лаптев В.Н., Соловов А.В.). Существуют публикации в периодической печати, материалы научно-практических конференций и семинаров, посвященные проблеме тестирвоания в отдельных предметных областях, однако единой концепции тестирования не существует.

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

Объект и предмет исследования

Объектом исследования являются системы тестирования. Предмет исследования и разработки - модели и алгоритмы адаптивного тестирования систем в заданных условиях.

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

Цель и задачи исследования

Целью работы является разработка моделей и алгоритмов адаптивного тестирования и программная реализация системы интеллектуального тестирования на основе разработанных алгоритмов.

Для достижения поставленной цели в работе решены следующие задачи:

- анализ современных подходов к тестированию в различных предметных областях;

- разработка стохастической и аппроксимационной моделей адаптивного тестирования;

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

- верификация алгоритмов в инструментальных средах математического моделирования;

- разработка и опытная эксплуатация программно-аналитического комплекса интеллектуального тестирования (ПАК ИТ) на основе предложенных алгоритмов.

Методы исследования

Для решения задач использована теория адаптивного управления, теоретико-графовые и теоретико-вероятностные методы, аппроксимационные методы вычислительной математики, методы матричного анализа и математической статистики. Теоретические положения подтверждены результатами моделирования в инструментальных средах математического моделирования.

При создании ПАК ИТ использованы методы модульного программирования. г

Научная новизна

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

1. На основе проведенного анализа подходов к тестированию определены критерии адаптивного тестирования и требования к математической модели.

2. Предложена стохастическая модель адаптивного тестирования для решения задачи наискорейшего поиска ошибки.

3. Предложена аппроксимационная модель адаптивного тестирования для определения наилучшего приближения.

4. Доказано, что метод выбора последовательности запросов при тестировании не зависит от непрерывности или дискретности входных/выходных параметров.

5. Разработаны алгоритмы адаптивного тестирования на основе стохастической и аппроксимационной моделей тестирования для задачи наискорейшего поиска ошибки и определения наилучшего приближения.

6. Осуществлена программная реализация алгоритмов адаптивного тестирования в виде программно-аналитического комплекса интеллектуального тестирования. Получено свидетельство об официальной регистрации программы для ЭВМ №2007611826 «Программно-аналитический комплекс интеллектуального тестирования «Logos» (ПАК ИТ «Logos»)».

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

Самостоятельное практическое значение имеют:

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

- алгоритмы адаптивного тестирования на основе разработанных моделей;

- программная реализация алгоритмов адаптивного тестирования в учебном процессе.

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

Достоверность полученных результатов

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

Личный вклад автора

Основные результаты диссертационной работы получены автором лично.

1. Исследованы современные подходы к тестированию, определены критерии адаптивного тестирования и требования к математической модели.

2. Разработаны стохастическая и аппроксимационная модели и алгоритмы адаптивного тестирования для задач наискорейшего поиска ошибки и определения наилучшего приближения соответственно.

3. Проведена верификация алгоритмов в существующих инструментальных средах математического моделирования.

4. Осуществлена программная реализация разработанных алгоритмов, разработка и внедрение программно-аналитического комплекса интеллектуального тестирования.

Реализация и внедрение результатов работы

Диссертационная работа выполнялась в соответствии с планом научно-технических исследований кафедры ИПОВС МИЭТ и является составной частью следующих научно-исследовательских работ, проводимых в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы:

- «Разработка моделей и алгоритмов тестирования знаний с динамической логической структурой»;

- «Исследование интеллектуальных алгоритмов определения уровня усвоения учебного материала и разработка концептуальных теоретических основ построения интегрированных систем адаптивного тестирования».

Разработанный в рамках исследования ПАК ИТ «Logos» отмечен медалью на Всероссийской выставке научно-технического творчества молодежи «НТТМ-2007» (г. Москва, ВВЦ, 27.06.07) и внедрен в ФГОУ ВПО «Калининградский государственный технический университет» для автоматизированного контроля знаний. Разработанные модели и алгоритмы внедрены в ОАО «ПроРескСервис» для тестирования программного обеспечения интегрированной информационной системы «Mercury-GT». Результаты диссертационной работы используются также в учебном процессе кафедры ИПОВС МИЭТ в курсах «Интеллектуальные информационные системы», «Компьютерные технологии в науке и образовании», «Системный анализ и моделирование процессов и систем». Внедрение подтверждено актами.

На защиту выносятся следующие положения:

1. Использование стохастической модели адаптивного тестирования позволяет сформировать обоснованный критерий выбора тестовых запросов для задачи наискорейшего поиска ошибки.

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

3. Разработанные алгоритмы на основе предложенных моделей адаптивного тестирования позволяют реализовать выбор запросов по сформированным критериям, что позволяет учитывать динамические свойства тестируемой системы. s

4. Применение алгоритмов позволяет увеличить быстродействие поиска ошибки более чем в 2 раза; увеличить точность приближения при фиксированном количестве запросов на 3 - 58 % в зависимости от их количества; уменьшить количество тестовых запросов при фиксированной точности тестирования в среднем на 20%.

5. Программная реализация разработанных алгоритмов может быть использована в интеллектуальных системах контроля знаний.

Апробация работы

Основные положения, выводы и предложения, сформулированные в диссертации, были представлены на 15 научных конференциях:

1. Всероссийский молодежный научно-инновационный конкурс-конференция «Электроника-2006», Москва, МИЭТ, 2006.

2. Всероссийская научно-техническая конференция «Приоритетные направления развития науки и технологий», Тула, ТулГУ, 2006.

3. Международная научно-методическая конференция «Современное образование: инновационный потенциал «умной экономики России», Томск, ТУСУР, 2007.

4. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2007», Москва, МИЭТ, 2007.

5. XI Международная студенческая школа-семинар «Новые информационные технологии», Украина, АР Крым, Судак, 2007.

6. Всероссийская межвузовская научно-практическая конференция «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем», Москва, МИЭТ, 2007.

7. Международная научно-практическая конференция по современным проблемам прикладной информатике (СППИ-3) на базе Санкт-Петербургского государственного инженерно-экономического университета «ИНЖЭКОН» (СПбГИЭУ), Санкт-Петербург, 2007.

8. Международная научно-методическая конференция «Современное образование: вызовам времени - новые подходы», Томск, ТУСУР, 2008.

9. XXV Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», Нижний Новгород: Нижегородский научный и информационно-методический центр «Диалог» (ННИМЦ «Диалог»), 2008.

10. XIV Международная открытая научная конференция «Современные проблемы информатизации в моделировании и социальных технологиях», Воронеж, 2009.

11. Научно-методическая конференция «Современные информационные технологии в образовании: Южный федеральный округ», Ростов-на-Дону, Южный федеральный университет, 2009.

12. Всероссийская научно-практическая конференция с международным участием «Информационные технологии в профессиональной деятельности и научной работе», Йошкар-Ола, Марийский государственный технический университет, 2009.

13. II Всероссийская научно-практическая конференция с международным участием «Тестирование в сфере образования: проблемы и перспективы развития», Красноярск, СибГТУ, 2009.

14. Международная научно-практическая конференция «Гибридный интеллект», Воронеж, ВорГТУ, 2009.

15. VII Международная научная конференция «Инновации в науке и образовании - 2009», Калининград, КТГУ, 2009 г.

Публикации

По теме диссертации опубликовано 20 печатных работ, в том числе 5 статей (одна в журнале, рекомендованном ВАК), 15 тезисов и докладов. Без соавторов опубликовано 7 работ.

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы из 110 наименований и четырех приложений. Работа включает 119 страниц основного текста, 59 рисунков, 3 таблицы, 69 страниц приложений. Приложения содержат акты о внедрении и использовании результатов, копию свидетельства о регистрации, листинги программ.

Выводы по главе 4

В четвертой главе описаны:

1. Функционал и структура ПАК ИТ «Logos», разработанного с применением алгоритмов, полученных в результате исследования.

2. Минимальные и рекомендуемые характеристики программно-аппаратных средств для установки ПАК ИТ «Logos».

3. Внедрение, апробация, а также результаты тестирования с использованием ПАК ИТ «Logos».

Заключение

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

1. Предложена стохастическая модель адаптивного тестирования для задачи наискорейшего поиска ошибки.

2. Разработана аппроксимационная модель адаптивного тестирования для определения наилучшего приближения.

3. Получен алгоритм адаптивного тестирования на основе стохастической модели для задачи наискорейшего поиска ошибки.

4. Получен алгоритм адаптивного тестирования на основе аппроксимационной модели для определения наилучшего приближения.

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

6. Обоснована связь между дискретным и непрерывным случаями, т.е. доказано, что метод выбора последовательности запросов при тестировании не зависит от непрерывности или дискретности входных/выходных параметров.

7. Разработанные алгоритмы адаптивного тестирования обеспечивают:

- увеличение быстродействия поиска ошибки (задача наискорейшего поиска ошибки) более чем в 2 раза;

- увеличение точности приближения при фиксированном количестве запросов (задача определения наилучшего приближения) на 3 - 58 % в зависимости от количества тестовых запросов;

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

8. Разработан и внедрен программно-аналитический комплекс интеллектуального тестирования (ПАК ИТ «Logos»), опытная эксплуатация которого доказывает повышение эффективности тестирования обучаемых в среднем на 12%.

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

1. Абдеев, Р.Ф. Философия информационной цивилизации / Р.Ф. Абдеев. -М.: ВЛАДОС, 1994.- 336 с

2. Аванесов, B.C. Композиция тестовых заданий / B.C. Аванесов. М.: Центр тестирования, 2002. - 237 с.

3. Аванесов, B.C. Теория и методика педагогических измерений Электронный ресурс. / В.С.Аванесов. Режим доступа: http://testolog.narod.ru/Theory.html. -Загл. с экрана.

4. Аванесов, B.C. Тесты в социологическом исследовании / B.C. Аванесов. — М.:Наука, 1982,- 199с.

5. Андреев, В.И. Педагогика: учебный курс для творческого саморазвития / В.И. Андреев. 2-е изд. - КазаныЦентр инновационных технологий, 2000. -608 с.

6. Бахвалов, Н.С. Численные методы / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. М.: БИНОМ. Лаб.знаний, 2003. - 632 с.

7. Бейзер, Б. Тестирование черного ящика. Технологии функционального тестирования программного обеспечения и систем / Б. Бейзер. СПб.: Издательский дом "ПИТЕР", 2004. 320 с.

8. Бесекерский, В.А. Теория систем автоматического управления / В.А. Бесекерский, Е.П. Попов. СПб: Профессия, 2003. - 751с.

9. Беспалько, В.П. Педагогический анализ некоторых популярных тестовых систем / В.П. Беспалько// Школьные технологии. 2006. - №3.-С.126-140.

10. Бурдонов, И.Б. Теория конформности для функционального тестирования программных систем на основе формальных моделей : дис. док.физ.-мат.наук: 05.13.11 / Бурдонов Игорь Борисович; Место защиты: Ин-т систем, программирования.- Москва, 2008.- 596 с.

11. Бусленко, Н.П. Моделирование сложных систем / Н.П. Бусленко. -М.: Наука, 1968. 356 с.

12. Вендровская, Р.Б. Тесты в американской системе образования / Р.Б.Вендровская // Педагогика. 2001. - №2.-С. 96-102.

13. Винниченко, И.В. Автоматизация процессов тестирования / И.В. Винниченко. СПб.: Питер, 2005. - 203 с.

14. Гагарина, Л.Г. Применение сетевых технологий в обучении дисциплине «Информатика» / Л.Г. Гагарина, Е.Б. Кемарская, Н.С. Фоминова // Профессиональный учебник. М.: ЮНИТИ-ДАНА, 2006. - №4(10). - С.32-33.

15. Гагарина, Л.Г. Теоретические основы и принципы реализации интеллектуального тестирования / Л.Г. Гагарина, И.С. Калинников, Н.С. Фоминова // Информационные технологии. М.: Новые технологии, 2008. - №8(144). - С.64-70.

16. Глова, В.И. Модели педагогического тестирования обучаемых / В.И. Глова, С.В. Дуплик // Вестник КТГУ им.А.Н.Туполева. 2003. - №2. - С.74-79.

17. Гмурман, В.Е. Теория вероятностей и математическая статистика / В.Е. Гмурман. М.: Высш.шк., 2003. - 479 с.

18. Городецкий, А.Я. Информационные системы. Вероятностные модели и статистические решения. Учеб. пособие / А.Я. Городецкий. СПб.: Изд-во СПбГПУ, 2003. - 326 с.

19. Горюшкин, Е.И. Использование нейросетевых технологий в адаптивном тестировании по информатике в вузе: автореф. дис. . канд. пед. наук. -Москва, 2009. 23 с.

20. Гостомыслов, JI. Тестирование:плюсы и минусы / Л.Гостомыслов // Высшее образование в России. 2001. - №3. - С. 152-154.

21. Грубер, Е. Словарь иностранных слов в русском языке для школьников и студентов: более 9 тыс. слов / Е.Грубер. М.: Локид-Пресс, 2005. - 654 с.

22. Гусак, А.А. Теория вероятностей. Справочное пособие к решению задач / А.А. Гусак, Е.А. Бричкова. Мн.: ТетраСистемс. - 2002. - 288 с.

23. Гутник, Г.В. Качество образования как системообразующий фактор региональной образовательной политики / Г.В.Гутник // Стандарты и мониторинг в образовании. — 1999. №3. - С.28-34.

24. Давыдов, Д.А. Проектирование систем адаптивного тестового контроля • / Д.А. Давыдов, Р.Г. Шарафиев // Педагогический журнал Башкортостана. -2006.-№2.-С. 39-59.

25. Дастин, Э. Автоматизированное тестирование программного обеспечения. Внедрение управление и эксплуатация / Э. Дастин, Д.Рэшка, Д. Пол; пер. Е. Молодцовой, М. Павлова. М.: ЛОРИ, 2003. - 567 с.

26. Деревицкий, Д.П. Прикладная теория дискретных адаптивных систем управления / Д.П. Деревицкий, А.Л. Фрадков. М.: Наука, 1981. - 216 с.

27. Долинер, Л.И. Адаптивные методические системы как основа обучения в условиях использования информационных коммуникапционных технологий

28. Электронный ресурс. / Л.И. Долинер // Конф. ИТО-2002. Режим доступа: http://ito.edu.ru/2002fl/l/I-l-405.html. - Загл. с экрана.

29. Дружинин, В.Н. Экспериментальная психология / В.Н. Дружинин. -СПб. Литер, 2000. 320 с.

30. Ельцын, А.В. TestGen система формирования испытательных материалов /

31. A.В. Ельцын, В.Ж. Куклин, А.С.Масленников. Йошкар-Ола, 1995. - 75 с.

32. Зельнер, А. Байесовские методы в эконометрии / А. Зельнер; пер. с англ. Г.Г. Пирогова и Ю.П. Федоровского. М.: Статистика, 1980. - 438 с.

33. Зыбин, Р.С. Автоматизация массового создания тестов работоспособности / Р.С. Зыбин, В.В, Кулямин, А.В. Пономаренко, В.В. Рубанов, Е.С. Чернов // Программирование. 2008.-№ 34(6). - С. 64-80.

34. Иванников, В.П. Применение технологии UniTesK для функционального тестирования моделей аппататного обеспечения Электронный ресурс. /

35. B.П. Иванников, А.С. Камкин, В.В, Кулямин, А.К. Петренко // Препринт ИСП РАН. Москва, 2005. - Режим доступа: http://www.citforum.ru/SE/testing/uniteskhard/ . - Загл. с экрана.

36. Испытания радиоэлектронной, электронно-вычислительной аппаратуры и испытательное оборудование: учеб. пособие для вузов/ А. И. Коробов и др..- М.: Радио и связь, 1987. — 272 с.

37. Ительсон, Л.Б. Математические методы в педагогике и педагогической психологии: автореф. дис. . докт. псих. наук. Электронный ресурс. 1965.- Режим доступа: http://www.childpsy.ru/dissertations/id/18618.php. Загл. с экрана.

38. Калбертсон, Р. Быстрое тестирование / Р. Калбертсон, К. Браун, Г. Кобб. -М.:Издательский дом «Вильяме», 2002.- 384 с.

39. Карнер, С. Тестирование программного обеспечения. Фундаментальные концепции менеджмента бизнес-приложений / С. Карнер, Д. Фолк, Е.К. Нгуен; пер. с англ. Киев: "ДиаСофт", 2001. -544 с.

40. Клайн, П. Справочное руководство по конструированию тестов / П. Клайн. -Киев: ПАН Лтд, 1994. 288 с.

41. Кларк, Э.М. Верификация моделей программ: Model Checking / Э.М. Кларк, О.Грамберг, Д. Пелед; пер. с англ. / под ред. Р.Смелянского. М.: МЦНМО, 2002.-416 с.

42. Климов, В.Г. Методика контроля знаний обучаемых с использованием электронных тестирующих систем Электронный ресурс. / В.Г. Климов // Конф. ИТО-Троицк 2005. - Режим доступа: http://ito.edu.ru/2005/Troitsk/4/4-0-4.html. - Загл. с экрана.

43. Колмогоров, А.Н. Введение в теорию вероятностей / А.Н. Колмогоров, И.Г. Журбенко, А.В. Прохоров. М.: Наука. - 1982. - 160 с.

44. Крайтор, Д.В. Инструментальный комплекс программ для создания обучающих систем на основе интеграции адаптивных технологий Электронный ресурс. / Д.В. Крайтор // Конф. ИТО-2002. Режим доступа: http://ito.edu.ru/2002AI/4/II-4-220.html. - Загл. с экрана.

45. Красильникова, В.А. Подготовка заданий для компьютерного тестирования: Методические рекомендации / В.А. Красильникова. Оренбург: ИПК ГОУ ОГУ, 2004.-31 с.

46. Ксмензова, Г.Ю. Оценочная деятельность педагога / Г.Ю. Ксензова. -М.: Педагогическое общество России, 1999. 121 с.

47. Кудрявцев, В.Б. Теория тестирования логических устройств /

48. B.Б. Кудрявцев, Э.Э. Гасанов, О.А. Долотова, Г.Р. Погосян; под.ред. В .А. Садовничего. М.: ФИЗМАТЛИТ, 2006. - 160 с.

49. Курейчик, В.М. Поисковая адаптация: теория и практика / В.М. Курейчик, Б .К. Лебедев, О.Б. Лебедев. М.:ФИЗМАТЛИТ, 2006. - 272 с.

50. Липаев, В.В. Тестирование программ / В.В. Липаев. М.: Радио и связь, 1986. - 296 с.

51. Липаев, В.В. Надежность программных средств / В.В. Липаев. М.: СИНТЕГ, 1998. - 232 с.

52. Литвак, Б.Г. Экспертная информация: Методы получения и анализа / Б .Г. Литвак. М.: Радио и связь, 1982. - 184 с.

53. Лукашин, Ю.П. Адаптивные методы краткосрочного прогнозирования временных рядов: Учеб. пособие / Ю.П. Лукашин. М.: Финансы и статистика, 2003. - 416 с.

54. Майерс, Г. Искусство тестирования программ / Г. Майерс; пер. с англ. под ред. Б.А. Позина. М.: Финансы и статистика, 1982. - 176 с.

55. Майерс, Г. Надежность программного обеспечения / Г. Майерс; пер. с англ. Ю.Ю. Галимов под ред. В.Ш. Кауфмана. -М.:МИР, 1980. 360 с.

56. Майоров, А.Н. Теория и практика создания тестов для системы образования / А.Н. Майоров. М.: Интеллект-центр, 2002. - 300с.

57. Макаренко, А.С. Педагогическая поэма / А.С. Макаренко. СПб.:Азбука. -2009.-416 с.

58. Малышенко, Ю.В. Автоматизация диагностирования электронных устройств / Ю.В. Малышенко, В.П. Чипулис, С.Г. Шаршунов. М.: Энергоатомиздат, 1986.-216 с.

59. Матросов, А.Ю. Алгоритмические методы синтеза тестов / А.Ю. Матросов. — Томск:Изд-во Томского университета, 1990. 270 с.

60. Моррис, У.Т. Наука об управлении. Байесовский подход /У.Т. Моррис; пер. с англ. О.В. Редькиной; под. ред. И.Ф. Шахнова. М.: МИР, 1971. - 304 с.

61. Огарков, С.Ю. Диагностика электромеханических систем: текст лекций /

62. C.Ю. Огарков, А.В. Соколов. Челябинск: Изд-во ЮУрГУ, 2003. - 55 с.

63. Прокофьева, Н.О. Модели и методы адаптивного контроля знаний / Н.О. Прокофьева, JI.B. Зайцева // Educational Technology & Society. 2004. -№7(4). - С. 265 - 277.

64. Протасов, А.С. Создание интеллектуальных средств адаптивного тестирования Электронный ресурс. / А.С. Протасов // Конф. ИТО 2003. -Режим доступа: http://ito.edu.ru/2003/VII/VII-0-2057.html. - Загл. с экрана.

65. Разработка моделей и алгоритмов тестирования знаний с динамической логической структурой Текст. : отчет о НИР (промежуточн.) : МИЭТ; рук. Фоминова Н.С. — М., 2009. 81 с. -Библиогр.: с.62-65. - № ГР 01200960485.

66. Растригин, JI.A. Адаптивное обучение с моделью обучаемого / JI.A. Растригин, М.Х. Эренштейн. Рига: Зинатне, 1988. - 160 с.

67. Резников, А.П. Предсказание естественных процессов обучающейся системой (физические, информационные, методологические аспекты) / А.П. Резников. Новосибирск: Наука, 1982. - 287 с.

68. Рудинский, И.Д. Принципы интеллектуального автоматизированного тестирования знаний Электронный ресурс. / И.Д. Рудинский // Конф. ИТО-2001. Режим доступа: http://www.ito.su/2001/ito/VI/VI-0-16.html. - Загл. с экрана.

69. Семенов, В.А. Управление познавательными поступками учеников на их персональных маршрутах в пространстве дидактических событий (из опыта работы) / В.А. Семенов // Школьные технологии. 1996. - №6. - С.69-70.

70. Сербии, В.В. Информационно-обучающая система на основе многокритериальной модели принятия решений: автореф. дис. . канд. тех. наук. Республика Казахстан, Усть-Каменогорск, 2009. - 23 с.

71. Сербии, В.В. Реализация адаптивных тестовых систем (адаптивные обучающие интеллектуальные и контролирующие системы объективной оценки знаний): Учебно-методическое пособие / В.В. Сербии. Алматы: РУМЦДО, 2006.

72. Симанков, B.C. Системный анализ в адаптивном управлении: Монография (научное издание) / B.C. Симанков, Е.В. Луценко, В.Н. Лаптев. Краснодар:

73. Ин-т совр. технол. и экон., 2001. 258 с.

74. Соммервил, И. Инженерия программного обеспечения / И. Соммервил; пер. с англ. М.: Издательский дом "Вильяме", 2002. - 624 с.

75. Стефанюк, В.Л. Локальная организация интеллектуальных систем / В.Л. Стефанюк. М.: ФИЗМАТЛИТ, 2004. - 328 с.

76. Тамре, Л. Введение в тестирование программного обеспечения / Л. Тамре; пер. с англ. М.:Издательский дом «Вильяме», 2003. - 368с.

77. Тоценко, В.Г. Алгоритмы технического диагностирования дискретных устройств / В.Г. Тоценко. М.: Радио и связь, 1985. - 240 с.

78. Турчак, Л.И. Основы численных методов: Учеб. Пособие / Л.И. Турчак, П.В. Плотников. М.: ФИЗМАТЛИТ, 2003. - 304 с.

79. Уткин, Л.В. Анализ риска и принятие решений при неполной информации / Л.В. Уткин. СПб.: Наука. - 2007. - 404 с.

80. Фихтенгольц, Г.М. Курс дифференциального и интегрального исчисления / Г.М. Фихтенгольц. М.: Наука, 1962. - Т.1. - 608 с.

81. Фоминова, Н.С. Адаптивное тестирование. Вероятностная и интерполяционная модели / Н.С. Фоминова // Гибридный интеллект. Международная научно-практическая конференция: Материалы конференции. Воронеж: Изд-во ВИЭСУ, 2009. - С. 205-208.

82. Фоминова, Н.С. Адаптивные системы. Задача наискорейшего поиска ошибки / Н.С. Фоминова // Актуальные проблемы современной науки. М.: Спутник+, 2009. - №6 (50). - С. 191-192.

83. Харари, Ф. Теория графов / Ф. Харари; пер. с англ. и предисл. В.П. Козырева; под ред. Г.П. Гаврилова. М.:Едиториал УРСС, 2003. - 296 с.

84. Хей, Дж. Введение в методы байесовского статистического вывода / Дж. Хей; пер. с англ. А.А. Рывкина. М.: Финансы и статистика, 1987. - 335 с.

85. Цыпкин, Я.З. Адаптация и обучение в автоматических системах / Я.З. Цыпкин. М.: Наука, 1968. -400с.

86. Цыпкин, Я.З. Информационная теория идентификации / Я.З. Цыпкин. М.: Наука, Физматлит, 1995. - 336с.

87. Челышкова, М.Б. Разработка педагогических тестов на основе современных математических моделей: Учеб.пособие / М.Б. Челышкова. М.: Исследовательский центр проблем качества подготовки специалистов, 1995. -33 с.

88. Чжен, Г. Диагностика отказов цифровых вычислительных систем / Г. Чжен, Е. Мэннинг, Г. Метц; пер. с англ. под ред. канд. техн. наук И.Б. Михайлова. -М.: МИР, 1972.-232 с.

89. Эйкхов, П. Основы идентификации систем управления. Оценивание параметров и состояния / П. Эйкхов; пер. с англ. В.А. Потоцкого и А.С. Манделя; под ред. Н.С. Райбмана. М.: МИР, 1975. - 680 с.

90. Яблонский, С.В. Элементы математической кибернетики / С.В. Яблонский. -М.: Высшая школа, 2007. 188 с.

91. Beizer, В. Software Testing Techniques / В. Beizer. Van Nostrand Reinholds, NY, 1990. - 549 pp.

92. Farchi, E. Using a model-based test generator to test for standard conformance / E. Farchi, A. Hartman, S. S. Pinter // IBM Systems Journal. 2002. - volume 41. -pp. 89-110.

93. Frederiksen, N. Test theory for a new generations of tests / N. Frederiksen, R.J. Mislevy, I. J. Bejar (Eds). Lawrence Erlbaum Ass. Publ. 1993, Hillsdale, N-J, 404 pp.

94. Leintz, B.P. Software maintenance management / B.P. Leintz, E.B. Swanson/ -Addison-Wesley, 1980. 160 pp.

95. Myers, GJ. The art of software testing / G.J. Myers. Publ. 2004, John Wiley & Sons, Inc., Hoboken, New Jersey. - 234 pp.

96. Rasch, G. Probabilistic Models for Some Intelligence and Attainment Tests / G. Rasch; with a Foreword and Afteword by B.D. Wright. The Univ. of Chicago Press, Chicago & London, 1980. - 199 pp.

97. Schach, S. Software engineering with Java / S. Schach. McGraw-Hill, 1996. -640pp.

98. Weinberg, G. Kill that code! / G. Weinberg // Infosystems. 1983. - pp.48-49.