October 18, 2013 at 14:41Method for generating test tasks based on AND / OR trees and its software implementation
My first topic on Habré will be devoted to my scientific studies, which are related to the methods of constructing algorithms for generating test tasks for organizing the control of knowledge of students.
It is no secret that providing testing with multivariate test items can reduce the effect of cheating among students. Automation of multivariate tasks falls on the shoulders of an algorithm embedded in a software generator. The literature describing methods for generating tasks cannot be counted, but not a single method claims to be universal, but is intended to build a generator or a specific task or a certain class of tasks.
The use of programming languages to describe the generation algorithms is not susceptible to criticism and has several advantages relative to the available methods, since the program code and the capabilities of the language used allow us to describe tasks for a wide class of disciplines. The only drawback is the lack of programming skills for most teachers, especially for humanities.
In this article, as a method for describing generation algorithms, we use the approach of generating combinatorial sets based on the AND / OR tree, as well as an attempt to formalize it in the form of a programming language. I will try to prove that the use of this method will allow us to describe task generators for various classes of disciplines (technical, humanitarian, etc.) and for various forms of testing ...
An AND / OR tree is a tree consisting of nodes of 2 types: an I-node and an OR-node. The figure below shows a schematic representation of the nodes of the AND / OR tree.
A variant of an AND / OR tree is a tree obtained from a given one by cutting off all arcs, except one, from the OR nodes. The root of the option will be the root of the source tree. The figure shows the AND / OR tree and all its variants.
The power of an AND / OR tree is the number of options it contains. So, the power of the tree shown in the figure is 6.
Another remarkable property of the AND / OR tree is the possibility of identifying a variant (obtaining a variant by its number) [1].
Consider the principle of describing the algorithm for generating a task in the form of an AND / OR tree using the example of the 1st task from the table above.
To do this, the task text is divided into fragments. Usually fragments are divided into nodes: constants and variables. For variable nodes, sets of implementations are written, each of which represents a specific text. Then, each of the selected implementation nodes is analyzed and, if possible, are divided into variable and constant nodes.
Attention! In the figure below, a schematic illustration of AND / OR nodes: AND node - with an arc, OR node - without an arc.
Having performed the left-side bypass of the variant and writing out the corresponding nodes, we obtain a specific description of the function. For example:
1. Option {A1, B1, C, D1, E1, F, G}
Anya bought a ticket for a year and made 5 trips within 25 days. How many rubles did she overpay if the ticket costs 2400 rubles, and a single trip is 15 rubles?
2. Option {A2, B1, C, D1, E1, F, G}
Sveta bought a ticket for a year and made 5 trips within 25 days. How many rubles did she overpay if the ticket costs 2400 rubles, and a single trip is 15 rubles?
Such a representation clearly shows the structure of the whole question for the developer, however, a syntax for the description of such tree structures is necessary.
It is proposed to use bracket notation for writing AND / OR trees: parentheses denote I-nodes, curly brackets indicate OR-nodes, nodes without brackets are sheets. Tree nodes can be named and unnamed. Named ones are those nodes that have an identifier, unnamed ones are those that have no identifier. The node identifier is an atom and can be represented by two types: a string or a number. An identifier may consist of any set of characters, excluding reserved characters and a space character.
The considered task in the form of an AND / OR tree in a programming language is as follows:
Main (A {“Anya”, “Sveta”, “Marina”}, B {“bought”, “acquired”}, “ticket”, C {“for a year”, “for half a year”, “for a month”} , D {(“and did during”, [1..28], “days”), “and did during the month”, “during the week”}, E {([15..20], “trips ”)}, F {“ how many rubles did she overpay if the ticket costs ”, [100,100..7000],“ rubles, and a one-time trip ”, [15..20],“ rubles? ”})) The
further task is reduced to the implementation of the interpreter of this syntactic construction, as well as the implementation of algorithms for obtaining a variant by its number and counting the power of the tree number for this task).
Given the recursive nature of the AND / OR tree, I looked in the direction of the multiparadigmal language F #. The F # language provides a complete set of functional programming tools: algebraic data types, higher-order functions, means for composing functions, and immutable data structures. All F # functionality is implemented on top of the common .NET Framework type system.
An integral part of the implementation of the interpreter is the lexical and syntactic analysis of the lines entered by the user, which allows translating the bracket record of AND / OR trees into the described data type of the AND / OR tree. Among the various code analyzers, the Yacc program library deserves attention, in particular, due to the fact that it contains lexical and syntactic analyzers at once and allows outputting the result in F # (FYacc). To describe the lexical analyzer in the F # language, the syntax diagram of the AND / OR tree is given.
A parser based on character constructs defined by regular expressions uses a recursive descent when trying to cast the resulting string to the Tree type, which in turn will be described in a marked-up union:
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}
Labeled F # language associations allow you to describe types, taking into account the recursive nature of AND / OR trees, and, using pattern matching, immediately start applying various operations on leaves and tree nodes. Marked union for AND / OR tree:
type AndOrTree =
// A node can contain one or more nodes AND
| And of AndOrTree list
// A node may contain one or more nodes OR
| Or of AndOrTree list
// Leaves of the tree may contain integer values
| Int of int
// Leaves of the tree may contain string values
| String of string
// Leaves of the tree may contain floating point values
| Float of float
// Nodes can be named
| SetNameTree of string * AndOrTree
// Nodes may contain the name of the node initialized earlier
| GetNameTree of string * AndOrTree
// Denote the root node
and Tree =
| Tree of AndOrTree
Further development of this method made it possible to describe tasks of a different range of disciplines, to form blocks of decisions, answers, prompts, etc. (depending on the requirements put forward by the form of testing). Based on this method, a "cloud" service for developing test task generators is implemented. Moreover, to build the generation algorithms does not require knowledge of the syntax - the development of the generator is carried out using visual components directly on the Web page.
In the process of writing the article, my scientific articles were used.
If the topic was interesting, I will write the further development of the project and present a system for developing multivariate test tasks implemented as part of an open Internet application.
It is no secret that providing testing with multivariate test items can reduce the effect of cheating among students. Automation of multivariate tasks falls on the shoulders of an algorithm embedded in a software generator. The literature describing methods for generating tasks cannot be counted, but not a single method claims to be universal, but is intended to build a generator or a specific task or a certain class of tasks.
The use of programming languages to describe the generation algorithms is not susceptible to criticism and has several advantages relative to the available methods, since the program code and the capabilities of the language used allow us to describe tasks for a wide class of disciplines. The only drawback is the lack of programming skills for most teachers, especially for humanities.
| Multivariate job example | |
|---|---|
Option 1.
| Option 2
|
In this article, as a method for describing generation algorithms, we use the approach of generating combinatorial sets based on the AND / OR tree, as well as an attempt to formalize it in the form of a programming language. I will try to prove that the use of this method will allow us to describe task generators for various classes of disciplines (technical, humanitarian, etc.) and for various forms of testing ...
The concept of a tree AND / OR
An AND / OR tree is a tree consisting of nodes of 2 types: an I-node and an OR-node. The figure below shows a schematic representation of the nodes of the AND / OR tree.
A variant of an AND / OR tree is a tree obtained from a given one by cutting off all arcs, except one, from the OR nodes. The root of the option will be the root of the source tree. The figure shows the AND / OR tree and all its variants.
The power of an AND / OR tree is the number of options it contains. So, the power of the tree shown in the figure is 6.
Another remarkable property of the AND / OR tree is the possibility of identifying a variant (obtaining a variant by its number) [1].
The relationship of the AND / OR tree with the test task
Consider the principle of describing the algorithm for generating a task in the form of an AND / OR tree using the example of the 1st task from the table above.
To do this, the task text is divided into fragments. Usually fragments are divided into nodes: constants and variables. For variable nodes, sets of implementations are written, each of which represents a specific text. Then, each of the selected implementation nodes is analyzed and, if possible, are divided into variable and constant nodes.
Attention! In the figure below, a schematic illustration of AND / OR nodes: AND node - with an arc, OR node - without an arc.
Having performed the left-side bypass of the variant and writing out the corresponding nodes, we obtain a specific description of the function. For example:
1. Option {A1, B1, C, D1, E1, F, G}
Anya bought a ticket for a year and made 5 trips within 25 days. How many rubles did she overpay if the ticket costs 2400 rubles, and a single trip is 15 rubles?
2. Option {A2, B1, C, D1, E1, F, G}
Sveta bought a ticket for a year and made 5 trips within 25 days. How many rubles did she overpay if the ticket costs 2400 rubles, and a single trip is 15 rubles?
Such a representation clearly shows the structure of the whole question for the developer, however, a syntax for the description of such tree structures is necessary.
Tree Description Syntax AND / OR
It is proposed to use bracket notation for writing AND / OR trees: parentheses denote I-nodes, curly brackets indicate OR-nodes, nodes without brackets are sheets. Tree nodes can be named and unnamed. Named ones are those nodes that have an identifier, unnamed ones are those that have no identifier. The node identifier is an atom and can be represented by two types: a string or a number. An identifier may consist of any set of characters, excluding reserved characters and a space character.
The considered task in the form of an AND / OR tree in a programming language is as follows:
Main (A {“Anya”, “Sveta”, “Marina”}, B {“bought”, “acquired”}, “ticket”, C {“for a year”, “for half a year”, “for a month”} , D {(“and did during”, [1..28], “days”), “and did during the month”, “during the week”}, E {([15..20], “trips ”)}, F {“ how many rubles did she overpay if the ticket costs ”, [100,100..7000],“ rubles, and a one-time trip ”, [15..20],“ rubles? ”})) The
further task is reduced to the implementation of the interpreter of this syntactic construction, as well as the implementation of algorithms for obtaining a variant by its number and counting the power of the tree number for this task).
Language F #
Given the recursive nature of the AND / OR tree, I looked in the direction of the multiparadigmal language F #. The F # language provides a complete set of functional programming tools: algebraic data types, higher-order functions, means for composing functions, and immutable data structures. All F # functionality is implemented on top of the common .NET Framework type system.
An integral part of the implementation of the interpreter is the lexical and syntactic analysis of the lines entered by the user, which allows translating the bracket record of AND / OR trees into the described data type of the AND / OR tree. Among the various code analyzers, the Yacc program library deserves attention, in particular, due to the fact that it contains lexical and syntactic analyzers at once and allows outputting the result in F # (FYacc). To describe the lexical analyzer in the F # language, the syntax diagram of the AND / OR tree is given.
A parser based on character constructs defined by regular expressions uses a recursive descent when trying to cast the resulting string to the Tree type, which in turn will be described in a marked-up union:
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}
Labeled F # language associations allow you to describe types, taking into account the recursive nature of AND / OR trees, and, using pattern matching, immediately start applying various operations on leaves and tree nodes. Marked union for AND / OR tree:
type AndOrTree =
// A node can contain one or more nodes AND
| And of AndOrTree list
// A node may contain one or more nodes OR
| Or of AndOrTree list
// Leaves of the tree may contain integer values
| Int of int
// Leaves of the tree may contain string values
| String of string
// Leaves of the tree may contain floating point values
| Float of float
// Nodes can be named
| SetNameTree of string * AndOrTree
// Nodes may contain the name of the node initialized earlier
| GetNameTree of string * AndOrTree
// Denote the root node
and Tree =
| Tree of AndOrTree
Conclusion
Further development of this method made it possible to describe tasks of a different range of disciplines, to form blocks of decisions, answers, prompts, etc. (depending on the requirements put forward by the form of testing). Based on this method, a "cloud" service for developing test task generators is implemented. Moreover, to build the generation algorithms does not require knowledge of the syntax - the development of the generator is carried out using visual components directly on the Web page.
In the process of writing the article, my scientific articles were used.
If the topic was interesting, I will write the further development of the project and present a system for developing multivariate test tasks implemented as part of an open Internet application.
List of sources used
- Kruchinin V.V. Using AND / OR trees to generate questions and tasks // Bulletin of Tomsk State University. 2004. No. 284. S. 183 - 186.
- Zorin Yu.A. Interpreter of the language for constructing test task generators based on AND / OR trees // Reports of Tomsk State University of Control Systems and Radioelectronics. 2013. No1. S. 75 - 79.
- Zorin Yu.A. The use of combinatorial generation algorithms in the construction of test task generators // Distance and virtual learning. 2013. No.6. S. 54 - 59.