Первый мой топик на Хабре будет посвящен моим научным исследованиям, которые связаны с методами построения алгоритмов генерации тестовых заданий для организации контроля знаний обучаемых.
Не секрет, что обеспечение тестирования многовариантными тестовыми заданиями позволяет снизить эффект списывания среди обучаемых. Автоматизация получения многовариантных заданий ложится на плечи того или иного алгоритма, заложенного в программном генераторе. Литература, описывающая методы генерации задач, не поддается счету, но ни один метод не претендует на некую универсальность, а предназначен для построения генератора либо конкретного задания либо определенного класса задач.
Использование языков программирования для описания алгоритмов генерации не поддается критике и имеет ряд преимуществ относительно имеющихся методов, так как программный код и возможности применяемого языка позволяют описывать задания для широкого класса дисциплин. Единственный недостаток — отсутствие навыков программирования у большинства преподавателей, особенно, у гуманитариев.
В данной статье в качестве метода описания алгоритмов генерации используется подход генерации комбинаторных множеств на основе дерева И/ИЛИ, а также попытка его формализации в виде программного языка. Я попытаюсь доказать, что использование данного метода позволит описывать генераторы задач для различного класса дисциплин (технические, гуманитарные и др.) и для различных форм проведения тестирования…
Деревом И/ИЛИ будем называть дерево, состоящее из узлов 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# реализованы поверх общей системы типов .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.
|
Вариант 2.
|
В данной статье в качестве метода описания алгоритмов генерации используется подход генерации комбинаторных множеств на основе дерева И/ИЛИ, а также попытка его формализации в виде программного языка. Я попытаюсь доказать, что использование данного метода позволит описывать генераторы задач для различного класса дисциплин (технические, гуманитарные и др.) и для различных форм проведения тестирования…
Понятие дерева И/ИЛИ
Деревом И/ИЛИ будем называть дерево, состоящее из узлов 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
Заключение
Дальнейшее развитие данного метода позволило описывать задания различного диапазона дисциплин, формировать блоки решений, ответов, подсказок и т.д. (в зависимости от требований, которые выдвигает форма проведения тестирования). На основе данного метода реализован «облачный» сервис разработки генераторов тестовых заданий. Причем, для построения алгоритмов генерации не требуется знание синтаксиса, — разработка генератора ведется с применением визуальных компонентов прямо на Веб-странице.
В процессе написания статьи использовались мои научные статьи.
Если топик был интересен, напишу дальнейшее развитие проекта и представлю систему разработки многовариантных тестовых заданий, реализованную в рамках открытого Интернет приложения.
Список используемых источников
- Кручинин В.В. Использование деревьев И/ИЛИ для генерации вопросов и задач // Вестник Томского государственного университета. 2004. №284. С. 183 – 186.
- Зорин Ю.А. Интерпретатор языка построения генераторов тестовых заданий на основе деревьев И/ИЛИ // Доклады Томского государственного университета систем управления и радиоэлектроники. 2013. №1. С. 75 – 79.
- Зорин Ю.А. Использование алгоритмов комбинаторной генерации при построении генераторов тестовых заданий // Дистанционное и виртуальное обучение. 2013. №6. С. 54 – 59.
