Method for generating test tasks based on AND / OR trees and its software implementation
My first topic on Habré will be devoted to my research, which is connected with the methods of constructing algorithms for generating test tasks for organizing knowledge control of students.
It is not a secret that providing test with multivariate test items allows reducing the effect of cheating among trainees. Automation of obtaining multiple tasks falls on the shoulders of an algorithm embedded in the software generator. The literature describing the methods of generating tasks is not amenable to counting, but not a single method claims to be universal, but is intended to build a generator either for a specific task or for a specific class of tasks.
The use of programming languages to describe generation algorithms is not amenable to criticism and has a number of advantages with respect to the methods available, since the program code and the capabilities of the language used make it possible to describe tasks for a wide class of disciplines. The only drawback is the lack of programming skills in most teachers, especially in the humanities.
')
In this article, the method of generating combinatorial sets based on the AND / OR tree is used as a method for describing generation algorithms, as well as an attempt to formalize it in the form of a program language. I will try to prove that using this method will allow to describe task generators for a different class of disciplines (technical, humanitarian, etc.) and for various forms of testing ...
A tree AND / OR will be called a tree consisting of nodes of 2 types: AND-node and OR-node. The figure below shows a schematic representation of the AND / OR tree nodes.
A variant of the AND / OR tree is a tree obtained from a given path by cutting off all the arcs, except one, at the OR nodes. The root of the variant is the root of the source tree. The picture shows the tree AND / OR and all its variants.
The power of the tree AND / OR is the number of variants it contains. Thus, the power of the tree presented 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 presented above.
For this, the task text is divided into fragments. Usually fragments are divided into nodes: constant and variables. For variable nodes, sets of implementations are written, each of which is a specific text. Each of the selected implementation nodes is then analyzed and, if possible, broken down into variables and permanent nodes.
Attention! The figure below shows a schematic representation of AND / OR nodes: AND node with arc, OR node without arc.
Having performed the left-sided round of the variant and having written out the corresponding nodes, we get a concrete description of the function. For example:
1. Option {A1, B1, C, D1, E1, F, G}
Anya bought a travel ticket for a year and made 5 trips within 25 days. How many rubles she overpaid, if the ticket costs 2400 rubles, and a one-time trip 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 she overpaid, if the ticket costs 2400 rubles, and a one-time trip 15 rubles?
Such a presentation visually displays the structure of the whole question for the developer, however, a syntax is needed to describe such tree structures.
To write trees AND / OR it is proposed to use the bracket notation: round brackets denote AND nodes, curly OR nodes, nodes without brackets are sheets. Tree nodes can be named and unnamed. Named - those nodes that have an identifier, unnamed - those that have no identifier. A node identifier is an atom and can be represented by two types: a string or a number. The identifier may consist of any character set, excluding reserved characters and the space character.
The considered task in the form of a tree AND / OR in the program language looks as follows:
Main (A {“Anya”, “Sveta”, “Marina”}, B {“bought”, “acquired”}, “travel card”, C {“for a year”, “for half a year”, “for a month”} , D {(“and made within”, [1..28], “days”), “and made within a month”, “within a week”}, E {([15..20], “trips ")}, F {" how many rubles she overpaid if the ticket is worth, "[100,100..7000]," rubles, and a one-time trip ", [15..20]," rubles? "}))
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 (the maximum number of options for the task).
Given the recursive nature of the tree AND / OR, I looked in the direction of the F # multi-paradigm language. The F # language provides a complete set of functional programming tools: algebraic data types, higher-order functions, means for combining functions, and immutable data structures. All the functionality of F # 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 strings entered by the user, which allows translating the bracket entry of AND / OR trees into the described data type of the AND / OR tree. Among various code analyzers, the “Yacc” program library deserves attention, in particular, due to the fact that it contains lexical and syntactic analyzers in its structure and allows you to produce the result in F # (FYacc). To describe the lexical analyzer in the F # language, the syntax diagram of the AND / OR tree is given.
The parser based on character constructions defined by regular expressions uses recursive descent when attempting to cast the resulting string to the Tree type, which in turn will be described in a marked 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}
Marked unions of the F # language allow us to describe the types, taking into account the recursive nature of the trees AND / OR, and using pattern matching, immediately begin applying various operations on the leaves and nodes of the tree. Marked union for tree AND / OR:
type AndOrTree =
// A node can contain one or more nodes.
| And of AndOrTree list
// A node can contain one or more nodes OR
| Or of AndOrTree list
// The leaves of the tree can contain integer values
| Int of int
// The leaves of the tree can contain string values
| String of string
// The leaves of the tree may contain floating point values
| Float of float
// Nodes can be named
| SetNameTree of string * AndOrTree
// Nodes can contain the name of a node that was previously initialized.
| GetNameTree of string * AndOrTree
// Denote the root node
and Tree =
| Tree of AndOrTree
Further development of this method allowed us to describe the tasks of a different range of disciplines, to form blocks of decisions, answers, tips, etc. (depending on the requirements put forward by the form of testing). On the basis of this method, a cloud service for the development of test task generators has been implemented. Moreover, the generation of generation algorithms does not require knowledge of the syntax - the generator is developed using visual components directly on the Web page.
In the process of writing an 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 within the framework of an open Internet application.
It is not a secret that providing test with multivariate test items allows reducing the effect of cheating among trainees. Automation of obtaining multiple tasks falls on the shoulders of an algorithm embedded in the software generator. The literature describing the methods of generating tasks is not amenable to counting, but not a single method claims to be universal, but is intended to build a generator either for a specific task or for a specific class of tasks.
The use of programming languages to describe generation algorithms is not amenable to criticism and has a number of advantages with respect to the methods available, since the program code and the capabilities of the language used make it possible to describe tasks for a wide class of disciplines. The only drawback is the lack of programming skills in most teachers, especially in the humanities.
')
| Multivariate example | |
|---|---|
Option 1.
| Option 2.
|
In this article, the method of generating combinatorial sets based on the AND / OR tree is used as a method for describing generation algorithms, as well as an attempt to formalize it in the form of a program language. I will try to prove that using this method will allow to describe task generators for a different class of disciplines (technical, humanitarian, etc.) and for various forms of testing ...
The concept of wood AND / OR
A tree AND / OR will be called a tree consisting of nodes of 2 types: AND-node and OR-node. The figure below shows a schematic representation of the AND / OR tree nodes.
A variant of the AND / OR tree is a tree obtained from a given path by cutting off all the arcs, except one, at the OR nodes. The root of the variant is the root of the source tree. The picture shows the tree AND / OR and all its variants.
The power of the tree AND / OR is the number of variants it contains. Thus, the power of the tree presented 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 connection of the tree AND / OR 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 presented above.
For this, the task text is divided into fragments. Usually fragments are divided into nodes: constant and variables. For variable nodes, sets of implementations are written, each of which is a specific text. Each of the selected implementation nodes is then analyzed and, if possible, broken down into variables and permanent nodes.
Attention! The figure below shows a schematic representation of AND / OR nodes: AND node with arc, OR node without arc.
Having performed the left-sided round of the variant and having written out the corresponding nodes, we get a concrete description of the function. For example:
1. Option {A1, B1, C, D1, E1, F, G}
Anya bought a travel ticket for a year and made 5 trips within 25 days. How many rubles she overpaid, if the ticket costs 2400 rubles, and a one-time trip 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 she overpaid, if the ticket costs 2400 rubles, and a one-time trip 15 rubles?
Such a presentation visually displays the structure of the whole question for the developer, however, a syntax is needed to describe such tree structures.
Tree Description Syntax AND / OR
To write trees AND / OR it is proposed to use the bracket notation: round brackets denote AND nodes, curly OR nodes, nodes without brackets are sheets. Tree nodes can be named and unnamed. Named - those nodes that have an identifier, unnamed - those that have no identifier. A node identifier is an atom and can be represented by two types: a string or a number. The identifier may consist of any character set, excluding reserved characters and the space character.
The considered task in the form of a tree AND / OR in the program language looks as follows:
Main (A {“Anya”, “Sveta”, “Marina”}, B {“bought”, “acquired”}, “travel card”, C {“for a year”, “for half a year”, “for a month”} , D {(“and made within”, [1..28], “days”), “and made within a month”, “within a week”}, E {([15..20], “trips ")}, F {" how many rubles she overpaid if the ticket is worth, "[100,100..7000]," rubles, and a one-time trip ", [15..20]," rubles? "}))
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 (the maximum number of options for the task).
F # language
Given the recursive nature of the tree AND / OR, I looked in the direction of the F # multi-paradigm language. The F # language provides a complete set of functional programming tools: algebraic data types, higher-order functions, means for combining functions, and immutable data structures. All the functionality of F # 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 strings entered by the user, which allows translating the bracket entry of AND / OR trees into the described data type of the AND / OR tree. Among various code analyzers, the “Yacc” program library deserves attention, in particular, due to the fact that it contains lexical and syntactic analyzers in its structure and allows you to produce the result in F # (FYacc). To describe the lexical analyzer in the F # language, the syntax diagram of the AND / OR tree is given.
The parser based on character constructions defined by regular expressions uses recursive descent when attempting to cast the resulting string to the Tree type, which in turn will be described in a marked 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}
Marked unions of the F # language allow us to describe the types, taking into account the recursive nature of the trees AND / OR, and using pattern matching, immediately begin applying various operations on the leaves and nodes of the tree. Marked union for tree AND / OR:
type AndOrTree =
// A node can contain one or more nodes.
| And of AndOrTree list
// A node can contain one or more nodes OR
| Or of AndOrTree list
// The leaves of the tree can contain integer values
| Int of int
// The leaves of the tree can contain string values
| String of string
// The leaves of the tree may contain floating point values
| Float of float
// Nodes can be named
| SetNameTree of string * AndOrTree
// Nodes can contain the name of a node that was previously initialized.
| GetNameTree of string * AndOrTree
// Denote the root node
and Tree =
| Tree of AndOrTree
Conclusion
Further development of this method allowed us to describe the tasks of a different range of disciplines, to form blocks of decisions, answers, tips, etc. (depending on the requirements put forward by the form of testing). On the basis of this method, a cloud service for the development of test task generators has been implemented. Moreover, the generation of generation algorithms does not require knowledge of the syntax - the generator is developed using visual components directly on the Web page.
In the process of writing an 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 within the framework of an open Internet application.
List of sources used
- Kruchinin V.V. Using trees AND / OR to generate questions and problems // Tomsk State University Bulletin. 2004. №284. Pp. 183 - 186.
- Zorin Yu.A. The interpreter of the language for constructing generators of test tasks on the basis of AND / OR trees // Reports of Tomsk State University of Control Systems and Radioelectronics. 2013. №1. Pp. 75 - 79.
- Zorin Yu.A. The use of combinatorial generation algorithms in the construction of test task generators // Remote and virtual learning. 2013. №6. S. 54 - 59.
Source: https://habr.com/ru/post/198068/
All Articles