Метод генерации тестовых заданий на основе деревьев И/ИЛИ и его программная реализация

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

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

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



    Пример многовариантного задания
    Вариант 1.
    1. Аня купила проездной билет на месяц и сделала за месяц только 29 поездок. Сколько рублей она переплатила, если проездной билет стоит на месяц стоит 650 рублей, а разовая поездка — 20 руб.?
    2. Найдите корень уравнения -14х-5=42-6х.
    3. Из 870 деталей на складе 52 оказались бракованными. Какова вероятность взять бракованную деталь? Ответ указать с точностью 0,01.

    Вариант 2.
    1. Света приобрела проездной билет на год и сделала в течение 30 недель только 50 поездок. Сколько рублей она переплатила, если проездной билет на год стоит 6650 рублей, а разовая поездка — 20 руб.?
    2. Найдите корень уравнения 4х+10=58+9х.
    3. Из 400 деталей на складе 12 оказались бракованными. Какова вероятность взять исправную деталь? Ответ указать с точностью 0,1.


    В данной статье в качестве метода описания алгоритмов генерации используется подход генерации комбинаторных множеств на основе дерева И/ИЛИ, а также попытка его формализации в виде программного языка. Я попытаюсь доказать, что использование данного метода позволит описывать генераторы задач для различного класса дисциплин (технические, гуманитарные и др.) и для различных форм проведения тестирования…

    Понятие дерева И/ИЛИ


    Деревом И/ИЛИ будем называть дерево, состоящее из узлов 2-х типов: И-узел и ИЛИ-узел. На рисунке ниже изображено схематическое представление узлов дерева И/ИЛИ.



    Вариантом дерева И/ИЛИ называется дерево, полученное из данного путём отсечения всех дуг, кроме одной, у ИЛИ-узлов. Корнем варианта будет корень исходного дерева. На рисунке показано дерево И/ИЛИ и все его варианты.


    Мощностью дерева И/ИЛИ называется количество вариантов, которое оно содержит. Так, мощность дерева, представленного на рисунке, равна 6.

    Еще одним замечательным свойством дерева И/ИЛИ является возможность идентификации варианта (получение варианта по его номеру) [1].

    Связь дерева И/ИЛИ с тестовым заданием


    Рассмотрим принцип описания алгоритма генерации задачи в виде дерева И/ИЛИ на примере 1-й задачи из таблицы, представленной выше.

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

    Внимание! На рисунке ниже схематичное изображение узлов И/ИЛИ: узел И — с дугой, узел ИЛИ — без дуги.

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

    1.Вариант {A1, B1, C, D1, E1, F, G}
    Аня купила проездной билет на год и сделала в течение 25 дней 5 поездок. Сколько рублей она переплатила, если проездной билет стоит 2400 рублей, а разовая поездка 15 рублей?

    2.Вариант {A2, B1, C, D1, E1, F, G}
    Света купила проездной билет на год и сделала в течение 25 дней 5 поездок. Сколько рублей она переплатила, если проездной билет стоит 2400 рублей, а разовая поездка 15 рублей?

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

    Синтаксис описания дерева И/ИЛИ


    Для записи деревьев И/ИЛИ предлагается использовать скобочную нотацию: круглыми скобками обозначаются И-узлы, фигурными – ИЛИ-узлы, узлы без скобок являются листами. Узлы дерева могут быть именованными и неименованными. Именованные – это те узлы, у которых есть идентификатор, неименованные – те, у которых идентификатора нет. Идентификатор узла является атомом и может представлен двумя типами: строкой или числом. Идентификатор может состоять из любого набора символов, исключая зарезервированные символы и знак пробела.
    Рассмотренное задание в виде дерева И/ИЛИ на программном языке, выглядит следующим образом:

    Main(A{“Аня”, “Света”, “Марина”}, B {“купила”, “приобрела”}, “проездной билет”, C{“на год”, “на полгода”, “на месяц”}, D{(“и сделала в течение”,[1..28],”дней”), “и сделал в течение месяца”, “в течение недели”}, E{([15..20], “поездок”)}, F{“сколько рублей она переплатила, если проездной билет стоит”, [100,100..7000], “рублей, а разовая поездка”,[15..20],”рублей?”}))

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

    Язык F#


    Учитывая рекурсивную природу дерева И/ИЛИ я посмотрел в строну мультипарадигмального языка F#. Язык F# предоставляет полный набор инструментов функционального программирования: алгебраические типы данных, функции высшего порядка, средства для композиции функций и неизменяемые структуры данных. Все функциональные возможности F# реализованы поверх общей системы типов .NET Framework.

    Неотъемлемой частью реализации интерпретатора является лексический и синтаксический анализ введенных пользователем строк, позволяющий переводить скобочную запись деревьев И/ИЛИ в описанный тип данных дерева И/ИЛИ. Среди различных анализаторов кода, внимания заслуживает программная библиотека «Yacc», в частности, из-за того, что в своем составе содержит сразу лексический и синтаксический анализаторы и позволяет выдавать результат на языке F# (FYacc). Для описания лексического анализатора на языке F# приведена синтаксическая диаграмма дерева И/ИЛИ.

    Синтаксический анализатор на основе символьных конструкций, определенных за счет регулярных выражений, использует рекурсивный спуск при попытке приведения полученной строки к типу Tree, которое в свою очередь будет описано в размеченном объединении:

    start:
    | Prog1 { Tree($1) }
    Tree:
    | LOR Tree ROR { Or ([] @ $2)}
    | LAND Tree RAND { And ([] @ $2)}
    | NAMETREE Tree { SetNameTree($1, $2) }
    | STR { Str $1}
    | INT32 { Int $1}
    | FLOAT { Float $1}

    Размеченные объединения языка F# позволяют описать типы, учитывая рекурсивную природу деревьев И/ИЛИ, и, используя, сопоставление с образцом, сразу приступать к применению различных операций над листьями и узлами дерева. Размеченное объединение для дерева И/ИЛИ:

    type AndOrTree =
    //Узел может содержать один или несколько узлов И
    | And of AndOrTree list
    //Узел может содержать один или несколько узлов ИЛИ
    | Or of AndOrTree list
    //Листья дерева могут содержать целочисленные значения
    | Int of int
    //Листья дерева могут содержать строковые значения
    | String of string
    //Листья дерева могут содержать значения с плавающей точкой
    | Float of float
    //Узлы могут быть именованные
    | SetNameTree of string * AndOrTree
    //Узлы могут содержать имя узла, инициализованного ранее
    | GetNameTree of string * AndOrTree
    // Обозначаем корневой узел
    and Tree =
    | Tree of AndOrTree

    Заключение


    Дальнейшее развитие данного метода позволило описывать задания различного диапазона дисциплин, формировать блоки решений, ответов, подсказок и т.д. (в зависимости от требований, которые выдвигает форма проведения тестирования). На основе данного метода реализован «облачный» сервис разработки генераторов тестовых заданий. Причем, для построения алгоритмов генерации не требуется знание синтаксиса, — разработка генератора ведется с применением визуальных компонентов прямо на Веб-странице.

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

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

    Список используемых источников


    1. Кручинин В.В. Использование деревьев И/ИЛИ для генерации вопросов и задач // Вестник Томского государственного университета. 2004. №284. С. 183 – 186.
    2. Зорин Ю.А. Интерпретатор языка построения генераторов тестовых заданий на основе деревьев И/ИЛИ // Доклады Томского государственного университета систем управления и радиоэлектроники. 2013. №1. С. 75 – 79.
    3. Зорин Ю.А. Использование алгоритмов комбинаторной генерации при построении генераторов тестовых заданий // Дистанционное и виртуальное обучение. 2013. №6. С. 54 – 59.
    Поделиться публикацией

    Похожие публикации

    Комментарии 7

      0
      Теперь понятно, откуда брались схожие варианты задач на всяческих контрольных работах в школе)
        +1
        Как всегда хочется несферических примеров. Я своим студентам контрольные генерировал скриптом. Это действительно удобно и здорово. Но увы, получалось все-таки не так сказачно, как в примере с Аней-Светой-Мариной, потому что воросы касались вещей весьма конкретных, например, делегатов C#, и пространства для рандомизации вопросов фактически не получалось.

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

        И еще отдельный вопрос. Там где, например, решить уравнение. Задание я построю, ок. А решение? Ну ладно линейное уравнение, а если что-то поинтересней?
          0
          Спасибо за вопрос, следующий пост сделаю обзорной, про реализованную систему построения генераторов и ваши вопросы улетучатся, там решения, ответы, указания и т.д. все так же описывается деревом. А правильное перемешивание вопросов решается за счет правильного создания дерева каталогов, в которых размещаются генераторы.
          +1
          Здравствуйте, я хотел бы задать несколько вопросов.

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

          2. Как выбирается конкретное значение очередного узла? Случайным образом?
          Если нет, тогда интересно было бы узнать, как? И надо учитывать, что значения разных узлов могут противоречить друг другу и их надо дополнительно контролировать (пример: купила билет на месяц и за 5 недель сделала столько-то поездок).
          Если да, то что делать с таким вариантом: «Аня купила билет на месяц и сделала в течение недели 20 поездок. Сколько она переплатила, если билет стоит 300 рублей, а одна поездка — 25 рублей.»?

          И у вас везде должно быть «в течение», конечно же.
            0
            Жаль, что автор не заинтересован в том, чтобы комментировать свою статью.
            К чему тогда было постить ее на Хабр?
              0
              Извините, совсем времени не было.
              1. Одно из замечательных свойств деревьев И/ИЛИ — нумерация элементов, подсчет мощности, в литературе [1] подробно это описано, + древовидное описание понятнее смотрится на бумаге, чем массивное. В любом случае в программной реализации узлы ИЛИ являются списком (массивом).

              2. В том то и прелесть дерева И/ИЛИ, имея его мощность, например 2000 вариантов, и имея функцию получения варианта по его номеру, реализация может быть разной, либо случайным образом либо последовательно брать один за другим вариантом. Далее в дереве имеются именные узлы, условные, интервальные, функциональные. Вот именно условные могут описывать условия для параметров которые противоречат друг другу. Другими словами если не выполняется условие, то данный вариант просто пропускаем…
            0
            Почему-то вспомнился DADA engine и известный генератор.

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

            Самое читаемое